src/librustc_mir/const_eval/machine.rs

   1 use rustc::mir;
   2 use rustc::ty::layout::HasTyCtxt;
   3 use rustc::ty::{self, Ty};
   4 use std::borrow::{Borrow, Cow};
   5 use std::collections::hash_map::Entry;
   6 use std::hash::Hash;
   7
   8 use rustc_data_structures::fx::FxHashMap;
   9
  10 use rustc::mir::AssertMessage;
  11 use rustc_span::source_map::Span;
  12 use rustc_span::symbol::Symbol;
  13
  14 use crate::interpret::{
  15     self, snapshot, AllocId, Allocation, GlobalId, ImmTy, InterpCx, InterpResult, Memory,
  16     MemoryKind, OpTy, PlaceTy, Pointer, Scalar,
  17 };
  18
  19 use super::error::*;
  20
  21 impl<'mir, 'tcx> InterpCx<'mir, 'tcx, CompileTimeInterpreter<'mir, 'tcx>> {
  22     /// Evaluate a const function where all arguments (if any) are zero-sized types.
  23     /// The evaluation is memoized thanks to the query system.
  24     ///
  25     /// Returns `true` if the call has been evaluated.
  26     fn try_eval_const_fn_call(
  27         &mut self,
  28         instance: ty::Instance<'tcx>,
  29         ret: Option<(PlaceTy<'tcx>, mir::BasicBlock)>,
  30         args: &[OpTy<'tcx>],
  31     ) -> InterpResult<'tcx, bool> {
  32         trace!("try_eval_const_fn_call: {:?}", instance);
  33         // Because `#[track_caller]` adds an implicit non-ZST argument, we also cannot
  34         // perform this optimization on items tagged with it.
  35         if instance.def.requires_caller_location(self.tcx()) {
  36             return Ok(false);
  37         }
  38         // For the moment we only do this for functions which take no arguments
  39         // (or all arguments are ZSTs) so that we don't memoize too much.
  40         if args.iter().any(|a| !a.layout.is_zst()) {
  41             return Ok(false);
  42         }
  43
  44         let dest = match ret {
  45             Some((dest, _)) => dest,
  46             // Don't memoize diverging function calls.
  47             None => return Ok(false),
  48         };
  49
  50         let gid = GlobalId { instance, promoted: None };
  51
  52         let place = self.const_eval_raw(gid)?;
  53
  54         self.copy_op(place.into(), dest)?;
  55
  56         self.return_to_block(ret.map(|r| r.1))?;
  57         self.dump_place(*dest);
  58         return Ok(true);
  59     }
  60
  61     /// "Intercept" a function call to a panic-related function
  62     /// because we have something special to do for it.
  63     /// If this returns successfully (`Ok`), the function should just be evaluated normally.
  64     fn hook_panic_fn(
  65         &mut self,
  66         span: Span,
  67         instance: ty::Instance<'tcx>,
  68         args: &[OpTy<'tcx>],
  69     ) -> InterpResult<'tcx> {
  70         let def_id = instance.def_id();
  71         if Some(def_id) == self.tcx.lang_items().panic_fn()
  72             || Some(def_id) == self.tcx.lang_items().begin_panic_fn()
  73         {
  74             // &'static str
  75             assert!(args.len() == 1);
  76
  77             let msg_place = self.deref_operand(args[0])?;
  78             let msg = Symbol::intern(self.read_str(msg_place)?);
  79             let span = self.find_closest_untracked_caller_location().unwrap_or(span);
  80             let (file, line, col) = self.location_triple_for_span(span);
  81             Err(ConstEvalErrKind::Panic { msg, file, line, col }.into())
  82         } else {
  83             Ok(())
  84         }
  85     }
  86 }
  87
  88 /// Number of steps until the detector even starts doing anything.
  89 /// Also, a warning is shown to the user when this number is reached.
  90 const STEPS_UNTIL_DETECTOR_ENABLED: isize = 1_000_000;
  91 /// The number of steps between loop detector snapshots.
  92 /// Should be a power of two for performance reasons.
  93 const DETECTOR_SNAPSHOT_PERIOD: isize = 256;
  94
  95 // Extra machine state for CTFE, and the Machine instance
  96 pub struct CompileTimeInterpreter<'mir, 'tcx> {
  97     /// When this value is negative, it indicates the number of interpreter
  98     /// steps *until* the loop detector is enabled. When it is positive, it is
  99     /// the number of steps after the detector has been enabled modulo the loop
 100     /// detector period.
 101     pub(super) steps_since_detector_enabled: isize,
 102
 103     /// Extra state to detect loops.
 104     pub(super) loop_detector: snapshot::InfiniteLoopDetector<'mir, 'tcx>,
 105 }
 106
 107 #[derive(Copy, Clone, Debug)]
 108 pub struct MemoryExtra {
 109     /// Whether this machine may read from statics
 110     pub(super) can_access_statics: bool,
 111 }
 112
 113 impl<'mir, 'tcx> CompileTimeInterpreter<'mir, 'tcx> {
 114     pub(super) fn new() -> Self {
 115         CompileTimeInterpreter {
 116             loop_detector: Default::default(),
 117             steps_since_detector_enabled: -STEPS_UNTIL_DETECTOR_ENABLED,
 118         }
 119     }
 120 }
 121
 122 impl<K: Hash + Eq, V> interpret::AllocMap<K, V> for FxHashMap<K, V> {
 123     #[inline(always)]
 124     fn contains_key<Q: ?Sized + Hash + Eq>(&mut self, k: &Q) -> bool
 125     where
 126         K: Borrow<Q>,
 127     {
 128         FxHashMap::contains_key(self, k)
 129     }
 130
 131     #[inline(always)]
 132     fn insert(&mut self, k: K, v: V) -> Option<V> {
 133         FxHashMap::insert(self, k, v)
 134     }
 135
 136     #[inline(always)]
 137     fn remove<Q: ?Sized + Hash + Eq>(&mut self, k: &Q) -> Option<V>
 138     where
 139         K: Borrow<Q>,
 140     {
 141         FxHashMap::remove(self, k)
 142     }
 143
 144     #[inline(always)]
 145     fn filter_map_collect<T>(&self, mut f: impl FnMut(&K, &V) -> Option<T>) -> Vec<T> {
 146         self.iter().filter_map(move |(k, v)| f(k, &*v)).collect()
 147     }
 148
 149     #[inline(always)]
 150     fn get_or<E>(&self, k: K, vacant: impl FnOnce() -> Result<V, E>) -> Result<&V, E> {
 151         match self.get(&k) {
 152             Some(v) => Ok(v),
 153             None => {
 154                 vacant()?;
 155                 bug!("The CTFE machine shouldn't ever need to extend the alloc_map when reading")
 156             }
 157         }
 158     }
 159
 160     #[inline(always)]
 161     fn get_mut_or<E>(&mut self, k: K, vacant: impl FnOnce() -> Result<V, E>) -> Result<&mut V, E> {
 162         match self.entry(k) {
 163             Entry::Occupied(e) => Ok(e.into_mut()),
 164             Entry::Vacant(e) => {
 165                 let v = vacant()?;
 166                 Ok(e.insert(v))
 167             }
 168         }
 169     }
 170 }
 171
 172 crate type CompileTimeEvalContext<'mir, 'tcx> =
 173     InterpCx<'mir, 'tcx, CompileTimeInterpreter<'mir, 'tcx>>;
 174
 175 impl interpret::MayLeak for ! {
 176     #[inline(always)]
 177     fn may_leak(self) -> bool {
 178         // `self` is uninhabited
 179         self
 180     }
 181 }
 182
 183 impl<'mir, 'tcx> interpret::Machine<'mir, 'tcx> for CompileTimeInterpreter<'mir, 'tcx> {
 184     type MemoryKinds = !;
 185     type PointerTag = ();
 186     type ExtraFnVal = !;
 187
 188     type FrameExtra = ();
 189     type MemoryExtra = MemoryExtra;
 190     type AllocExtra = ();
 191
 192     type MemoryMap = FxHashMap<AllocId, (MemoryKind<!>, Allocation)>;
 193
 194     const STATIC_KIND: Option<!> = None; // no copying of statics allowed
 195
 196     // We do not check for alignment to avoid having to carry an `Align`
 197     // in `ConstValue::ByRef`.
 198     const CHECK_ALIGN: bool = false;
 199
 200     #[inline(always)]
 201     fn enforce_validity(_ecx: &InterpCx<'mir, 'tcx, Self>) -> bool {
 202         false // for now, we don't enforce validity
 203     }
 204
 205     fn find_mir_or_eval_fn(
 206         ecx: &mut InterpCx<'mir, 'tcx, Self>,
 207         span: Span,
 208         instance: ty::Instance<'tcx>,
 209         args: &[OpTy<'tcx>],
 210         ret: Option<(PlaceTy<'tcx>, mir::BasicBlock)>,
 211         _unwind: Option<mir::BasicBlock>, // unwinding is not supported in consts
 212     ) -> InterpResult<'tcx, Option<&'mir mir::Body<'tcx>>> {
 213         debug!("find_mir_or_eval_fn: {:?}", instance);
 214
 215         // Only check non-glue functions
 216         if let ty::InstanceDef::Item(def_id) = instance.def {
 217             // Execution might have wandered off into other crates, so we cannot do a stability-
 218             // sensitive check here.  But we can at least rule out functions that are not const
 219             // at all.
 220             if ecx.tcx.is_const_fn_raw(def_id) {
 221                 // If this function is a `const fn` then under certain circumstances we
 222                 // can evaluate call via the query system, thus memoizing all future calls.
 223                 if ecx.try_eval_const_fn_call(instance, ret, args)? {
 224                     return Ok(None);
 225                 }
 226             } else {
 227                 // Some functions we support even if they are non-const -- but avoid testing
 228                 // that for const fn!
 229                 ecx.hook_panic_fn(span, instance, args)?;
 230                 // We certainly do *not* want to actually call the fn
 231                 // though, so be sure we return here.
 232                 throw_unsup_format!("calling non-const function `{}`", instance)
 233             }
 234         }
 235         // This is a const fn. Call it.
 236         Ok(Some(match ecx.load_mir(instance.def, None) {
 237             Ok(body) => *body,
 238             Err(err) => {
 239                 if let err_unsup!(NoMirFor(ref path)) = err.kind {
 240                     return Err(ConstEvalErrKind::NeedsRfc(format!(
 241                         "calling extern function `{}`",
 242                         path
 243                     ))
 244                     .into());
 245                 }
 246                 return Err(err);
 247             }
 248         }))
 249     }
 250
 251     fn call_extra_fn(
 252         _ecx: &mut InterpCx<'mir, 'tcx, Self>,
 253         fn_val: !,
 254         _args: &[OpTy<'tcx>],
 255         _ret: Option<(PlaceTy<'tcx>, mir::BasicBlock)>,
 256         _unwind: Option<mir::BasicBlock>,
 257     ) -> InterpResult<'tcx> {
 258         match fn_val {}
 259     }
 260
 261     fn call_intrinsic(
 262         ecx: &mut InterpCx<'mir, 'tcx, Self>,
 263         span: Span,
 264         instance: ty::Instance<'tcx>,
 265         args: &[OpTy<'tcx>],
 266         ret: Option<(PlaceTy<'tcx>, mir::BasicBlock)>,
 267         _unwind: Option<mir::BasicBlock>,
 268     ) -> InterpResult<'tcx> {
 269         if ecx.emulate_intrinsic(span, instance, args, ret)? {
 270             return Ok(());
 271         }
 272         // An intrinsic that we do not support
 273         let intrinsic_name = ecx.tcx.item_name(instance.def_id());
 274         Err(ConstEvalErrKind::NeedsRfc(format!("calling intrinsic `{}`", intrinsic_name)).into())
 275     }
 276
 277     fn assert_panic(
 278         ecx: &mut InterpCx<'mir, 'tcx, Self>,
 279         _span: Span,
 280         msg: &AssertMessage<'tcx>,
 281         _unwind: Option<mir::BasicBlock>,
 282     ) -> InterpResult<'tcx> {
 283         use rustc::mir::AssertKind::*;
 284         // Convert `AssertKind<Operand>` to `AssertKind<u64>`.
 285         let err = match msg {
 286             BoundsCheck { ref len, ref index } => {
 287                 let len = ecx
 288                     .read_immediate(ecx.eval_operand(len, None)?)
 289                     .expect("can't eval len")
 290                     .to_scalar()?
 291                     .to_machine_usize(&*ecx)?;
 292                 let index = ecx
 293                     .read_immediate(ecx.eval_operand(index, None)?)
 294                     .expect("can't eval index")
 295                     .to_scalar()?
 296                     .to_machine_usize(&*ecx)?;
 297                 BoundsCheck { len, index }
 298             }
 299             Overflow(op) => Overflow(*op),
 300             OverflowNeg => OverflowNeg,
 301             DivisionByZero => DivisionByZero,
 302             RemainderByZero => RemainderByZero,
 303             ResumedAfterReturn(generator_kind) => ResumedAfterReturn(*generator_kind),
 304             ResumedAfterPanic(generator_kind) => ResumedAfterPanic(*generator_kind),
 305         };
 306         Err(ConstEvalErrKind::AssertFailure(err).into())
 307     }
 308
 309     fn ptr_to_int(_mem: &Memory<'mir, 'tcx, Self>, _ptr: Pointer) -> InterpResult<'tcx, u64> {
 310         Err(ConstEvalErrKind::NeedsRfc("pointer-to-integer cast".to_string()).into())
 311     }
 312
 313     fn binary_ptr_op(
 314         _ecx: &InterpCx<'mir, 'tcx, Self>,
 315         _bin_op: mir::BinOp,
 316         _left: ImmTy<'tcx>,
 317         _right: ImmTy<'tcx>,
 318     ) -> InterpResult<'tcx, (Scalar, bool, Ty<'tcx>)> {
 319         Err(ConstEvalErrKind::NeedsRfc("pointer arithmetic or comparison".to_string()).into())
 320     }
 321
 322     #[inline(always)]
 323     fn init_allocation_extra<'b>(
 324         _memory_extra: &MemoryExtra,
 325         _id: AllocId,
 326         alloc: Cow<'b, Allocation>,
 327         _kind: Option<MemoryKind<!>>,
 328     ) -> (Cow<'b, Allocation<Self::PointerTag>>, Self::PointerTag) {
 329         // We do not use a tag so we can just cheaply forward the allocation
 330         (alloc, ())
 331     }
 332
 333     #[inline(always)]
 334     fn tag_static_base_pointer(_memory_extra: &MemoryExtra, _id: AllocId) -> Self::PointerTag {
 335         ()
 336     }
 337
 338     fn box_alloc(
 339         _ecx: &mut InterpCx<'mir, 'tcx, Self>,
 340         _dest: PlaceTy<'tcx>,
 341     ) -> InterpResult<'tcx> {
 342         Err(ConstEvalErrKind::NeedsRfc("heap allocations via `box` keyword".to_string()).into())
 343     }
 344
 345     fn before_terminator(ecx: &mut InterpCx<'mir, 'tcx, Self>) -> InterpResult<'tcx> {
 346         {
 347             let steps = &mut ecx.machine.steps_since_detector_enabled;
 348
 349             *steps += 1;
 350             if *steps < 0 {
 351                 return Ok(());
 352             }
 353
 354             *steps %= DETECTOR_SNAPSHOT_PERIOD;
 355             if *steps != 0 {
 356                 return Ok(());
 357             }
 358         }
 359
 360         let span = ecx.frame().span;
 361         ecx.machine.loop_detector.observe_and_analyze(*ecx.tcx, span, &ecx.memory, &ecx.stack[..])
 362     }
 363
 364     #[inline(always)]
 365     fn stack_push(_ecx: &mut InterpCx<'mir, 'tcx, Self>) -> InterpResult<'tcx> {
 366         Ok(())
 367     }
 368
 369     fn before_access_static(
 370         memory_extra: &MemoryExtra,
 371         _allocation: &Allocation,
 372     ) -> InterpResult<'tcx> {
 373         if memory_extra.can_access_statics {
 374             Ok(())
 375         } else {
 376             Err(ConstEvalErrKind::ConstAccessesStatic.into())
 377         }
 378     }
 379 }
 380
 381 // Please do not add any code below the above `Machine` trait impl. I (oli-obk) plan more cleanups
 382 // so we can end up having a file with just that impl, but for now, let's keep the impl discoverable
 383 // at the bottom of this file.