Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[ICE] with recursive impl trait and Iterator.by_ref() #67552

Closed
tage64 opened this issue Dec 23, 2019 · 3 comments · Fixed by #72540
Closed

[ICE] with recursive impl trait and Iterator.by_ref() #67552

tage64 opened this issue Dec 23, 2019 · 3 comments · Fixed by #72540
Assignees
Labels
A-impl-trait Area: `impl Trait`. Universally / existentially quantified anonymous types with static dispatch. C-bug Category: This is a bug. glacier ICE tracked in rust-lang/glacier. I-ICE Issue: The compiler panicked, giving an Internal Compilation Error (ICE) ❄️ P-high High priority T-compiler Relevant to the compiler team, which will review and decide on the PR/issue.

Comments

@tage64
Copy link

tage64 commented Dec 23, 2019

The compiler panics when compiling the following code.

I tried this code:

main.rs:

fn main() {
    rec(std::iter::empty::<()>(), 0);
}

fn rec(mut it: impl Iterator, n: u32) -> usize {
    if n == 0 {
        it.count()
    } else {
        rec(it.by_ref(), n - 1)
    }
}

I ran:

$ rustc main.rs

Rustc panics:

thread 'rustc' panicked at 'assertion failed: !substs.needs_infer()', src/librustc/traits/specialize/mod.rs:122:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace.

error: internal compiler error: unexpected panic

note: the compiler unexpectedly panicked. this is a bug.

note: we would appreciate a bug report: https://github.com/rust-lang/rust/blob/master/CONTRIBUTING.md#bug-reports

note: rustc 1.39.0 (4560ea788 2019-11-04) running on x86_64-unknown-linux-gnu

Meta

$ rustc --version --verbose
rustc 1.39.0 (4560ea7 2019-11-04)
binary: rustc
commit-hash: 4560ea7
commit-date: 2019-11-04
host: x86_64-unknown-linux-gnu
release: 1.39.0
LLVM version: 9.0

@jonas-schievink
Copy link
Contributor

Reproduces on nightly as well. Playground link.

@jonas-schievink jonas-schievink added A-impl-trait Area: `impl Trait`. Universally / existentially quantified anonymous types with static dispatch. C-bug Category: This is a bug. I-ICE Issue: The compiler panicked, giving an Internal Compilation Error (ICE) ❄️ I-nominated T-compiler Relevant to the compiler team, which will review and decide on the PR/issue. labels Dec 23, 2019
@pnkfelix
Copy link
Member

pnkfelix commented Jan 2, 2020

triage: P-high, removing nomination.

@pnkfelix pnkfelix added P-high High priority and removed I-nominated labels Jan 2, 2020
@Centril
Copy link
Contributor

Centril commented Jan 2, 2020

Reduced:

fn main() {
    rec(Empty);
}

struct Empty;

impl Iterator for Empty {
    type Item = ();
    fn next<'a>(&'a mut self) -> core::option::Option<()> {
        None
    }
}

fn identity<T>(x: T) -> T {
    x
}

fn rec<T>(mut it: T)
where
    T: Iterator,
{
    if () == () {
        T::count(it);
    } else {
        rec(identity(&mut it))
    }
}

@rust-lang-glacier-bot rust-lang-glacier-bot added the glacier ICE tracked in rust-lang/glacier. label Jan 5, 2020
@davidtwco davidtwco self-assigned this May 24, 2020
davidtwco added a commit to davidtwco/rust that referenced this issue May 28, 2020
This commit adjusts the condition used in the recursion limit check of
the monomorphization collector, from `>` to `>=`.

In rust-lang#67552, the test case had infinite indirect recursion, repeating a
handful of functions (from the perspective of the monomorphization
collector): `rec` -> `identity` -> `Iterator::count` -> `Iterator::fold`
-> `Iterator::next` -> `rec`.

During this process, `resolve_associated_item` was invoked for
`Iterator::fold` (during the construction of an `Instance`), and
ICE'd due to substitutions needing inference. However, previous
iterations of this recursion would have called this function for
`Iterator::fold` - and did! - and succeeded in doing so (trivially
checkable from debug logging, `()` is present where `_` is in the substs
of the failing execution).

The expected outcome of this test case would be a recursion limit error
(which is present when the `identity` fn indirection is removed), and
the recursion depth of `rec` is increasing (other functions finish
collecting their neighbours and thus have their recursion depths reset).

When the ICE occurs, the recursion depth of `rec` is 256 (which matches
the recursion limit), which suggests perhaps that a different part of
the compiler is using a `>=` comparison and returning a different result
on this recursion rather than what it returned in every previous
recursion, thus stopping the monomorphization collector from reporting
an error on the next recursion, where `recursion_depth_of_rec > 256`
would have been true.

With grep and some educated guesses, we can determine that
the recursion limit check at line 818 in
`src/librustc_trait_selection/traits/project.rs` is the other check that
is using a different comparison. Modifying either comparison to be `>` or
`>=` respectively will fix the error, but changing the monomorphization
collector produces the nicer error.

Signed-off-by: David Wood <david@davidtw.co>
@bors bors closed this as completed in f96e3e2 May 30, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-impl-trait Area: `impl Trait`. Universally / existentially quantified anonymous types with static dispatch. C-bug Category: This is a bug. glacier ICE tracked in rust-lang/glacier. I-ICE Issue: The compiler panicked, giving an Internal Compilation Error (ICE) ❄️ P-high High priority T-compiler Relevant to the compiler team, which will review and decide on the PR/issue.
Projects
None yet
Development

Successfully merging a pull request may close this issue.

6 participants