ICE: broken MIR: equate_inputs_and_outputs: NoSolution

[K4rakara]

All of this is yanked out of my work-in-progress bug-for-bug* Misskey Flavored markdown parser, which uses the Parser trait, as defined below, to hopefully allow the compiler to create well-optimized functions via inlining and such.

Where things get messy is in the introduction of the DynParser trait, which uses the same technique used by the lending_iterator and higher-kinded-types crates in order to remove the generic lifetime from its associated type, Output, since lifetime-only generic associated types aren't object-safe (yet?), despite lifetime-only generic parameters being object-safe.

Object-safety is required in this case, because the impl Trait syntax doesn't support cyclic types (for obvious reasons), so boxing and dynamic dispatch is necessary in order to break said cycle.

*as in, it behaves identically to mfm-js, regardless of if that behavior is really "correct" behavior for a markdown parser or not.

Code

Sorry for the rather large reproduction, this was as small as I was able to get it 😓

#![feature(decl_macro)]
#![feature(lazy_cell)]
#![feature(never_type)]

// Stand-in for the `higher-kinded-types` crate:
mod higher_kinded_types {
    use with_lifetime::WithLifetime;
    mod with_lifetime {
        pub trait WithLifetime<'lt> : Send + Sync + Unpin {
            type T;
        }

        impl<'lt, T : ?Sized + WithLifetime<'lt>>
            WithLifetime<'lt>
        for
            crate::higher_kinded_types::__private::HKT<T>
        {
            type T = T::T;
        }
    }

    pub trait HKT : Send + Sync + Unpin + seal::Sealed {
        type __<'lt>;
    }

    mod seal {
        pub trait Sealed {}
        impl<T : ?Sized> Sealed for super::__private::HKT<T> {}
    }

    impl<T : ?Sized> HKT for T
    where
        Self : for<'any> WithLifetime<'any> + seal::Sealed,
    {
        type __<'lt> = <Self as WithLifetime<'lt>>::T;
    }

    mod __private {
        pub use {::core, super::with_lifetime::WithLifetime};
        pub struct HKT<T : ?Sized>(::core::marker::PhantomData<T>, !);
    }

    pub macro HKT(<$lt:lifetime> = $T:ty $(,)?) {
        __private::HKT<dyn for<$lt> WithLifetime<$lt, T = $T>>
    }
}

// Stand-in for the `once-cell` crate.
mod once_cell {
    pub mod unsync {
        pub use std::cell::LazyCell as Lazy;
    }
}

use std::str::CharIndices;

use higher_kinded_types::HKT;

pub trait DynParser {
    type Output: HKT;

    fn dyn_parse<'a>(
        &self,
        input: &'a str,
        chars: CharIndices<'a>,
        state: &mut ParserState,
    ) -> Result<'a, <Self::Output as HKT>::__<'a>>;
}

impl<T> DynParser for T
where
    T: Parser,
{
    type Output = HKT!(<'a> = T::Output<'a>);

    fn dyn_parse<'a>(
        &self,
        input: &'a str,
        chars: CharIndices<'a>,
        state: &mut ParserState,
    ) -> Result<'a, <Self::Output as HKT>::__<'a>> {
        self.parse(input, chars, state)
    }
}

pub trait Parser {
    type Output<'a>;
    
    fn parse<'a>(
        &self,
        input: &'a str,
        chars: CharIndices<'a>,
        state: &mut ParserState,
    ) -> Result<'a, Self::Output<'a>>;
}

impl<Output: HKT> Parser for dyn '_ + DynParser<Output = Output> {
    type Output<'a> = Output::__<'a>;

    fn parse<'a>(
        &self,
        input: &'a str,
        chars: CharIndices<'a>,
        state: &mut ParserState,
    ) -> Result<'a, Self::Output<'a>> {
        self.dyn_parse(input, chars, state)
    }
}

impl<T> Parser for Box<T>
where
    T: ?Sized + Parser,
{
    type Output<'a> = T::Output<'a>;

    fn parse<'a>(
        &self,
        input: &'a str,
        chars: CharIndices<'a>,
        state: &mut ParserState,
    ) -> Result<'a, Self::Output<'a>> {
        <T as Parser>::parse(self, input, chars, state)
    }
}

#[derive(Clone, Debug, Default)]
pub struct ParserState { }

pub type Result<'a, T, E = ()> = ::std::result::Result<(CharIndices<'a>, T), E>;

pub const fn always<T>(value: T) -> impl for<'a> Parser<Output<'a> = T>
where
    T: Clone,
{
    #[derive(Clone)]
    struct Always<T> { value: T }

    impl<T> Parser for Always<T>
    where
        T: Clone,
    {
        type Output<'a> = T;

        fn parse<'a>(
            &self,
            _: &'a str,
            chars: CharIndices<'a>,
            _: &mut ParserState,
        ) -> Result<'a, Self::Output<'a>> {
            Ok((chars, self.value.clone()))
        }
    }

    Always { value }
}

pub const fn lazy<T, F>(init: F) -> impl for<'a> Parser<Output<'a> = T::Output<'a>>
where
    F: FnOnce() -> T,
    T: Parser,
{
    struct Lazy<F, T> { inner: once_cell::unsync::Lazy<T, F> }

    impl<F, T> Parser for Lazy<F, T>
    where
        F: FnOnce() -> T,
        T: Parser,
    {
        type Output<'a> = T::Output<'a>;

        fn parse<'a>(
            &self,
            input: &'a str,
            chars: CharIndices<'a>,
            state: &mut ParserState,
        ) -> Result<'a, Self::Output<'a>> {
            self.inner.parse(input, chars, state)
        }
    }

    Lazy { inner: once_cell::unsync::Lazy::new(init) }
}

pub fn uncycle<'a, T>(parser: T) -> Box<dyn 'a + DynParser<Output = HKT!(<'b> = T::Output<'b>)>>
where
    T: Parser + 'a,
{
    Box::new(parser)
}

/// vvv HERE vvv
pub fn foo() -> impl for<'a> Parser<Output<'a> = ()> {
    lazy(|| uncycle(always(())))
}

fn main() {
    println!("Hello, world!");
}

Meta

rustc --version --verbose:

rustc 1.72.0-nightly (df77afbca 2023-06-12)
binary: rustc
commit-hash: df77afbcaf3365a32066a8ca4a00ae6fc9a69647
commit-date: 2023-06-12
host: x86_64-unknown-linux-gnu
release: 1.72.0-nightly
LLVM version: 16.0.5

Error output

error: internal compiler error: no errors encountered even though `delay_span_bug` issued

error: internal compiler error: broken MIR in DefId(0:99 ~ delay_span_bug_ice[dc5f]::foo::{closure#0}) (bb0[0]): equate_inputs_and_outputs: `std::boxed::Box<dyn DynParser<Output = higher_kinded_types::__private::HKT<dyn for<'b> higher_kinded_types::with_lifetime::WithLifetime<'b, for<'b> T = ()>>>>==std::boxed::Box<dyn DynParser<Output = higher_kinded_types::__private::HKT<dyn for<'b> higher_kinded_types::with_lifetime::WithLifetime<'b, for<'b> T = <impl Parser<Output = ()> as Parser>::Output<'b>>>>>` failed with `NoSolution`
   --> src/main.rs:193:10
    |
193 |     lazy(|| uncycle(always(())))
    |          ^^^^^^^^^^^^^^^^^^^^^^
    |
    = note: delayed at compiler/rustc_borrowck/src/type_check/input_output.rs:133:13

Backtrace

 0: <rustc_errors::HandlerInner>::emit_diagnostic
 1: <rustc_errors::Handler>::delay_span_bug::<rustc_span::span_encoding::Span, alloc::string::String>
 2: rustc_borrowck::type_check::type_check
 3: rustc_borrowck::nll::compute_regions
 4: rustc_borrowck::do_mir_borrowck
 5: rustc_borrowck::mir_borrowck
 6: rustc_query_impl::plumbing::__rust_begin_short_backtrace::<rustc_query_impl::query_impl::mir_borrowck::dynamic_query::{closure#2}::{closure#0}, rustc_middle::query::erase::Erased<[u8; 8]>>
 7: <rustc_query_impl::query_impl::mir_borrowck::dynamic_query::{closure#2} as core::ops::function::FnOnce<(rustc_middle::ty::context::TyCtxt, rustc_span::def_id::LocalDefId)>>::call_once
 8: rustc_query_system::query::plumbing::try_execute_query::<rustc_query_impl::DynamicConfig<rustc_query_system::query::caches::VecCache<rustc_span::def_id::LocalDefId, rustc_middle::query::erase::Erased<[u8; 8]>>, false, false, false>, rustc_query_impl::plumbing::QueryCtxt, true>
 9: rustc_query_impl::query_impl::mir_borrowck::get_query_incr::__rust_end_short_backtrace
10: <rustc_borrowck::type_check::TypeChecker>::prove_closure_bounds
11: <rustc_borrowck::type_check::TypeChecker>::typeck_mir
12: rustc_borrowck::type_check::type_check
13: rustc_borrowck::nll::compute_regions
14: rustc_borrowck::do_mir_borrowck
15: rustc_borrowck::mir_borrowck
16: rustc_query_impl::plumbing::__rust_begin_short_backtrace::<rustc_query_impl::query_impl::mir_borrowck::dynamic_query::{closure#2}::{closure#0}, rustc_middle::query::erase::Erased<[u8; 8]>>
17: <rustc_query_impl::query_impl::mir_borrowck::dynamic_query::{closure#2} as core::ops::function::FnOnce<(rustc_middle::ty::context::TyCtxt, rustc_span::def_id::LocalDefId)>>::call_once
18: rustc_query_system::query::plumbing::try_execute_query::<rustc_query_impl::DynamicConfig<rustc_query_system::query::caches::VecCache<rustc_span::def_id::LocalDefId, rustc_middle::query::erase::Erased<[u8; 8]>>, false, false, false>, rustc_query_impl::plumbing::QueryCtxt, true>
19: rustc_query_impl::query_impl::mir_borrowck::get_query_incr::__rust_end_short_backtrace
20: rustc_hir_analysis::collect::type_of::opaque::find_opaque_ty_constraints_for_rpit
21: rustc_hir_analysis::collect::type_of::type_of
22: rustc_query_impl::plumbing::__rust_begin_short_backtrace::<rustc_query_impl::query_impl::type_of::dynamic_query::{closure#2}::{closure#0}, rustc_middle::query::erase::Erased<[u8; 8]>>
23: <rustc_query_impl::query_impl::type_of::dynamic_query::{closure#2} as core::ops::function::FnOnce<(rustc_middle::ty::context::TyCtxt, rustc_span::def_id::DefId)>>::call_once
24: rustc_query_system::query::plumbing::try_execute_query::<rustc_query_impl::DynamicConfig<rustc_query_system::query::caches::DefaultCache<rustc_span::def_id::DefId, rustc_middle::query::erase::Erased<[u8; 8]>>, false, false, false>, rustc_query_impl::plumbing::QueryCtxt, true>
25: rustc_query_impl::query_impl::type_of::get_query_incr::__rust_end_short_backtrace
26: rustc_middle::query::plumbing::query_get_at::<rustc_query_system::query::caches::DefaultCache<rustc_span::def_id::DefId, rustc_middle::query::erase::Erased<[u8; 8]>>>
27: rustc_hir_analysis::check::check::check_mod_item_types
28: rustc_query_impl::plumbing::__rust_begin_short_backtrace::<rustc_query_impl::query_impl::check_mod_item_types::dynamic_query::{closure#2}::{closure#0}, rustc_middle::query::erase::Erased<[u8; 0]>>
29: <rustc_query_impl::query_impl::check_mod_item_types::dynamic_query::{closure#2} as core::ops::function::FnOnce<(rustc_middle::ty::context::TyCtxt, rustc_span::def_id::LocalDefId)>>::call_once
30: rustc_query_system::query::plumbing::try_execute_query::<rustc_query_impl::DynamicConfig<rustc_query_system::query::caches::VecCache<rustc_span::def_id::LocalDefId, rustc_middle::query::erase::Erased<[u8; 0]>>, false, false, false>, rustc_query_impl::plumbing::QueryCtxt, true>
31: rustc_query_impl::query_impl::check_mod_item_types::get_query_incr::__rust_end_short_backtrace
32: <rustc_middle::hir::map::Map>::for_each_module::<rustc_hir_analysis::check_crate::{closure#6}::{closure#0}>
33: <rustc_session::session::Session>::time::<(), rustc_hir_analysis::check_crate::{closure#6}>
34: rustc_hir_analysis::check_crate
35: rustc_interface::passes::analysis
36: rustc_query_impl::plumbing::__rust_begin_short_backtrace::<rustc_query_impl::query_impl::analysis::dynamic_query::{closure#2}::{closure#0}, rustc_middle::query::erase::Erased<[u8; 1]>>
37: <rustc_query_impl::query_impl::analysis::dynamic_query::{closure#2} as core::ops::function::FnOnce<(rustc_middle::ty::context::TyCtxt, ())>>::call_once
38: rustc_query_system::query::plumbing::try_execute_query::<rustc_query_impl::DynamicConfig<rustc_query_system::query::caches::SingleCache<rustc_middle::query::erase::Erased<[u8; 1]>>, false, false, false>, rustc_query_impl::plumbing::QueryCtxt, true>
39: rustc_query_impl::query_impl::analysis::get_query_incr::__rust_end_short_backtrace
40: <rustc_middle::ty::context::GlobalCtxt>::enter::<rustc_driver_impl::run_compiler::{closure#1}::{closure#2}::{closure#4}, core::result::Result<(), rustc_span::ErrorGuaranteed>>
41: <rustc_interface::interface::Compiler>::enter::<rustc_driver_impl::run_compiler::{closure#1}::{closure#2}, core::result::Result<core::option::Option<rustc_interface::queries::Linker>, rustc_span::ErrorGuaranteed>>
42: <scoped_tls::ScopedKey<rustc_span::SessionGlobals>>::set::<rustc_interface::interface::run_compiler<core::result::Result<(), rustc_span::ErrorGuaranteed>, rustc_driver_impl::run_compiler::{closure#1}>::{closure#0}, core::result::Result<(), rustc_span::ErrorGuaranteed>>
43: std::sys_common::backtrace::__rust_begin_short_backtrace::<rustc_interface::util::run_in_thread_pool_with_globals<rustc_interface::interface::run_compiler<core::result::Result<(), rustc_span::ErrorGuaranteed>, rustc_driver_impl::run_compiler::{closure#1}>::{closure#0}, core::result::Result<(), rustc_span::ErrorGuaranteed>>::{closure#0}::{closure#0}, core::result::Result<(), rustc_span::ErrorGuaranteed>>
44: <<std::thread::Builder>::spawn_unchecked_<rustc_interface::util::run_in_thread_pool_with_globals<rustc_interface::interface::run_compiler<core::result::Result<(), rustc_span::ErrorGuaranteed>, rustc_driver_impl::run_compiler::{closure#1}>::{closure#0}, core::result::Result<(), rustc_span::ErrorGuaranteed>>::{closure#0}::{closure#0}, core::result::Result<(), rustc_span::ErrorGuaranteed>>::{closure#1} as core::ops::function::FnOnce<()>>::call_once::{shim:vtable#0}
45: <alloc::boxed::Box<F,A> as core::ops::function::FnOnce<Args>>::call_once
           at /rustc/df77afbcaf3365a32066a8ca4a00ae6fc9a69647/library/alloc/src/boxed.rs:1985:9
46: <alloc::boxed::Box<F,A> as core::ops::function::FnOnce<Args>>::call_once
           at /rustc/df77afbcaf3365a32066a8ca4a00ae6fc9a69647/library/alloc/src/boxed.rs:1985:9
47: std::sys::unix::thread::Thread::new::thread_start
           at /rustc/df77afbcaf3365a32066a8ca4a00ae6fc9a69647/library/std/src/sys/unix/thread.rs:108:17
48: start_thread
49: __clone3

[Jules-Bertholet]

Reduced:

trait FnRet {
    type Ret;
}
impl<T> FnRet for fn() -> T {
    type Ret = T;
}
type Never = <fn() -> ! as FnRet>::Ret;
mod higher_kinded_types {
    use with_lifetime::WithLifetime;
    pub(crate) mod with_lifetime {
        pub(crate) trait WithLifetime<'lt>: Send + Sync + Unpin {
            type T;
        }
        impl<'lt, T: ?Sized + WithLifetime<'lt>> WithLifetime<'lt>
            for crate::higher_kinded_types::__private::Hkt<T>
        {
            type T = T::T;
        }
    }
    pub(crate) trait Hkt: Send + Sync + Unpin + seal::Sealed {
        type __<'lt>;
    }
    mod seal {
        pub(crate) trait Sealed {}
        impl<T: ?Sized> Sealed for super::__private::Hkt<T> {}
    }
    impl<T: ?Sized> Hkt for T
    where
        Self: for<'any> WithLifetime<'any> + seal::Sealed,
    {
        type __<'lt> = <Self as WithLifetime<'lt>>::T;
    }
    pub(crate) mod __private {
        use crate::Never;
        pub(crate) struct Hkt<T: ?Sized>(::core::marker::PhantomData<T>, Never);
    }
}
use higher_kinded_types::Hkt;
use std::{marker::PhantomData, str::CharIndices};
pub(crate) trait DynParser {
    type Output: Hkt;
    fn dyn_parse<'a>(&self) -> Result<'a, <Self::Output as Hkt>::__<'a>>;
}
impl<T> DynParser for T
where
    T: Parser,
{
    type Output = crate::higher_kinded_types::__private::Hkt<
        dyn for<'a> crate::higher_kinded_types::with_lifetime::WithLifetime<'a, T = T::Output<'a>>,
    >;
    fn dyn_parse<'a>(&self) -> Result<'a, <Self::Output as Hkt>::__<'a>> {
        loop {}
    }
}
pub trait Parser {
    type Output<'a>;
    fn parse<'a>(&self) -> Result<'a, Self::Output<'a>>;
}
impl<Output: Hkt> Parser for dyn '_ + DynParser<Output = Output> {
    type Output<'a> = Output::__<'a>;
    fn parse<'a>(&self) -> Result<'a, Self::Output<'a>> {
        loop {}
    }
}
impl<T> Parser for Box<T>
where
    T: ?Sized + Parser,
{
    type Output<'a> = T::Output<'a>;
    fn parse<'a>(&self) -> Result<'a, Self::Output<'a>> {
        loop {}
    }
}
pub(crate) type Result<'a, T, E = ()> = ::std::result::Result<(CharIndices<'a>, T), E>;
pub(crate) const fn always<T>(value: T) -> impl for<'a> Parser<Output<'a> = T> {
    struct Always<T> {
        value: T,
    }
    impl<T> Parser for Always<T> {
        type Output<'a> = T;
        fn parse<'a>(&self) -> Result<'a, Self::Output<'a>> {
            loop {}
        }
    }
    Always { value }
}
pub(crate) fn lazy<T, F>(_: F) -> impl for<'a> Parser<Output<'a> = T::Output<'a>>
where
    F: FnOnce() -> T,
    T: Parser,
{
    struct Lazy<F, T> {
        inner: PhantomData<T>,
        inner2: PhantomData<F>,
    }
    impl<F, T> Parser for Lazy<F, T>
    where
        F: FnOnce() -> T,
        T: Parser,
    {
        type Output<'a> = T::Output<'a>;
        fn parse<'a>(&self) -> Result<'a, Self::Output<'a>> {
            loop {}
        }
    }
    Lazy {
        inner: PhantomData,
        inner2: PhantomData::<F>,
    }
}
pub(crate) fn uncycle<'a, T>(
    parser: T,
) -> Box<
    dyn 'a
        + DynParser<
            Output = crate::higher_kinded_types::__private::Hkt<
                dyn for<'b> crate::higher_kinded_types::with_lifetime::WithLifetime<
                    'b,
                    T = T::Output<'b>,
                >,
            >,
        >,
>
where
    T: Parser + 'a,
{
    Box::new(parser)
}
/// vvv HERE vvv
pub fn foo() -> impl for<'a> Parser<Output<'a> = ()> {
    lazy(|| uncycle(always(())))
}

[danielhenrymantilla]

Further reduced.

HKTs

use higher_kinded_types::HKT;
mod higher_kinded_types {
    pub(crate) trait HKT {
        type Of<'lt>;
    }

    pub(crate) trait WithLifetime<'lt> {
        type T;
    }

    impl<T: ?Sized + for<'any> WithLifetime<'any>> HKT
        for T
    {
        type Of<'lt> = <T as WithLifetime<'lt>>::T;
    }
    
    macro_rules! __ {(
        <$lt:lifetime> = $T:ty
    ) => (
        dyn for<$lt> crate::higher_kinded_types::WithLifetime<$lt, T = $T>
    )}
    pub(crate) use __ as HKT;
}

Problematic code

trait Trait {
    type Gat<'lt>;
}

impl Trait for () {
    type Gat<'lt> = ();
}

/// Same as `Trait`, but using HKTs rather than GATs
trait HTrait {
    type Hat: ?Sized + HKT;
}

impl<Hat: ?Sized + HKT> Trait for Box<dyn HTrait<Hat = Hat>> {
    type Gat<'lt> = Hat::Of<'lt>;
}

fn existential()
  -> impl for<'a> Trait<Gat<'a> = ()>
{}

fn dyn_hoops<T: Trait>(_: T)
  -> Box<dyn HTrait<Hat = HKT!(<'a> = T::Gat<'a>)>>
//                                    ^^^^^^^^^^ seems to be key to cause the ICE.
{loop {}}

fn bound_on_fn_output<Output: Trait>(
    _: impl FnOnce() -> Output,
)
{}

fn ice() {
    bound_on_fn_output(|| -> _ { // not annotating `-> Box<dyn HTrait<Hat = _>>` seems important as well.
        dyn_hoops(existential())
    });
}

https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=ed91b7f1777c7914fd707cb9f23f3017

[aliemjay]

Further minimized:

trait Trait {
    type Gat<'lt>;
}

impl Trait for () {
    type Gat<'lt> = ();
}

fn dyn_hoops<T: Trait>(_: T) -> *const dyn FnOnce(T::Gat<'_>) {
    loop {}
}

fn main() {
    let _ = || { dyn_hoops(()) };
}