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