ICE: OutputTypeParameterMismatch in failing to resolve associated type as tuple.

[rphmeier]

I honestly don't really know how to describe this one.
On stable the uncommented version works as expected, although it yields an ICE on both Beta and Nightly.

On all three release channels, the commented portion of the code fails to resolve
<(PhantomData<A>, PhantomData<B>, PhantomData<C>) as Foo<'a>>::Item as (&'a A, &'a B, &'a C), although they are the same type.

use std::marker::PhantomData;

trait Foo<'a> {
    type Item: 'a;

    fn consume<F>(self, f: F) where F: Fn(Self::Item);
}

fn get<T>() -> T { unimplemented!() }

impl<'a, A: 'a, B: 'a, C: 'a> Foo<'a> for 
(PhantomData<A>, PhantomData<B>, PhantomData<C>) {
    type Item = (&'a A, &'a B, &'a C);

    fn consume<F>(self, f: F) where F: Fn(Self::Item) {
        f(get());
    }
}

#[derive(Clone)]
struct Wrap<T> {
    foo: T,
}

impl<T: for<'a> Foo<'a>> Wrap<T> {
    fn consume<F>(self, f: F) where F: for<'a> Fn(<T as Foo<'a>>::Item) {
        self.foo.consume(f);
    }
}

fn drop3<A, B, C>(_: A, _: B, _: C) {}

fn main() {
    let foo = (PhantomData::<u32>, PhantomData::<f32>, PhantomData::<i32>);
    let wrap = Wrap {
        foo: foo
    };

    wrap.clone().consume(|item| {
        let (a, b, c) = item;
        drop3(a, b, c);
    });

    // uncomment to break
    // wrap.consume(|(a, b, c)| drop3(a, b, c));
}

The expected behavior is that I should be able to call wrap.consume() and match on the argument as a tuple. Note that without the indirection through "Wrap", this works as expected. In my program, the wrapper does more work which cannot be stripped away.
playground: http://is.gd/EYtNFj

[Aatch]

Removing the higher-ranked lifetimes appears to make it work. Interestingly, the MIR typecheck seems to be picking up the error indirectly, as the warnings disappear once that is fixed.

This is still a bug, but changing the Wrap inherent impl to this:

impl<'a, T: Foo<'a>> Wrap<T> {
  fn consume<F>(f: F) where F: Fn(<T as Foo<'a>>::Item) {
    self.foo.consume(f);
  }
}

works.

I assume the reason is that there's no link between the lifetime in the bound on F and the one in the impl signature, my guess is that one part of the compiler is allowing it, but another part is expecting the lifetimes to match up, which is the source of the error.

The error in the case where your destructing in the parameter list is correct, though not very helpful.

[rphmeier]

Could you elaborate on why you believe the error message to be correct? It is my understanding that you can destructure tuples in a function or closure's argument list. This function is accepting a tuple as the argument but is not allowing destructuring within the argument list.

[Aatch]

@rphmeier ah, I was focussed on the error and missed the fact that the first case works on stable. It's not about whether or not you can or can't destructure in an argument list (you can). The error is about a type-mismatch. The use of higher-ranked lifetimes here isn't correct, and causes the types not match. Why the let-destructuring works on stable is beyond me though.

[nikomatsakis]

triage: P-high

[pnkfelix]

This may have been obvious to others, but just to confirm: reproducing the issue described does not require using a 3-tuple. A 1-tuple (A,) does suffice.

However, the behavior changes in a subtle manner if you try to go all the way to removing the tuple entirely (e.g. impl<'a, A: 'a> Foo<'a> for PhantomData<A> and type Item = &'a A;), then on stable, the commented and uncommented code both compile, while the nightly compiler still has a warning about broken MIR.

[pnkfelix]

Nominating; I currently agree with @Aatch's analysis that the original code should (probably) have been rejected by the compiler, but I am not clear on what the appropriate course of action is to take this time.

Namely, we are currently in a situation where we are both emitting a warning from mir typecheck, and then subsequently erroring during trans::collector due to

Encountered error OutputTypeParameterMismatch(Binder(<[closure] as Fn<(<(PhantomData<u32>,) as Foo<'a>>::Item,)>>), Binder(<[closure] as Fn<((&'static u32,),)>>), Sorts(ExpectedFound { expected: (&'static u32,), found: <(PhantomData<u32>,) as Foo<'_>>::Item })) selecting Binder(<[closure] as Fn<((&'static u32,),)>>) during trans

So my question is: Should we either:

1. Figure out how to get the trans::collector to stop erroring in this case, or
2. Treat this scenario as an error in the source program
   • (i.e. either promote the MIR typeck warning to an error, or figure out a way to detect this scenario outside of MIR typeck)

[pnkfelix]

Here is a gist of a somewhat reduced version of the issue:
https://gist.github.com/pnkfelix/74440e047d26c0a410ce5fc74204962c

notably, it is set up so that you can pass --cfg removal_1 and/or --cfg removal_2 to observe the ICE going away.

I said earlier that the original code probably should have been rejected, but the more I look at this, the more uncertain I become about that claim. (To me it comes down to a question of whether the impl's precondition of having a T: for <'a> Foo<'a> means that it is correct to use that T in the context of for <'b> Fn(<T as Foo<'b>>::Item))

[rphmeier]

Thanks for looking into this @pnkfelix -- I'm not particularly knowledgeable about the intricacies of HRTBs, but my intuition when I was writing this code went as like this:
Verify that for all 'a, T implements Foo<'a>
Pass a function which can accept, for all 'a, Foo<'a>::Item.
Call the function using Foo<'a> for some anonymous yet valid 'a.
So far, this seems mostly ok. My understanding of the situation begins to fall apart here. In actuality, the type of T as Foo<'a> item is only altered w.r.t. 'a itself. However, since it could technically be possible for Foo<'static>::Item to be completely different than Foo<'a>::Item rather than the two having some kind of subtyping relationship, this begins to verge into the category of general HKT, which is not supported at all.
In that sense, I think that this should be classified as a bug, although I am not familiar with the compiler implementation details.

[nikomatsakis]

So I looked into this. My feeling is that the underlying problem here is that we do not attempt to normalize under a higher-ranked binder -- this is why (e.g.) stable fails to understand the argument type. This is definitely a pre-existing issue (and there are a number of open issues related to it), but I'm not sure why we started to ICE when we did not before.

[nikomatsakis]

Did more digging. The story is a bit more complex, but I think more readily fixed. It turns out that, in the main typeck pass, we do indeed fail to normalize the type of the parameter in the closure. But, because references to local variables go through the same procedure that computes the types for references to items, we put those same types through the same instantiation procedure, which applies substitutions and then does normalization. In this case, there are no substitutions to apply, but we still do it. And this causes us to normalize the type of the argument on each reference to &u32 (note that while type-checking the body of the closure, the region is not considered bound, but rather free). MIR however doesn't do this extra normalization.

So TL;DR I think we can get this example (at least) working by normalizing the argument types before we store them in the liberated-fn-sig map, or else by normalized the argument types when building MIR. I sort of lean towards the former, just because it's a bit easier to do since there is already a fulfillment context handing around and so forth to handle errors (and it seems more efficient to boot, since we can stop renormalizing on each reference).

[nikomatsakis]

Another reason to normalize the entire fn signature is that I think it will fix this example, which illustrates that the return type is not normalized, though the argument types are:

use std::marker::PhantomData;

trait Foo<'a> {
    type Item;
    fn consume<F>(self, f: F) where F: Fn(Self::Item);
}
struct Consume<A>(PhantomData<A>);

impl<'a, A:'a> Foo<'a> for Consume<A> {
    type Item = &'a A;

    fn consume<F>(self, _f: F) where F: Fn(Self::Item) -> Self::Item {
        if blackbox() {
            _f(any());
        }
    }
}

#[derive(Clone)]
struct Wrap<T> { foo: T }

impl<T: for <'a> Foo<'a>> Wrap<T> {
    fn consume<F>(self, f: F) where F: for <'b> Fn(<T as Foo<'b>>::Item) -> <T as Foo<'b>>::Item {
        self.foo.consume(f);
    }
}

fn main() {
    // This does not (but is only noticed if you call the closure).
    let _wrap = Wrap { foo: Consume(PhantomData::<u32>,) };
    _wrap.consume(|xxxxx| xxxxx);
}

pub static mut FLAG: bool = false;
fn blackbox() -> bool { unsafe { FLAG } }
fn any<T>() -> T { loop { } }

[nikomatsakis]

OK so it appears I was half right. After fixing the problem I mentioned, the warnings about MIR typeck failures go away, but the ICE remains. Also, the variation I posted still doesn't type check. =)

I am now looking in more detail at the ICE from trans.

[pnkfelix]

Note that at this point the current stable (1.9) exhibits the warning and the ICE on the original code posted in the description.

(The gist I posted earlier sidesteps the ICE on the current stable, but still ICE's on the current beta.)

[mitchmindtree]

I have a PR blocked by an ICE that appeared after updating to stable 1.9, and after spending the day attempting to find a workaround it's beginning to look suspiciously similar to this one. Some similarities:

• Appeared in 1.9 and still exists in 1.11.
• Occurs in trans.
• Used to emit Broken MIR warnings until I changed a tuple type alias from using an associated type to the actual type (here). The ICE still remains though.

There are more details along with the backtrace and an example at my original issue here #34027. I'm happy to close it in favour of tracking this issue if you think they fall under the same umbrella.

[nikomatsakis]

So I did some further digging. The current error is definitely the kind of problem I had hope for lazy normalization to fix -- the immediate cause of the ICE is that we wind up solving an obligation where we will be able to normalize, but only once we have "opened" the binder, and once we do that, we are in the inference code and hence we can't normalize (yet!). I'm not sure though why this is only occurring now.

[nikomatsakis]

My branch btw is issue-33364 (which does solve the MIR warning).

[mitchmindtree]

I ended up working around the ICE I was running into, see here for details.

[nikomatsakis]

I tried commenting out the trans collector, but still encountered the same ICE (which is what I expected). This does though suggest the problem is not "specific" to MIR in any particular way (also what I expected). I don't really know how this ever avoided an ICE, tbh, but it really does feel like we should fix via the lazy normalization series of patches, though that's a bit longer term (not sure just how long; @soltanmm has been making some very steady progress and things are getting close).

[pnkfelix]

I did enough bisection to determine that the problem was exposed during PR #32080.

However, many of the individual commits of that PR unfortunately do not build, so the end bisect state looks like this: commit 9723a3b builds and does not expose the problem, commit da66431 builds and does expose it, and git bisect reports:

# only skipped commits left to test
# possible first bad commit: [da66431d06b961efd323f25978964df54d44d3c4] trans: Combine cabi and back::abi into abi.
# possible first bad commit: [cdfad40735745252ad42519df8a6c8ecc3739b58] trans: Condense the fn instantiation logic into callee.
# possible first bad commit: [b05556e06da7c79f9db746728c2557114a94b3b1] trans: Rename MonoId to Instance and start using it in more places.
# possible first bad commit: [d6e72c48dd7dacebe08b44e7ee6ce0f052797f55] trans: Don't store extra copies of intrinsics ID/substs.
# possible first bad commit: [89766a81ef6270595cb8e51f100ed44be4bb9929] trans: use Cell instead of RefCell where it suffices.
# possible first bad commit: [b122d1636ac502dad51c827c16dc95d80d96c838] trans: simplify the declare interface.
# possible first bad commit: [c6d214bdeb1bfc9664ad14085c94bf2cbc5af6ee] trans: Revamp and empower cabi::FnType.
# possible first bad commit: [9221b9118b96d668e2cf5d701b10c0566aa072e9] trans: Pass the Rust type for the closure env in type_of_rust_fn.
# possible first bad commit: [7011e30352583b5965c4a9118ca2c14b8ab24454] trans: Remove the old ExprOrMethodCall.
# possible first bad commit: [55b5a365ef64c6c1a53e348a5a5a5ff1cac1d958] trans: Remove unused return type argument from declare_cfn.
# possible first bad commit: [5af3c12cfc07887b66ed1d8cd9e59e1c77cc8790] trans: Move static item handling to consts.
# possible first bad commit: [c3f856e7e24be568902a38c6a488aee6098f94cc] trans: Remove dead code for variants and structs from get_item_val.
# possible first bad commit: [e0970498c79de1a1381d697b3c27895ef798e288] trans: Move trans_foreign_mod and trans_impl to trans_item.
# possible first bad commit: [16201d45f16845cb5dc2fc0b48bcf34a6715ea14] trans: Get functions and do calls only through Callee.
# possible first bad commit: [062a05dde8c3ea5386fa358d882e1eaca99a9ff0] metadata: Constrain FoundAst::FoundParent to an Item.
# possible first bad commit: [b918e37eb3e393c5a5b0408430e146c0b66ec7ed] metedata: Remove the unnecessary indirection to astencode.

I haven't traced through the different behaves on the two nearest points in the commit series that expose the problem. I might try to do that next, in the hopes of learning why we were avoiding an ICE here previously. (But I also suspect that I should reassign this bug to @nikomatsakis )

[nikomatsakis]

One possible strategy might be to optimize how trans works so that it only fulfills obligations that it HAS to fulfill to resolve in order to solve type variables. This might sidestep the ICE for now because it may never feel the need to resolve this particular obligation. I have to double-check this assertion though, it may not be true. In any case it wouldn't be a fix (that would be lazy norm, I think), but then again my feeling is this code only ever worked through happenstance in any case.

[brson]

@rust-lang/compiler Can someone be assigned to this P-high bug?

[pnkfelix]

triage: P-medium

[nikomatsakis]

OK so -- just an update. I tried a few alternatives here as a possible alternative to @pnkfelix's PR #34573. In particular, I tried:

• implementing eager normalization under binders
  • I have to look a bit more, but this roughly went wrong because some type variables wanted to escape out past the for, not sure if this can be readily solved; but it seems like it'll come up again with lazy norm
• separating out the obligations for closures in a different way as described in this comment -- too much across-the-board refactoring for a hack

[brson]

@pnkfelix Can you clarify why this is P-medium instead of P-high?

[arielb1]

Because it is probably not going to be fixed before lazy normalization.

[brson]

@arielb1 thanks!

[pnkfelix]

Removing I-needs-decision flag; we definitely decided to not land #34573. The plan instead is to implement lazy normalization, which should fix this (or at least make it feasible to fix in a principled way...)

[steveklabnik]

Triage: OP's code still errors with

 error: internal compiler error: librustc\traits\codegen\mod.rs:68: Encountered error `OutputTypeParameterMismatch(Binder(<[closure@src\main.rs:39:26:
42:6] as std::ops::Fn<(<(std::marker::PhantomData<u32>, std::marker::PhantomData<f32>, std::marker::PhantomData<i32>) as Foo<'_>>::Item,)>>), Binder(<
[closure@src\main.rs:39:26: 42:6] as std::ops::Fn<((&u32, &f32, &i32),)>>), Sorts(ExpectedFound { expected: (&u32, &f32, &i32), found: <(std::marker::
PhantomData<u32>, std::marker::PhantomData<f32>, std::marker::PhantomData<i32>) as Foo<'_>>::Item }))` selecting `Binder(<[closure@src\main.rs:39:26:
42:6] as std::ops::Fn<((&u32, &f32, &i32),)>>)` during codegen

thread 'main' panicked at 'Box<Any>', librustc_errors\lib.rs:578:9

you also don't need to uncomment the last line to break it.

[eddyb]

@nikomatsakis is #52812 a duplicate of this?

[eddyb]

This issue itself might be a duplicate of #29997.

[pnkfelix]

since this is blocked on lazy normalization, lets CC #60471

[pnkfelix]

closing as duplicate of #62529, which is where I will try to track future instances of this field of ICE.