ICE: librustc/traits/codegen/mod.rs:68: Encountered error `OutputTypeParameterMismatch`

[earthengine]

I was attempt to apply the trick of this blog post to improve my named closures crate. But I run into this ICE, which is unfortunately in stable.

https://play.rust-lang.org/?gist=22299e701c9bdb472a5fc8fe303b7fa1&version=stable&mode=debug&edition=2015

use std::marker::PhantomData;

trait Lt<'a> {
    type T;
}
struct Id<T>(PhantomData<T>);
impl<'a,T> Lt<'a> for Id<T> {
    type T = T;
}

struct Ref<T>(PhantomData<T>) where T: ?Sized;
impl<'a,T> Lt<'a> for Ref<T>
where T: 'a + Lt<'a> + ?Sized
{
    type T = &'a T;
}
struct Mut<T>(PhantomData<T>) where T: ?Sized;
impl<'a,T> Lt<'a> for Mut<T>
where T: 'a + Lt<'a> + ?Sized
{
    type T = &'a mut T;
}

struct C<I,O>(for<'a> fn(<I as Lt<'a>>::T) -> O) where I: for<'a> Lt<'a>;


fn main() {
    let c = C::<Id<_>,_>(|()| 3);
    c.0(());

}

This is freshly occur so I didn't simplify the code.

[earthengine]

Miminum reproducable:

trait Lt<'a> {
    type T;
}
impl<'a> Lt<'a> for () {
    type T = ();
}

fn main() {
    let _:fn(<() as Lt<'_>>::T) = |()| {};
}

[earthengine]

The error message actually tells us the reason:

...Sorts(ExpectedFound { expected: (), found: <Id<()> as Lt<'_>>::T }))...

So the unification between () and <Id<()> as Lt<'_>>::T failed unexpectedly.

Interestingly, the following works:

fn main() {
    let _: fn(_) = |_:<Id<()> as Lt<'_>>::T| {};
}

but creates another ICE when try to call the function:

trait Lt<'a> {
    type T;
}
struct Id<T>(T);
impl<'a,T> Lt<'a> for Id<T> {
    type T = T;
}

fn main() {
    let f: fn(_) = |_:<Id<()> as Lt<'_>>::T| {};
    f(())
}

where the error message again contains:

...Sorts(ExpectedFound { expected: (), found: <Id<()> as Lt<'_>>::T })...

So, my guess is that somehow this unification passed. However, some work was missing to actually substitute it before generating MIR, and the MIR checker then fails because it didn't follow the same logic to justify the unification.

[earthengine]

The following is working, but the MIR shows a potential reason that seems causes the issue.

trait Lt<'a> {
    type T;
}
struct Id<T>(T);
impl<'a,T> Lt<'a> for Id<T> {
    type T = T;
}

fn main() {
    let _v: <Id<()> as Lt<'_>>::T = ();
    let _f: fn(_) = |_:<Id<()> as Lt<'_>>::T| {};
    //ICE: broken MIR in DefId
    //_f(_v)
}

In generated MIR, it contains the following:

        scope 4 {
            let _2: fn(<Id<()> as Lt>::T); // "_f" in scope 4 at src/main.rs:11:9: 11:11
        }

I think this should be subsituted and change to

        scope 4 {
            let _2: fn(()); // "_f" in scope 4 at src/main.rs:11:9: 11:11
        }

Interestingly, the variable _v has been substituted properly:

    scope 2 {
        let _1: ();                      // "_v" in scope 2 at src/main.rs:10:9: 10:11
    }

Further investigate shows that if we remove the lifetime the problem is resolved. So it seems that the erasure of lifetime wasn't done properly and left behind things that can be substituted?

Issues maybe releated:

#51236 resolved by #52990

[earthengine]

Manually desugaring FnOnce in nightly works, but not with the sugared stable FnOnce:

//Working
let _:&FnOnce<(<() as Lt<'_>>::T,),Output=()> = &|_|{};
//Not working
let _:&FnOnce(<() as Lt<'_>>::T) = &|_|{};

Suggests the problem is in desugaring FnXXX traits.

More example:
1.

let f:&FnOnce(_)= &|_:<() as Lt<'_>>::T|{};

compiled into MIR (which is WRONG):

    scope 2 {
        let _1: &dyn std::ops::FnOnce(<() as Lt>::T); // "f" in scope 2 at src/main.rs:10:9: 10:10
    }

let f:&mut FnMut<(<() as Lt<'_>>::T,),Output=()> = &mut |_|{};

compiled into MIR (CORRECT)

scope 2 {
        let _1: &mut dyn std::ops::FnMut(()); // "f" in scope 2 at src/main.rs:11:9: 11:10
    }

[earthengine]

A more scary ICE: panic with messages that is irrelevant to the code (nightly only with #![unboxed_closures])

fn main() {
    let v:<() as Lt<'_>>::T = ();
    let f:&mut FnMut<(_,),Output=()> = &mut |_:<() as Lt<'_>>::T|{};
    f(v);
}

Error mesage:

thread 'main' panicked at 'cannot access a scoped thread local variable without calling `set` first', /cargo/registry/src/github.com-1ecc6299db9ec823/scoped-tls-0.1.2/src/lib.rs:186:9
stack backtrace:
   0: std::sys::unix::backtrace::tracing::imp::unwind_backtrace
             at libstd/sys/unix/backtrace/tracing/gcc_s.rs:49
   1: std::sys_common::backtrace::print
             at libstd/sys_common/backtrace.rs:71
             at libstd/sys_common/backtrace.rs:59
   2: std::panicking::default_hook::{{closure}}
             at libstd/panicking.rs:211
   3: std::panicking::default_hook
             at libstd/panicking.rs:227
   4: rustc::util::common::panic_hook
   5: std::panicking::rust_panic_with_hook
             at libstd/panicking.rs:479
   6: std::panicking::begin_panic
   7: <scoped_tls::ScopedKey<T>>::with
   8: syntax_pos::<impl syntax_pos::span_encoding::Span>::macro_backtrace
   9: rustc_errors::emitter::EmitterWriter::fix_multispan_in_std_macros
  10: <rustc_errors::emitter::EmitterWriter as rustc_errors::emitter::Emitter>::emit
  11: rustc_errors::Handler::emit_db
  12: <rustc_errors::Handler as core::ops::drop::Drop>::drop
  13: core::ptr::drop_in_place
  14: core::ptr::drop_in_place
  15: core::ptr::drop_in_place
  16: <std::panic::AssertUnwindSafe<F> as core::ops::function::FnOnce<()>>::call_once
  17: __rust_maybe_catch_panic
             at libpanic_unwind/lib.rs:102
  18: rustc_driver::run
  19: rustc_driver::main
  20: std::rt::lang_start::{{closure}}
  21: std::panicking::try::do_call
             at libstd/rt.rs:59
             at libstd/panicking.rs:310
  22: __rust_maybe_catch_panic
             at libpanic_unwind/lib.rs:102
  23: std::rt::lang_start_internal
             at libstd/panicking.rs:289
             at libstd/panic.rs:392
             at libstd/rt.rs:58
  24: main
  25: __libc_start_main
  26: <unknown>
query stack during panic:
end of query stack

I run a local compiler that was compiled from source code, and modifyed the src\librustc_codegen_llvm\back\link.rs file, so function link_library panics right after finish. Then I can see the true error is pretty the same as the "broken MIR" one.

So if I am right, the thread that do MIRI verification was running simultaneously with the LLVM codegen and linker. But MIRI thread issued an error at an unfortunate time point so it crashes the profiler thread. Compare to the HRTB broken MIR issue, I think this is more serious and so I am going to create another issue.

[earthengine]

@alexreg

I need answer of the following question:

When should <() as Lt<'_>>::T being substituted to ()? It seems like, for other kind of types (structs, enums, tuples etc), this substitution is done properly, except that in case of fn or FnXXX this is not.

So I suppose the fix would be in the monorphization. After monorphization the substitution should be done but it didn't, which causes problems in codegen.

[earthengine]

r? @matthewjasper

Found the following code in "/src/librustc/traits/select.rs":

    /// In the case of closure types and fn pointers,
    /// we currently treat the input type parameters on the trait as
    /// outputs. This means that when we have a match we have only
    /// considered the self type, so we have to go back and make sure
    /// to relate the argument types too.  This is kind of wrong, but
    /// since we control the full set of impls, also not that wrong,
    /// and it DOES yield better error messages (since we don't report
    /// errors as if there is no applicable impl, but rather report
    /// errors are about mismatched argument types.
    ///
    /// Here is an example. Imagine we have a closure expression
    /// and we desugared it so that the type of the expression is
    /// `Closure`, and `Closure` expects an int as argument. Then it
    /// is "as if" the compiler generated this impl:
    ///
    ///     impl Fn(int) for Closure { ... }
    ///
    /// Now imagine our obligation is `Fn(usize) for Closure`. So far
    /// we have matched the self-type `Closure`. At this point we'll
    /// compare the `int` to `usize` and generate an error.
    ///
    /// Note that this checking occurs *after* the impl has selected,
    /// because these output type parameters should not affect the
    /// selection of the impl. Therefore, if there is a mismatch, we
    /// report an error to the user.
    fn confirm_poly_trait_refs(&mut self,
                               obligation_cause: ObligationCause<'tcx>,
                               obligation_param_env: ty::ParamEnv<'tcx>,
                               obligation_trait_ref: ty::PolyTraitRef<'tcx>,
                               expected_trait_ref: ty::PolyTraitRef<'tcx>)
                               -> Result<Vec<PredicateObligation<'tcx>>, SelectionError<'tcx>>
    {
        let obligation_trait_ref = obligation_trait_ref.clone();
        self.infcx
            .at(&obligation_cause, obligation_param_env)
            .sup(obligation_trait_ref, expected_trait_ref)
            .map(|InferOk { obligations, .. }| obligations)
            .map_err(|e| OutputTypeParameterMismatch(expected_trait_ref, obligation_trait_ref, e))
    }

seems like the following assumsion

    /// Note that this checking occurs *after* the impl has selected,
    /// because these output type parameters should not affect the
    /// selection of the impl. Therefore, if there is a mismatch, we
    /// report an error to the user.

didn't hold in this case so the error is reported.

So the conclusion:

in "/src/librustc/traits/select.rs",

pub fn select(...
     let candidate = match self.candidate_from_obligation(&stack) {...
     ...
     match self.confirm_candidate(obligation, candidate) {...
     ...
}

the call candidate_from_obligation picks the trait implementation, but it does not do any substitution. So confirm_candidate picks up the mismatch and reports error.

One obvious solution is to ensure we substitute associate types after candidate_from_obligation and before calling confirm_candidate (or at least confirm_poly_trait_refs). Can anyone tell me how?

[earthengine]

Or, is the following (/src/librustc/traits/select.rs)

    fn confirm_fn_pointer_candidate(&mut self, obligation: &TraitObligation<'tcx>)
        -> Result<VtableFnPointerData<'tcx, PredicateObligation<'tcx>>, SelectionError<'tcx>>
    {
        debug!("confirm_fn_pointer_candidate({:?})",
               obligation);

        // ok to skip binder; it is reintroduced below
        let self_ty = self.infcx.shallow_resolve(*obligation.self_ty().skip_binder());
        let sig = self_ty.fn_sig(self.tcx());
        let trait_ref =
            self.tcx().closure_trait_ref_and_return_type(obligation.predicate.def_id(),
                                                         self_ty,
                                                         sig,
                                                         util::TupleArgumentsFlag::Yes)
            .map_bound(|(trait_ref, _)| trait_ref);

        let Normalized { value: trait_ref, obligations } =
            project::normalize_with_depth(self,
                                          obligation.param_env,
                                          obligation.cause.clone(),
                                          obligation.recursion_depth + 1,
                                          &trait_ref);

        self.confirm_poly_trait_refs(obligation.cause.clone(),
                                     obligation.param_env,
                                     obligation.predicate.to_poly_trait_ref(),
                                     trait_ref)?;
        Ok(VtableFnPointerData { fn_ty: self_ty, nested: obligations })
    }

correct? I mean the following assumsion:

// ok to skip binder; it is reintroduced below

given the fact that we have trouble to unify <() as Lt<'_>>::T with ()?

[earthengine]

@nikomatsakis

I see you have been working on #18993 (HRTB). This issue seems to be in the concept "late bound regions" you introduced: <() as Lt<'_>>::T contains a late bound region, but binding is way TOOOO late in this case and actually being never.

Can you please look into this and tell me when it is supposed to be bound?

(I can see the difficulty here: there is a lifetime but was never specified and no clue was given to infer it, making it hard to assume anything on it)

[earthengine]

A slightly adjusted from the minimal reproducable

trait Lt<'a> {
    type T;
}
impl<'a> Lt<'a> for () {
    type T = ();
}

fn main() {
    let _:fn(()) = |_:<() as Lt<'_>>::T| {};
}

gives a normal, but still confusing error message:

error[E0308]: mismatched types
 --> src/main.rs:9:20
  |
9 |     let _:fn(()) = |_:<() as Lt<'_>>::T| {};
  |                    ^^^^^^^^^^^^^^^^^^^^^^^^ expected (), found associated type
  |
  = note: expected type `fn(())`
             found type `[closure@src/main.rs:9:20: 9:44]`

This is consistent in both stable and nightly(2015 or 2018).

Another example:

trait Lt<'a> {
    type T;
}
impl<'a> Lt<'a> for () {
    type T = ();
}

fn test<'a>() {
    let _:fn(<() as Lt<'a>>::T) = |()| {};
}

fn main() {
    test();
}

is working, but will trigger this ICE if remove the 'a lifetime from test and replace Lt<'a> with Lt<'_>.
This suggest the proper solution seems to be treat '_ as if there is a 'a in scope.

[pnkfelix]

assigning self for preliminary investigation

[pnkfelix]

Since this is an ICE and is not using any unstable features (and in fact, reproduces on the stable channel), I have tagged it as P-high for now.

That means we'll be visiting it regularly during the weekly compiler team meeting.

[pnkfelix]

Also: Thank you @earthengine for your patience as well as your copious notes from your own investigations.

My current hypothesis is that normalization is supposed to be doing the substitution mapping <() as Lt<'_>>::T to (), but for some reason is missing the case(s) that you have identified here.

[pnkfelix]

Discussed at T-compiler meeting. Seems to be duplicate of issue #29997. Closing as duplicate.