Associated types, impl traits ~and closures~; oh my, an ICE.

[WildCryptoFox]

While experimenting with some code I hit this ICE. Interestingly, when running cargo test a second time, it magically works - skipping the error. Also, cargo miri test works fine too.

I'm on a slightly older nightly because some rustup components are missing on the latest. https://play.rust-lang.org confirms the ICE in both its stable and nightly.

#![allow(dead_code)]

trait HasAssocType {
    type Inner;
}

impl HasAssocType for () {
    type Inner = ();
}

trait Tr<I, T>: Fn(I) -> Option<T> {}
impl<I, T, Q: Fn(I) -> Option<T>> Tr<I, T> for Q {}

fn f<T: HasAssocType>() -> impl Tr<T, T::Inner> {
    |_| None
}

fn g<T, Y>(f: impl Tr<T, Y>) -> impl Tr<T, Y> {
    f
}

fn h() {
    g(f())(());
}

~ $ rustc --edition 2018 mir-ice.rs --test
error: internal compiler error: broken MIR in DefId(0:32 ~ mir_ice[317d]::h[0]) (Terminator { source_info: SourceInfo { span: mir-ice.rs:23:5: 23:11, scope: scope[0] }, kind: _3 = const g::<(), <() as HasAssocType>::Inner, impl Tr<(), <() as HasAssocType>::Inner>>(move _4) -> [return: bb3, unwind: bb4] }): call dest mismatch (impl Tr<(), <() as HasAssocType>::Inner> <- impl Tr<(), ()>): NoSolution
  --> mir-ice.rs:22:1
   |
22 | / fn h() {
23 | |     g(f())(());
24 | | }
   | |_^

error: internal compiler error: broken MIR in DefId(0:32 ~ mir_ice[317d]::h[0]) (_2 = &_3): bad assignment (&impl Tr<(), ()> = &impl Tr<(), <() as HasAssocType>::Inner>): NoSolution
  --> mir-ice.rs:23:5
   |
23 |     g(f())(());
   |     ^^^^^^

thread 'rustc' panicked at 'no errors encountered even though `delay_span_bug` issued', src/librustc_errors/lib.rs:362:17
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.37.0-nightly (1d9981f04 2019-06-20) running on x86_64-unknown-linux-gnu

[Centril]

Slight reduction:

#![allow(dead_code)]

trait HasAssocType {
    type Inner;
}

impl HasAssocType for () {
    type Inner = ();
}

trait Tr<I, T>
where
    Self: Fn(I),
{
}

impl<I, T, Q> Tr<I, T> for Q where Q: Fn(I) {}

fn f<T>() -> impl Tr<T, T::Inner>
where
    T: HasAssocType,
{
    |_| ()
}

fn g<T, Y, F>(f: F) -> impl Tr<T, Y>
where
    F: Tr<T, Y>,
{
    f
}

fn h() {
    g(f())(());
}

[nagisa]

Marking P-high. The fact that miri works and a regular compile does not suggests a missing call to normalize() somewhere, which would be fairly easy to fix once it is found.

[WildCryptoFox]

@nagisa Not sure if it is related but I'm writing a parser combinator library (quite similar to nom 5.0), and when I'm not getting the error described above, I'm getting another with one of my test cases.

This requires me to boost the #![type_length_limit = "N"] to as suggested after a few iterations 12,792,521 and the builds are getting unusually slow. A common factor for these issues is that cargo miri test always works. Does the compiler not like combinators?

I'm not ready to release this code yet and I haven't reduced the second issue like the first.

Example depth of these combinators, can obviously get deeper. Along these lines. All functions but the second arguments to map return functions. (snippet of IRCv3 message-tags extension)

// snip
            opt(tuple!(
                tag("@"),
                map(
                    take_while1(none_of(" ".chars())),
                    delimited(
                        tag(";"),
                        tuple!(
                            opt(tag("+")),
                            opt(tuple(host, tag("/"))),
                            take_while(alt2!(letter, number, tag("-"))),
                            opt(tuple(
                                tag("="),
                                take_while(none_of("\0\0xa\0x0d; ".chars()))
                            ))
                        )
                    )
                ),
                space
            )),
// snip

error: reached the type-length limit while instantiating `alt::<&str, std::option::Option<...mnom/src/lib.rs:169:23: 169:40]>`
   --> omnom/src/lib.rs:122:1
    |
122 | / pub fn alt<I, T>(f: impl Omnom<I, T>, g: impl Omnom<I, T>) -> impl Omnom<I, T> {
123 | |     move |i| f(i).or_else(|(i, _)| g(i))
124 | | }
    | |_^
    |
    = note: consider adding a `#![type_length_limit="2683000"]` attribute to your crate

[WildCryptoFox]

HA. Okay this gets more weird. Moving fn h out to a test, everything else works except... Rust suddenly forgets how to make trivial equivalences.

src/lib.rs as above with h stripped into tests/test.rs. cargo test. Due to the requirement of a second compilation unit, I cannot reproduce this one on the playground.

Oh and this one doesn't get to "just work" with miri.

error[E0271]: type mismatch resolving `<() as weird_ice::HasAssocType>::Inner == <() as weird_ice::HasAssocType>::Inner`
 --> tests/test.rs:4:7
  |
4 |     g(f())(());
  |       ^^^ expected (), found associated type
  |
  = note: expected type `()`
             found type `<() as weird_ice::HasAssocType>::Inner`

[WildCryptoFox]

Workaround. Passes the ICE and the type mismatch. Still requires #![type_length_limit="17557366"] in my real tests.

fn f<T: HasAssocType<Inner = Y>, Y>() -> impl Tr<T, Y> { /* .. */ }

[WildCryptoFox]

@nagisa Using cargo rustc --test=irc -- -Zself-profile and summarize summarize irc-*.

Without the workaround. The IRC test builds in 8.54s on the first pass (ICE) (summary) plus 2.8s on the second (no ICE). (summary).

With the workaround. The test builds in 8.49s. (summary).

The first and third both spend 61% of the time (5 seconds) on normalize_ty_after_erasing_regions, followed by collect_and_partition_mono_items with 11-12% of the time (~980ms). The second pass to the first flips these but they're still at the top with 33% (920ms) and 31% (857ms) respectively.

All other tests (much simpler) compile immediately.

Edit: No idea why the first even built in the second pass as it should have failed with the type mismatch issue... shrugs

[pnkfelix]

triage: assigning to self for investigation.

[pnkfelix]

(haven't had a chance yet to look at this.)

[WildCryptoFox]

Thanks @pnkfelix !

[eddyb]

Context: I was helping @WildCryptoFox reduce a different (but similar) ICE from the same project and I started wondering how the reduction in this issue didn't trigger that ICE as well.

Closures appear to be irrelevant, and I've reduced the testcase further to:

trait Trait {
    type Assoc;
}

impl Trait for () {
    type Assoc = ();
}

trait Dummy<T> {}

impl<T, U> Dummy<T> for U {}

fn make<T: Trait>() -> impl Dummy<T::Assoc> {}

fn extract<T>(_: impl Dummy<T>) -> Option<T> {
    None
}

pub fn ice() {
    extract(make::<()>());
}

In particular it appears that extract returning some type that includes T is necessary for reproduction, as it leads to a <() as Trait>::Assoc vs () mismatch in the caller.

However, this is not the end of the story - attempting to reduce the testcase further results in other ICEs, not fixed by #65099.

The smallest such change to the above snippet is:

- impl<T, U> Dummy<T> for U {}
+ impl<T> Dummy<T> for () {}

which results in this (spanless) ICE before and after #65099:

error: internal compiler error: broken MIR in DefId(...::ice[0]) (NoSolution):
could not prove Binder(TraitPredicate(<impl Dummy<<() as Trait>::Assoc> as Dummy<()>>))

That ICE persists through further reduction, and this is my best so far: playground

trait Trait {
    type Assoc;
}

impl Trait for () {
    type Assoc = ();
}

fn unit() -> impl Into<<() as Trait>::Assoc> {}

pub fn ice() {
    Into::into(unit());
}

This looks suspiciously simple, I'm surprised more people haven't hit it yet.

[pnkfelix]

question I might attempt to pose at the T-compiler meeting: In cases like this, is it best to reopen the same bug when you find a variant that tickles a similar ICE? Or are we better off opening a fresh ticket for the variant code?

On the one hand, a proliferation of tickets is not fun.

On the other hand, it becomes pretty difficult to track what an issue number represents when you have to interpret phrases like "fixes PR #NNN" as time-relative (i.e. was that phrase written before or after the bug was reopened with a new variant example)...

[pnkfelix]

I haven't had a chance to look at @eddyb 's new variant yet. I will try to find time to do so, either tomorrow or next week.

[eddyb]

@pnkfelix Part of the reason I feel like this issue should be reopened was because I started from the same codebase @WildCryptoFox got this issue's example from. Had that code been published, even to a temporary git branch, it could've been possible to check before marking this issue as fixed, if the actual code got fixed.

OTOH, even if it's in the same area, I think it's technically a separate ICE, just one that got dropped accidentally from the first reduction, so I wouldn't mind a new issue either way.

(And this time would be good to share the code that is triggering all of these ICEs)

[WildCryptoFox]

@eddyb Oh. The code isn't secret just not ready to publish given the ICE issues and poor compilation performance. https://gitlab.com/sio4/code/omnom

The weird-ice directory contains the first reduction. Safe to ignore that, the main crate is the real code.

[pnkfelix]

Just to clarify: it looks to me like the bug exposed from the original omnom crate (linked above) is exercised by running cargo test, not just cargo build (which runs successfully for me).

(And, as previously mentioned, you currently need to clean or otherwise remove the incremental compilation state, in between calls; otherwise you will fall into #65401

[pnkfelix]

OTOH, even if it's in the same area, I think it's technically a separate ICE, just one that got dropped accidentally from the first reduction, so I wouldn't mind a new issue either way.

I went ahead and filed #65934 to track that bug independently of this one.

[pnkfelix]

marked with E-needs-mcve since it would be good to factor a minimal test out from the test suite of the omnom source crate

[eddyb]

@pnkfelix I don't understand, https://github.com/rust-lang/rust/issues/63154#issuecomment-541592381 is just that. Or do you mean a minimal test while still using the library? (IME, that's also tricky, not all combinators can trigger an ICE)

[pnkfelix]

@eddyb ah sorry, at the time when you posted that comment, the source for omnon was not yet linked here, so I was unaware it had been derived from the test suite for that crate

[eddyb]

Yeah, all the code snippets from @WildCryptoFox (including the original testcase of this issue) are derived from the omnom crate.

[pnkfelix]

Okay so based on @eddyb's feedback it sounds like we have our MCVE

[pnkfelix]

since we have our MCVE (and it seems to approximately match the test I added in PR #65099), and I have independently filed #65934, we can reclose this as fixed.