CTFE fails to detect a certain class of infinite loops

[ecstatic-morse]

#51702 implemented a limited form of infinite loop detection during const evaluation by periodically comparing MIR interpreter states.

Currently, the detector considers AllocIds when comparing interpreter memory. It is possible for two interpreter states which have different AllocIds to be functionally equivalent if the underlying allocations have the same structure and values. For example, the following code, which could easily be terminated by the infinite loop detector, causes const evaluation to continue forever.

#![feature(const_fn, const_let)]

const fn churn_alloc_id() -> usize {
    let mut x: &i32 = &5;
    loop {
        x = &5;
    }
    0
}

fn main() {
    let _ = [(); churn_alloc_id()];
}

This hangs the current nightly build (2017-07-16).

@oli-obk suggested to ignore AllocIds by traversing all allocations in interpreter memory at a given moment in time in a predictable order. If two traversals observe logically equivalent Allocations in the same order, the interpreter state as a whole is logically equivalent as well.

I have some free time again, so I'll try to implement this.

[brunocodutra]

I decided to give a stab at fixing this issue and I believe I made some good progress, my WIP is in #52626.

So far I managed to generalize the implementation of Hash for EvalSnapshot to traverse Allocations beginning from ByRef locals and transitively resolving relocations, thus avoiding hashing alloc_ids. The next step is to generalize the implementation of PartialEq for EvalSnapshot in a similar way.

@ecstatic-morse did you get to start implementing a fix as well? Maybe we could complement each other's work.

[ecstatic-morse]

I haven't gotten started yet; I don't have as much free time as I thought 😄. I'll look at what you have so far though!

[jplatte]

@ecstatic-morse This can be closed, right? The PR that fixes this (according to its description) has long been merged.

[ecstatic-morse]

I haven't looked at that PR, but it seems like the test is passing, so let's close this.