hang in fulfill due to exponential blowup #110544

lcnr · 2023-04-19T14:34:36Z

trait Trait {}

struct W<T>(T);

impl<T, U> Trait for W<(W<T>, W<U>)>
where
    W<T>: Trait,
    W<U>: Trait,
{}

fn impls<T: Trait>() {}

fn main() {
    impls::<W<_>>()
}

this program results in a hang in both rustc (fulfill) and in r-a (causing my PC to freeze).

if we prove this using a breadth first approach we try to prove O(2^recursion_limit) goals

The text was updated successfully, but these errors were encountered:

…w-response, r=lcnr Clear response values for overflow in new solver When we have an overflow, return a trivial query response. This fixes an ICE with the code described in rust-lang#110544: ```rust trait Trait {} struct W<T>(T); impl<T, U> Trait for W<(W<T>, W)> where W<T>: Trait, W: Trait, {} fn impls<T: Trait>() {} fn main() { impls::<W<_>>() } ``` Where, while proving `W<?0>: Trait`, we overflow but still apply the query response of `?0 = (W<?1>, W<?2>)`. Then while re-processing the query to validate that our evaluation result was stable, we get a different query response that looks like `?1 = (W<?3>, W<?4>), ?2 = (W<?5>, W<?6>)`, and so we trigger the ICE. Also, by returning a trivial query response we also avoid the infinite-loop/OOM behavior of the old solver. r? `@lcnr`

…w-response, r=lcnr Clear response values for overflow in new solver When we have an overflow, return a trivial query response. This fixes an ICE with the code described in rust-lang#110544: ```rust trait Trait {} struct W<T>(T); impl<T, U> Trait for W<(W<T>, W)> where W<T>: Trait, W: Trait, {} fn impls<T: Trait>() {} fn main() { impls::<W<_>>() } ``` Where, while proving `W<?0>: Trait`, we overflow but still apply the query response of `?0 = (W<?1>, W<?2>)`. Then while re-processing the query to validate that our evaluation result was stable, we get a different query response that looks like `?1 = (W<?3>, W<?4>), ?2 = (W<?5>, W<?6>)`, and so we trigger the ICE. Also, by returning a trivial query response we also avoid the infinite-loop/OOM behavior of the old solver. r? ``@lcnr``

…w-response, r=lcnr Clear response values for overflow in new solver When we have an overflow, return a trivial query response. This fixes an ICE with the code described in rust-lang#110544: ```rust trait Trait {} struct W<T>(T); impl<T, U> Trait for W<(W<T>, W)> where W<T>: Trait, W: Trait, {} fn impls<T: Trait>() {} fn main() { impls::<W<_>>() } ``` Where, while proving `W<?0>: Trait`, we overflow but still apply the query response of `?0 = (W<?1>, W<?2>)`. Then while re-processing the query to validate that our evaluation result was stable, we get a different query response that looks like `?1 = (W<?3>, W<?4>), ?2 = (W<?5>, W<?6>)`, and so we trigger the ICE. Also, by returning a trivial query response we also avoid the infinite-loop/OOM behavior of the old solver. r? `@lcnr`

…w-response, r=lcnr Clear response values for overflow in new solver When we have an overflow, return a trivial query response. This fixes an ICE with the code described in rust-lang#110544: ```rust trait Trait {} struct W<T>(T); impl<T, U> Trait for W<(W<T>, W)> where W<T>: Trait, W: Trait, {} fn impls<T: Trait>() {} fn main() { impls::<W<_>>() } ``` Where, while proving `W<?0>: Trait`, we overflow but still apply the query response of `?0 = (W<?1>, W<?2>)`. Then while re-processing the query to validate that our evaluation result was stable, we get a different query response that looks like `?1 = (W<?3>, W<?4>), ?2 = (W<?5>, W<?6>)`, and so we trigger the ICE. Also, by returning a trivial query response we also avoid the infinite-loop/OOM behavior of the old solver. r? ``@lcnr``

lcnr added C-bug Category: This is a bug. I-hang Issue: The compiler never terminates, due to infinite loops, deadlock, livelock, etc. labels Apr 19, 2023

compiler-errors mentioned this issue Apr 20, 2023

Clear response values for overflow in new solver #110614

Merged

compiler-errors self-assigned this Apr 20, 2023

compiler-errors removed their assignment May 10, 2023

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

hang in fulfill due to exponential blowup #110544

hang in fulfill due to exponential blowup #110544

lcnr commented Apr 19, 2023

hang in fulfill due to exponential blowup #110544

hang in fulfill due to exponential blowup #110544

Comments

lcnr commented Apr 19, 2023