src/librustc_mir/const_eval/machine.rs

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