src/librustc_mir/interpret/snapshot.rs

   1 //! This module contains the machinery necessary to detect infinite loops
   2 //! during const-evaluation by taking snapshots of the state of the interpreter
   3 //! at regular intervals.
   4
   5 // This lives in `interpret` because it needs access to all sots of private state.  However,
   6 // it is not used by the general miri engine, just by CTFE.
   7
   8 use std::hash::{Hash, Hasher};
   9 use std::mem;
  10
  11 use rustc::ich::{StableHashingContext, StableHashingContextProvider};
  12 use rustc::mir;
  13 use rustc::mir::interpret::{
  14     AllocId, Pointer, Scalar,
  15     Relocations, Allocation, UndefMask,
  16     EvalResult, EvalErrorKind,
  17 };
  18
  19 use rustc::ty::{self, TyCtxt};
  20 use rustc::ty::layout::Align;
  21 use rustc_data_structures::fx::FxHashSet;
  22 use rustc_data_structures::indexed_vec::IndexVec;
  23 use rustc_data_structures::stable_hasher::{HashStable, StableHasher, StableHasherResult};
  24 use syntax::ast::Mutability;
  25 use syntax::source_map::Span;
  26
  27 use super::eval_context::{LocalValue, StackPopCleanup};
  28 use super::{Frame, Memory, Operand, MemPlace, Place, Value, ScalarMaybeUndef};
  29 use const_eval::CompileTimeInterpreter;
  30
  31 #[derive(Default)]
  32 pub(crate) struct InfiniteLoopDetector<'a, 'mir, 'tcx: 'a + 'mir> {
  33     /// The set of all `EvalSnapshot` *hashes* observed by this detector.
  34     ///
  35     /// When a collision occurs in this table, we store the full snapshot in
  36     /// `snapshots`.
  37     hashes: FxHashSet<u64>,
  38
  39     /// The set of all `EvalSnapshot`s observed by this detector.
  40     ///
  41     /// An `EvalSnapshot` will only be fully cloned once it has caused a
  42     /// collision in `hashes`. As a result, the detector must observe at least
  43     /// *two* full cycles of an infinite loop before it triggers.
  44     snapshots: FxHashSet<EvalSnapshot<'a, 'mir, 'tcx>>,
  45 }
  46
  47 impl<'a, 'mir, 'tcx> InfiniteLoopDetector<'a, 'mir, 'tcx>
  48 {
  49     pub fn observe_and_analyze<'b>(
  50         &mut self,
  51         tcx: &TyCtxt<'b, 'tcx, 'tcx>,
  52         span: Span,
  53         memory: &Memory<'a, 'mir, 'tcx, CompileTimeInterpreter<'a, 'mir, 'tcx>>,
  54         stack: &[Frame<'mir, 'tcx>],
  55     ) -> EvalResult<'tcx, ()> {
  56         // Compute stack's hash before copying anything
  57         let mut hcx = tcx.get_stable_hashing_context();
  58         let mut hasher = StableHasher::<u64>::new();
  59         stack.hash_stable(&mut hcx, &mut hasher);
  60         let hash = hasher.finish();
  61
  62         // Check if we know that hash already
  63         if self.hashes.is_empty() {
  64             // FIXME(#49980): make this warning a lint
  65             tcx.sess.span_warn(span,
  66                 "Constant evaluating a complex constant, this might take some time");
  67         }
  68         if self.hashes.insert(hash) {
  69             // No collision
  70             return Ok(())
  71         }
  72
  73         // We need to make a full copy. NOW things that to get really expensive.
  74         info!("snapshotting the state of the interpreter");
  75
  76         if self.snapshots.insert(EvalSnapshot::new(memory, stack)) {
  77             // Spurious collision or first cycle
  78             return Ok(())
  79         }
  80
  81         // Second cycle
  82         Err(EvalErrorKind::InfiniteLoop.into())
  83     }
  84 }
  85
  86 trait SnapshotContext<'a> {
  87     fn resolve(&'a self, id: &AllocId) -> Option<&'a Allocation>;
  88 }
  89
  90 /// Taking a snapshot of the evaluation context produces a view of
  91 /// the state of the interpreter that is invariant to `AllocId`s.
  92 trait Snapshot<'a, Ctx: SnapshotContext<'a>> {
  93     type Item;
  94     fn snapshot(&self, ctx: &'a Ctx) -> Self::Item;
  95 }
  96
  97 macro_rules! __impl_snapshot_field {
  98     ($field:ident, $ctx:expr) => ($field.snapshot($ctx));
  99     ($field:ident, $ctx:expr, $delegate:expr) => ($delegate);
 100 }
 101
 102 // This assumes the type has two type parameters, first for the tag (set to `()`),
 103 // then for the id
 104 macro_rules! impl_snapshot_for {
 105     // FIXME(mark-i-m): Some of these should be `?` rather than `*`.
 106     (enum $enum_name:ident {
 107         $( $variant:ident $( ( $($field:ident $(-> $delegate:expr)*),* ) )* ),* $(,)*
 108     }) => {
 109
 110         impl<'a, Ctx> self::Snapshot<'a, Ctx> for $enum_name
 111             where Ctx: self::SnapshotContext<'a>,
 112         {
 113             type Item = $enum_name<(), AllocIdSnapshot<'a>>;
 114
 115             #[inline]
 116             fn snapshot(&self, __ctx: &'a Ctx) -> Self::Item {
 117                 match *self {
 118                     $(
 119                         $enum_name::$variant $( ( $(ref $field),* ) )* =>
 120                             $enum_name::$variant $(
 121                                 ( $( __impl_snapshot_field!($field, __ctx $(, $delegate)*) ),* ),
 122                             )*
 123                     )*
 124                 }
 125             }
 126         }
 127     };
 128
 129     // FIXME(mark-i-m): same here.
 130     (struct $struct_name:ident { $($field:ident $(-> $delegate:expr)*),*  $(,)* }) => {
 131         impl<'a, Ctx> self::Snapshot<'a, Ctx> for $struct_name
 132             where Ctx: self::SnapshotContext<'a>,
 133         {
 134             type Item = $struct_name<(), AllocIdSnapshot<'a>>;
 135
 136             #[inline]
 137             fn snapshot(&self, __ctx: &'a Ctx) -> Self::Item {
 138                 let $struct_name {
 139                     $(ref $field),*
 140                 } = *self;
 141
 142                 $struct_name {
 143                     $( $field: __impl_snapshot_field!($field, __ctx $(, $delegate)*) ),*
 144                 }
 145             }
 146         }
 147     };
 148 }
 149
 150 impl<'a, Ctx, T> Snapshot<'a, Ctx> for Option<T>
 151     where Ctx: SnapshotContext<'a>,
 152           T: Snapshot<'a, Ctx>
 153 {
 154     type Item = Option<<T as Snapshot<'a, Ctx>>::Item>;
 155
 156     fn snapshot(&self, ctx: &'a Ctx) -> Self::Item {
 157         match self {
 158             Some(x) => Some(x.snapshot(ctx)),
 159             None => None,
 160         }
 161     }
 162 }
 163
 164 #[derive(Eq, PartialEq)]
 165 struct AllocIdSnapshot<'a>(Option<AllocationSnapshot<'a>>);
 166
 167 impl<'a, Ctx> Snapshot<'a, Ctx> for AllocId
 168     where Ctx: SnapshotContext<'a>,
 169 {
 170     type Item = AllocIdSnapshot<'a>;
 171
 172     fn snapshot(&self, ctx: &'a Ctx) -> Self::Item {
 173         AllocIdSnapshot(ctx.resolve(self).map(|alloc| alloc.snapshot(ctx)))
 174     }
 175 }
 176
 177 impl_snapshot_for!(struct Pointer {
 178     alloc_id,
 179     offset -> *offset, // just copy offset verbatim
 180     tag -> *tag, // just copy tag
 181 });
 182
 183 impl<'a, Ctx> Snapshot<'a, Ctx> for Scalar
 184     where Ctx: SnapshotContext<'a>,
 185 {
 186     type Item = Scalar<(), AllocIdSnapshot<'a>>;
 187
 188     fn snapshot(&self, ctx: &'a Ctx) -> Self::Item {
 189         match self {
 190             Scalar::Ptr(p) => Scalar::Ptr(p.snapshot(ctx)),
 191             Scalar::Bits{ size, bits } => Scalar::Bits {
 192                 size: *size,
 193                 bits: *bits,
 194             },
 195         }
 196     }
 197 }
 198
 199 impl_stable_hash_for!(enum ::interpret::ScalarMaybeUndef {
 200     Scalar(v),
 201     Undef
 202 });
 203
 204 impl_snapshot_for!(enum ScalarMaybeUndef {
 205     Scalar(s),
 206     Undef,
 207 });
 208
 209 impl_stable_hash_for!(struct ::interpret::MemPlace {
 210     ptr,
 211     align,
 212     meta,
 213 });
 214 impl_snapshot_for!(struct MemPlace {
 215     ptr,
 216     meta,
 217     align -> *align, // just copy alignment verbatim
 218 });
 219
 220 // Can't use the macro here because that does not support named enum fields.
 221 impl<'a> HashStable<StableHashingContext<'a>> for Place {
 222     fn hash_stable<W: StableHasherResult>(
 223         &self, hcx: &mut StableHashingContext<'a>,
 224         hasher: &mut StableHasher<W>)
 225     {
 226         mem::discriminant(self).hash_stable(hcx, hasher);
 227         match self {
 228             Place::Ptr(mem_place) => mem_place.hash_stable(hcx, hasher),
 229
 230             Place::Local { frame, local } => {
 231                 frame.hash_stable(hcx, hasher);
 232                 local.hash_stable(hcx, hasher);
 233             },
 234         }
 235     }
 236 }
 237 impl<'a, Ctx> Snapshot<'a, Ctx> for Place
 238     where Ctx: SnapshotContext<'a>,
 239 {
 240     type Item = Place<(), AllocIdSnapshot<'a>>;
 241
 242     fn snapshot(&self, ctx: &'a Ctx) -> Self::Item {
 243         match self {
 244             Place::Ptr(p) => Place::Ptr(p.snapshot(ctx)),
 245
 246             Place::Local{ frame, local } => Place::Local{
 247                 frame: *frame,
 248                 local: *local,
 249             },
 250         }
 251     }
 252 }
 253
 254 impl_stable_hash_for!(enum ::interpret::Value {
 255     Scalar(x),
 256     ScalarPair(x, y),
 257 });
 258 impl_snapshot_for!(enum Value {
 259     Scalar(s),
 260     ScalarPair(s, t),
 261 });
 262
 263 impl_stable_hash_for!(enum ::interpret::Operand {
 264     Immediate(x),
 265     Indirect(x),
 266 });
 267 impl_snapshot_for!(enum Operand {
 268     Immediate(v),
 269     Indirect(m),
 270 });
 271
 272 impl_stable_hash_for!(enum ::interpret::LocalValue {
 273     Dead,
 274     Live(x),
 275 });
 276 impl_snapshot_for!(enum LocalValue {
 277     Live(v),
 278     Dead,
 279 });
 280
 281 impl<'a, Ctx> Snapshot<'a, Ctx> for Relocations
 282     where Ctx: SnapshotContext<'a>,
 283 {
 284     type Item = Relocations<(), AllocIdSnapshot<'a>>;
 285
 286     fn snapshot(&self, ctx: &'a Ctx) -> Self::Item {
 287         Relocations::from_presorted(self.iter()
 288             .map(|(size, ((), id))| (*size, ((), id.snapshot(ctx))))
 289             .collect())
 290     }
 291 }
 292
 293 #[derive(Eq, PartialEq)]
 294 struct AllocationSnapshot<'a> {
 295     bytes: &'a [u8],
 296     relocations: Relocations<(), AllocIdSnapshot<'a>>,
 297     undef_mask: &'a UndefMask,
 298     align: &'a Align,
 299     mutability: &'a Mutability,
 300 }
 301
 302 impl<'a, Ctx> Snapshot<'a, Ctx> for &'a Allocation
 303     where Ctx: SnapshotContext<'a>,
 304 {
 305     type Item = AllocationSnapshot<'a>;
 306
 307     fn snapshot(&self, ctx: &'a Ctx) -> Self::Item {
 308         let Allocation { bytes, relocations, undef_mask, align, mutability, extra: () } = self;
 309
 310         AllocationSnapshot {
 311             bytes,
 312             undef_mask,
 313             align,
 314             mutability,
 315             relocations: relocations.snapshot(ctx),
 316         }
 317     }
 318 }
 319
 320 // Can't use the macro here because that does not support named enum fields.
 321 impl<'a> HashStable<StableHashingContext<'a>> for StackPopCleanup {
 322     fn hash_stable<W: StableHasherResult>(
 323         &self,
 324         hcx: &mut StableHashingContext<'a>,
 325         hasher: &mut StableHasher<W>)
 326     {
 327         mem::discriminant(self).hash_stable(hcx, hasher);
 328         match self {
 329             StackPopCleanup::Goto(ref block) => block.hash_stable(hcx, hasher),
 330             StackPopCleanup::None { cleanup } => cleanup.hash_stable(hcx, hasher),
 331         }
 332     }
 333 }
 334
 335 #[derive(Eq, PartialEq)]
 336 struct FrameSnapshot<'a, 'tcx: 'a> {
 337     instance: &'a ty::Instance<'tcx>,
 338     span: &'a Span,
 339     return_to_block: &'a StackPopCleanup,
 340     return_place: Option<Place<(), AllocIdSnapshot<'a>>>,
 341     locals: IndexVec<mir::Local, LocalValue<(), AllocIdSnapshot<'a>>>,
 342     block: &'a mir::BasicBlock,
 343     stmt: usize,
 344 }
 345
 346 // Not using the macro because that does not support types depending on two lifetimes
 347 impl<'a, 'mir, 'tcx: 'mir> HashStable<StableHashingContext<'a>> for Frame<'mir, 'tcx> {
 348     fn hash_stable<W: StableHasherResult>(
 349         &self,
 350         hcx: &mut StableHashingContext<'a>,
 351         hasher: &mut StableHasher<W>) {
 352
 353         let Frame {
 354             mir,
 355             instance,
 356             span,
 357             return_to_block,
 358             return_place,
 359             locals,
 360             block,
 361             stmt,
 362         } = self;
 363
 364         (mir, instance, span, return_to_block).hash_stable(hcx, hasher);
 365         (return_place.as_ref().map(|r| &**r), locals, block, stmt).hash_stable(hcx, hasher);
 366     }
 367 }
 368 impl<'a, 'mir, 'tcx, Ctx> Snapshot<'a, Ctx> for &'a Frame<'mir, 'tcx>
 369     where Ctx: SnapshotContext<'a>,
 370 {
 371     type Item = FrameSnapshot<'a, 'tcx>;
 372
 373     fn snapshot(&self, ctx: &'a Ctx) -> Self::Item {
 374         let Frame {
 375             mir: _,
 376             instance,
 377             span,
 378             return_to_block,
 379             return_place,
 380             locals,
 381             block,
 382             stmt,
 383         } = self;
 384
 385         FrameSnapshot {
 386             instance,
 387             span,
 388             return_to_block,
 389             block,
 390             stmt: *stmt,
 391             return_place: return_place.map(|r| r.snapshot(ctx)),
 392             locals: locals.iter().map(|local| local.snapshot(ctx)).collect(),
 393         }
 394     }
 395 }
 396
 397 impl<'a, 'b, 'mir, 'tcx: 'a+'mir> SnapshotContext<'b>
 398     for Memory<'a, 'mir, 'tcx, CompileTimeInterpreter<'a, 'mir, 'tcx>>
 399 {
 400     fn resolve(&'b self, id: &AllocId) -> Option<&'b Allocation> {
 401         self.get(*id).ok()
 402     }
 403 }
 404
 405 /// The virtual machine state during const-evaluation at a given point in time.
 406 /// We assume the `CompileTimeInterpreter` has no interesting extra state that
 407 /// is worth considering here.
 408 struct EvalSnapshot<'a, 'mir, 'tcx: 'a + 'mir> {
 409     memory: Memory<'a, 'mir, 'tcx, CompileTimeInterpreter<'a, 'mir, 'tcx>>,
 410     stack: Vec<Frame<'mir, 'tcx>>,
 411 }
 412
 413 impl<'a, 'mir, 'tcx: 'a + 'mir> EvalSnapshot<'a, 'mir, 'tcx>
 414 {
 415     fn new(
 416         memory: &Memory<'a, 'mir, 'tcx, CompileTimeInterpreter<'a, 'mir, 'tcx>>,
 417         stack: &[Frame<'mir, 'tcx>]
 418     ) -> Self {
 419         EvalSnapshot {
 420             memory: memory.clone(),
 421             stack: stack.into(),
 422         }
 423     }
 424
 425     // Used to compare two snapshots
 426     fn snapshot(&'b self)
 427         -> Vec<FrameSnapshot<'b, 'tcx>>
 428     {
 429         // Start with the stack, iterate and recursively snapshot
 430         self.stack.iter().map(|frame| frame.snapshot(&self.memory)).collect()
 431     }
 432
 433 }
 434
 435 impl<'a, 'mir, 'tcx> Hash for EvalSnapshot<'a, 'mir, 'tcx>
 436 {
 437     fn hash<H: Hasher>(&self, state: &mut H) {
 438         // Implement in terms of hash stable, so that k1 == k2 -> hash(k1) == hash(k2)
 439         let mut hcx = self.memory.tcx.get_stable_hashing_context();
 440         let mut hasher = StableHasher::<u64>::new();
 441         self.hash_stable(&mut hcx, &mut hasher);
 442         hasher.finish().hash(state)
 443     }
 444 }
 445
 446 // Not using the macro because we need special handling for `memory`, which the macro
 447 // does not support at the same time as the extra bounds on the type.
 448 impl<'a, 'b, 'mir, 'tcx> HashStable<StableHashingContext<'b>>
 449     for EvalSnapshot<'a, 'mir, 'tcx>
 450 {
 451     fn hash_stable<W: StableHasherResult>(
 452         &self,
 453         hcx: &mut StableHashingContext<'b>,
 454         hasher: &mut StableHasher<W>)
 455     {
 456         // Not hashing memory: Avoid hashing memory all the time during execution
 457         let EvalSnapshot{ memory: _, stack } = self;
 458         stack.hash_stable(hcx, hasher);
 459     }
 460 }
 461
 462 impl<'a, 'mir, 'tcx> Eq for EvalSnapshot<'a, 'mir, 'tcx>
 463 {}
 464
 465 impl<'a, 'mir, 'tcx> PartialEq for EvalSnapshot<'a, 'mir, 'tcx>
 466 {
 467     fn eq(&self, other: &Self) -> bool {
 468         // FIXME: This looks to be a *ridicolously expensive* comparison operation.
 469         // Doesn't this make tons of copies?  Either `snapshot` is very badly named,
 470         // or it does!
 471         self.snapshot() == other.snapshot()
 472     }
 473 }