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.
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.
8 use std::hash::{Hash, Hasher};
11 use rustc::ich::{StableHashingContext, StableHashingContextProvider};
13 use rustc::mir::interpret::{
14 AllocId, Pointer, Scalar,
15 Relocations, Allocation, UndefMask,
16 EvalResult, EvalErrorKind,
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;
27 use super::eval_context::{LocalValue, StackPopCleanup};
28 use super::{Frame, Memory, Operand, MemPlace, Place, Value, ScalarMaybeUndef};
29 use const_eval::CompileTimeInterpreter;
32 pub(crate) struct InfiniteLoopDetector<'a, 'mir, 'tcx: 'a + 'mir> {
33 /// The set of all `EvalSnapshot` *hashes* observed by this detector.
35 /// When a collision occurs in this table, we store the full snapshot in
37 hashes: FxHashSet<u64>,
39 /// The set of all `EvalSnapshot`s observed by this detector.
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>>,
47 impl<'a, 'mir, 'tcx> InfiniteLoopDetector<'a, 'mir, 'tcx>
49 pub fn observe_and_analyze<'b>(
51 tcx: &TyCtxt<'b, 'tcx, 'tcx>,
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();
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");
68 if self.hashes.insert(hash) {
73 // We need to make a full copy. NOW things that to get really expensive.
74 info!("snapshotting the state of the interpreter");
76 if self.snapshots.insert(EvalSnapshot::new(memory, stack)) {
77 // Spurious collision or first cycle
82 Err(EvalErrorKind::InfiniteLoop.into())
86 trait SnapshotContext<'a> {
87 fn resolve(&'a self, id: &AllocId) -> Option<&'a Allocation>;
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>> {
94 fn snapshot(&self, ctx: &'a Ctx) -> Self::Item;
97 macro_rules! __impl_snapshot_field {
98 ($field:ident, $ctx:expr) => ($field.snapshot($ctx));
99 ($field:ident, $ctx:expr, $delegate:expr) => ($delegate);
102 // This assumes the type has two type parameters, first for the tag (set to `()`),
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)*),* ) )* ),* $(,)*
110 impl<'a, Ctx> self::Snapshot<'a, Ctx> for $enum_name
111 where Ctx: self::SnapshotContext<'a>,
113 type Item = $enum_name<(), AllocIdSnapshot<'a>>;
116 fn snapshot(&self, __ctx: &'a Ctx) -> Self::Item {
119 $enum_name::$variant $( ( $(ref $field),* ) )* =>
120 $enum_name::$variant $(
121 ( $( __impl_snapshot_field!($field, __ctx $(, $delegate)*) ),* ),
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>,
134 type Item = $struct_name<(), AllocIdSnapshot<'a>>;
137 fn snapshot(&self, __ctx: &'a Ctx) -> Self::Item {
143 $( $field: __impl_snapshot_field!($field, __ctx $(, $delegate)*) ),*
150 impl<'a, Ctx, T> Snapshot<'a, Ctx> for Option<T>
151 where Ctx: SnapshotContext<'a>,
154 type Item = Option<<T as Snapshot<'a, Ctx>>::Item>;
156 fn snapshot(&self, ctx: &'a Ctx) -> Self::Item {
158 Some(x) => Some(x.snapshot(ctx)),
164 #[derive(Eq, PartialEq)]
165 struct AllocIdSnapshot<'a>(Option<AllocationSnapshot<'a>>);
167 impl<'a, Ctx> Snapshot<'a, Ctx> for AllocId
168 where Ctx: SnapshotContext<'a>,
170 type Item = AllocIdSnapshot<'a>;
172 fn snapshot(&self, ctx: &'a Ctx) -> Self::Item {
173 AllocIdSnapshot(ctx.resolve(self).map(|alloc| alloc.snapshot(ctx)))
177 impl_snapshot_for!(struct Pointer {
179 offset -> *offset, // just copy offset verbatim
180 tag -> *tag, // just copy tag
183 impl<'a, Ctx> Snapshot<'a, Ctx> for Scalar
184 where Ctx: SnapshotContext<'a>,
186 type Item = Scalar<(), AllocIdSnapshot<'a>>;
188 fn snapshot(&self, ctx: &'a Ctx) -> Self::Item {
190 Scalar::Ptr(p) => Scalar::Ptr(p.snapshot(ctx)),
191 Scalar::Bits{ size, bits } => Scalar::Bits {
199 impl_stable_hash_for!(enum ::interpret::ScalarMaybeUndef {
204 impl_snapshot_for!(enum ScalarMaybeUndef {
209 impl_stable_hash_for!(struct ::interpret::MemPlace {
214 impl_snapshot_for!(struct MemPlace {
217 align -> *align, // just copy alignment verbatim
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>)
226 mem::discriminant(self).hash_stable(hcx, hasher);
228 Place::Ptr(mem_place) => mem_place.hash_stable(hcx, hasher),
230 Place::Local { frame, local } => {
231 frame.hash_stable(hcx, hasher);
232 local.hash_stable(hcx, hasher);
237 impl<'a, Ctx> Snapshot<'a, Ctx> for Place
238 where Ctx: SnapshotContext<'a>,
240 type Item = Place<(), AllocIdSnapshot<'a>>;
242 fn snapshot(&self, ctx: &'a Ctx) -> Self::Item {
244 Place::Ptr(p) => Place::Ptr(p.snapshot(ctx)),
246 Place::Local{ frame, local } => Place::Local{
254 impl_stable_hash_for!(enum ::interpret::Value {
258 impl_snapshot_for!(enum Value {
263 impl_stable_hash_for!(enum ::interpret::Operand {
267 impl_snapshot_for!(enum Operand {
272 impl_stable_hash_for!(enum ::interpret::LocalValue {
276 impl_snapshot_for!(enum LocalValue {
281 impl<'a, Ctx> Snapshot<'a, Ctx> for Relocations
282 where Ctx: SnapshotContext<'a>,
284 type Item = Relocations<(), AllocIdSnapshot<'a>>;
286 fn snapshot(&self, ctx: &'a Ctx) -> Self::Item {
287 Relocations::from_presorted(self.iter()
288 .map(|(size, ((), id))| (*size, ((), id.snapshot(ctx))))
293 #[derive(Eq, PartialEq)]
294 struct AllocationSnapshot<'a> {
296 relocations: Relocations<(), AllocIdSnapshot<'a>>,
297 undef_mask: &'a UndefMask,
299 mutability: &'a Mutability,
302 impl<'a, Ctx> Snapshot<'a, Ctx> for &'a Allocation
303 where Ctx: SnapshotContext<'a>,
305 type Item = AllocationSnapshot<'a>;
307 fn snapshot(&self, ctx: &'a Ctx) -> Self::Item {
308 let Allocation { bytes, relocations, undef_mask, align, mutability, extra: () } = self;
315 relocations: relocations.snapshot(ctx),
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>(
324 hcx: &mut StableHashingContext<'a>,
325 hasher: &mut StableHasher<W>)
327 mem::discriminant(self).hash_stable(hcx, hasher);
329 StackPopCleanup::Goto(ref block) => block.hash_stable(hcx, hasher),
330 StackPopCleanup::None { cleanup } => cleanup.hash_stable(hcx, hasher),
335 #[derive(Eq, PartialEq)]
336 struct FrameSnapshot<'a, 'tcx: 'a> {
337 instance: &'a ty::Instance<'tcx>,
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,
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>(
350 hcx: &mut StableHashingContext<'a>,
351 hasher: &mut StableHasher<W>) {
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);
368 impl<'a, 'mir, 'tcx, Ctx> Snapshot<'a, Ctx> for &'a Frame<'mir, 'tcx>
369 where Ctx: SnapshotContext<'a>,
371 type Item = FrameSnapshot<'a, 'tcx>;
373 fn snapshot(&self, ctx: &'a Ctx) -> Self::Item {
391 return_place: return_place.map(|r| r.snapshot(ctx)),
392 locals: locals.iter().map(|local| local.snapshot(ctx)).collect(),
397 impl<'a, 'b, 'mir, 'tcx: 'a+'mir> SnapshotContext<'b>
398 for Memory<'a, 'mir, 'tcx, CompileTimeInterpreter<'a, 'mir, 'tcx>>
400 fn resolve(&'b self, id: &AllocId) -> Option<&'b Allocation> {
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>>,
413 impl<'a, 'mir, 'tcx: 'a + 'mir> EvalSnapshot<'a, 'mir, 'tcx>
416 memory: &Memory<'a, 'mir, 'tcx, CompileTimeInterpreter<'a, 'mir, 'tcx>>,
417 stack: &[Frame<'mir, 'tcx>]
420 memory: memory.clone(),
425 // Used to compare two snapshots
426 fn snapshot(&'b self)
427 -> Vec<FrameSnapshot<'b, 'tcx>>
429 // Start with the stack, iterate and recursively snapshot
430 self.stack.iter().map(|frame| frame.snapshot(&self.memory)).collect()
435 impl<'a, 'mir, 'tcx> Hash for EvalSnapshot<'a, 'mir, 'tcx>
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)
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>
451 fn hash_stable<W: StableHasherResult>(
453 hcx: &mut StableHashingContext<'b>,
454 hasher: &mut StableHasher<W>)
456 // Not hashing memory: Avoid hashing memory all the time during execution
457 let EvalSnapshot{ memory: _, stack } = self;
458 stack.hash_stable(hcx, hasher);
462 impl<'a, 'mir, 'tcx> Eq for EvalSnapshot<'a, 'mir, 'tcx>
465 impl<'a, 'mir, 'tcx> PartialEq for EvalSnapshot<'a, 'mir, 'tcx>
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,
471 self.snapshot() == other.snapshot()