Skip to content

CTFE fails to detect a certain class of infinite loops #52475

Closed
Closed
CTFE fails to detect a certain class of infinite loops#52475
Labels
A-const-evalArea: Constant evaluation, covers all const contexts (static, const fn, ...)T-compilerRelevant to the compiler team, which will review and decide on the PR/issue.

Description

@ecstatic-morse
ecstatic-morse
opened on Jul 18, 2018

#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.

Activity

  1. brunocodutra commented on Jul 22, 2018

    @brunocodutra
    brunocodutra
    on Jul 22, 2018
    Contributor

    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.

  2. ecstatic-morse commented on Jul 22, 2018

    @ecstatic-morse
    ecstatic-morse
    on Jul 22, 2018
    ContributorAuthor

    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!

  3. bors
    added a commit that references this issue on Sep 6, 2018

    Auto merge of #52626 - brunocodutra:issue-52475, r=oli-obk

    c318691
  4. jonas-schievink
    added
    T-compilerRelevant to the compiler team, which will review and decide on the PR/issue.
    A-const-evalArea: Constant evaluation, covers all const contexts (static, const fn, ...)
    on Jan 27, 2019

  5. jplatte commented on Nov 20, 2019

    @jplatte
    jplatte
    on Nov 20, 2019
    Contributor

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

  6. ecstatic-morse commented on Nov 20, 2019

    @ecstatic-morse
    ecstatic-morse
    on Nov 20, 2019
    ContributorAuthor

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

  7. ecstatic-morse
    closed this as completedon Nov 20, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    A-const-evalArea: Constant evaluation, covers all const contexts (static, const fn, ...)T-compilerRelevant to the compiler team, which will review and decide on the PR/issue.

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions