infinite recursion ICE

[DutchGhost]

The following ICE's on nightly and beta, both on debug and release mode:

fn rec() -> impl Fn() { rec() }

fn main() {
    let f = rec();
}

Stable refuses to compile:

 Compiling playground v0.0.1 (file:///playground)
warning: function cannot return without recurring
 --> src/main.rs:2:1
  |
2 | fn rec() -> impl Fn() { rec() }
  | ^^^^^^^^^^^^^^^^^^^^^   ----- recursive call site
  | |
  | cannot return without recurring
  |
  = note: #[warn(unconditional_recursion)] on by default
  = help: a `loop` may express intention better if this is on purpose

error[E0275]: overflow evaluating the requirement `impl std::ops::Fn<()>`
  |
  = help: consider adding a `#![recursion_limit="128"]` attribute to your crate

error: aborting due to previous error

For more information about this error, try `rustc --explain E0275`.
error: Could not compile `playground`.

To learn more, run the command again with --verbose.

in a way, this is related to #28728 (LLVM optimization bug)

ICE message:

error: internal compiler error: librustc\traits\query\normalize.rs:124: infinite recursion generic_ty: impl std::ops::Fn<()>, substs: [], concrete_ty: impl std::ops::Fn<()>, ty: impl std::ops::Fn<()>

Backtrace:

``` thread 'main' panicked at 'Box', librustc_errors\lib.rs:557:9 stack backtrace: 0: ::drop 1: std::error::> for alloc::boxed::Box<(dyn std::error::Error + core::marker::Send + core::marker::Sync + 'a)>>::from 2: std::panicking::take_hook 3: std::panicking::take_hook 4: ::fmt 5: std::panicking::rust_panic_with_hook 6: ::fmt 7: rustc_errors::Handler::bug 8: as core::clone::Clone>::clone 9: rustc::ty::context::tls::track_diagnostic 10: rustc::ty::context::tls::track_diagnostic 11: rustc::ty::context::tls::track_diagnostic 12: rustc::session::bug_fmt 13: rustc::session::bug_fmt 14: as rustc::ty::fold::TypeFolder<'gcx, 'tcx>>::fold_ty 15: as rustc_traits::lowering::Lower>>>::lower 16: as rustc_traits::lowering::Lower>>>::lower 17: as rustc::ty::context::Lift<'tcx>>::lift_to_tcx 18: rustc_traits::provide 19: as core::fmt::Debug>::fmt 20: rustc::ty::context::tls::track_diagnostic 21: rustc::dep_graph::graph::DepGraph::assert_ignored 22: rustc::ty::context::tls::track_diagnostic 23: rustc::ty::query::plumbing::>::try_print_query_stack 24: rustc::ty::query::plumbing::>::try_print_query_stack 25: as rustc::ty::fold::TypeFolder<'tcx, 'tcx>>::fold_ty 26: as rustc::mir::visit::Visitor<'tcx>>::visit_terminator_kind 27: rustc_mir::monomorphize::collector::collect_crate_mono_items 28: >::visit_local 29: ::fmt 30: rustc_mir::monomorphize::collector::collect_crate_mono_items 31: 32: ::next 33: rustc::ty::context::tls::track_diagnostic 34: rustc::dep_graph::graph::DepGraph::assert_ignored 35: rustc::ty::context::tls::track_diagnostic 36: rustc::ty::query::plumbing::>::try_print_query_stack 37: rustc::ty::query::plumbing::>::try_print_query_stack 38: ::codegen_crate 39: >::visit_item 40: rustc_driver::driver::phase_4_codegen 41: >::visit_impl_item 42: >::visit_impl_item 43: >::visit_item 44: ::fmt 45: rustc_driver::driver::compile_input 46: rustc_driver::run_compiler 47: rustc_driver::target_features::add_configuration 48: >::visit_impl_item 49: _rust_maybe_catch_panic 50: rustc_driver::profile::dump 51: rustc_driver::main 52: 53: std::panicking::update_panic_count 54: _rust_maybe_catch_panic 55: std::rt::lang_start_internal 56: 57: 58: BaseThreadInitThunk 59: RtlUserThreadStart query stack during panic: #0 [normalize_ty_after_erasing_regions] normalizing `ParamEnvAnd { param_env: ParamEnv { caller_bounds: [], reveal: All }, value: impl std::ops::Fn<()> }` #1 [collect_and_partition_mono_items] collect_and_partition_mono_items end of query stack error: aborting due to previous error

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.29.0-nightly (874dec2 2018-07-21) running on x86_64-pc-windows-msvc

note: compiler flags: -C opt-level=3 --crate-type bin

note: some of the compiler flags provided by cargo are hidden

error: Could not compile llvm-opt-ice.

To learn more, run the command again with --verbose.

</details>

[DutchGhost]

A slighty more interesting example might be this:

fn rec() -> *const impl Copy {
    // This should *NEVER* run, but just to trigger the recursion
    if false {
        rec()
        
    } else {

        0u8 as *const _ // cast is needed to make compiler happy about the types
    }
}

fn main() {
    rec();
}

As far as I know, in this example the type that implements Copy is the u8, however it is being cast to...something

[DutchGhost]

With the 2018's async fn, it fails to compile, complaining about recursion limit.

However when inserting an await!(), it still crashes:

#![feature(futures_api)]
#![feature(async_await)]
#![feature(await_macro)]

use std::future::Future;

async fn rec() -> impl Future { await!(rec()) }

fn main() {
    
    rec();
}

[DutchGhost]

as of 1.28, this also ICE's on stable:

Backtrace:

warning: function cannot return without recurring
   --> src\lib.rs:173:5
    |
173 |     pub fn infinite_recursion() -> impl Fn() { infinite_recursion() }
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^   -------------------- recursive call site
    |     |
    |     cannot return without recurring
    |
    = note: #[warn(unconditional_recursion)] on by default
    = help: a `loop` may express intention better if this is on purpose

thread 'main' panicked at 'assertion failed: `(left != right)`
  left: `impl std::ops::Fn<()>`,
 right: `impl std::ops::Fn<()>`: infinite recursion', librustc\traits\query\normalize.rs:130:25
stack backtrace:
   0: <std::sync::mpsc::select::Select as core::fmt::Debug>::fmt
   1: std::stdsimd::arch::detect::os::check_for
   2: std::panicking::take_hook
   3: std::panicking::take_hook
   4: <rustc::ty::query::on_disk_cache::CacheEncoder<'enc, 'a, 'tcx, serialize::opaque::Encoder<'enc>> as serialize::serialize::SpecializedEncoder<rustc::ich::fingerprint::Fingerprint>>::specialized_encode
   5: std::panicking::rust_panic_with_hook
   6: std::panicking::begin_panic_fmt
   7: std::panicking::begin_panic_fmt
   8: <rustc::traits::query::normalize::QueryNormalizer<'cx, 'gcx, 'tcx> as rustc::ty::fold::TypeFolder<'gcx, 'tcx>>::fold_ty
   9: rustc_traits::provide
  10: <rustc_traits::chalk_context::ConstrainedSubst<'a> as rustc::ty::context::Lift<'tcx>>::lift_to_tcx
  11: <rustc::ty::Predicate<'tcx> as rustc_traits::lowering::Lower<rustc::ty::sty::Binder<rustc::traits::DomainGoal<'tcx>>>>::lower
  12: <unknown>
  13: rustc::ty::query::on_disk_cache::__ty_decoder_impl::<impl serialize::serialize::Decoder for rustc::ty::query::on_disk_cache::CacheDecoder<'a, 'tcx, 'x>>::read_str
  14: rustc::ty::context::tls::track_diagnostic
  15: rustc::ty::context::tls::track_diagnostic
  16: rustc::dep_graph::graph::DepGraph::assert_ignored
  17: rustc::ty::context::tls::track_diagnostic
  18: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt<'a, 'gcx, 'tcx>>::try_print_query_stack
  19: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt<'a, 'gcx, 'tcx>>::try_print_query_stack
  20: <rustc::traits::query::normalize_erasing_regions::NormalizeAfterErasingRegionsFolder<'cx, 'tcx> as rustc::ty::fold::TypeFolder<'tcx, 'tcx>>::fold_ty
  21: <rustc_mir::monomorphize::collector::MirNeighborCollector<'a, 'tcx> as rustc::mir::visit::Visitor<'tcx>>::visit_terminator_kind
  22: rustc_mir::monomorphize::collector::collect_crate_mono_items
  23: rustc_mir::monomorphize::collector::collect_crate_mono_items
  24: rustc_mir::monomorphize::collector::collect_crate_mono_items
  25: <rustc_codegen_llvm::time_graph::TimelineId as core::fmt::Debug>::fmt
  26: <rustc_codegen_llvm::base::ValueIter as core::iter::iterator::Iterator>::next
  27: rustc::ty::context::tls::track_diagnostic
  28: rustc::ty::context::tls::track_diagnostic
  29: rustc::dep_graph::graph::DepGraph::assert_ignored
  30: rustc::ty::context::tls::track_diagnostic
  31: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt<'a, 'gcx, 'tcx>>::try_print_query_stack
  32: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt<'a, 'gcx, 'tcx>>::try_print_query_stack
  33: <rustc_codegen_llvm::back::linker::MsvcLinker<'a> as rustc_codegen_llvm::back::linker::Linker>::finalize
  34: rustc::ty::context::tls::track_diagnostic
  35: rustc::ty::context::tls::track_diagnostic
  36: rustc::dep_graph::graph::DepGraph::assert_ignored
  37: rustc::ty::context::tls::track_diagnostic
  38: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt<'a, 'gcx, 'tcx>>::try_print_query_stack
  39: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt<'a, 'gcx, 'tcx>>::try_print_query_stack
  40: <rustc_metadata::encoder::ImplVisitor<'a, 'tcx> as rustc::hir::itemlikevisit::ItemLikeVisitor<'v>>::visit_item
  41: rustc_metadata::cstore_impl::<impl rustc::middle::cstore::CrateStore for rustc_metadata::cstore::CStore>::encode_metadata
  42: rustc::ty::context::TyCtxt::encode_metadata
  43: rustc_codegen_llvm::base::codegen_instance
  44: <rustc_codegen_llvm::time_graph::TimelineId as core::fmt::Debug>::fmt
  45: <rustc_codegen_llvm::base::ValueIter as core::iter::iterator::Iterator>::next
  46: <rustc_codegen_llvm::LlvmCodegenBackend as rustc_codegen_utils::codegen_backend::CodegenBackend>::codegen_crate
  47: rustc_driver::driver::build_output_filenames
  48: rustc_driver::driver::phase_4_codegen
  49: rustc_driver::profile::dump
  50: <rustc_driver::derive_registrar::Finder as rustc::hir::itemlikevisit::ItemLikeVisitor<'v>>::visit_impl_item
  51: <rustc_driver::pretty::IdentifiedAnnotation<'hir> as rustc_driver::pretty::PrinterSupport>::sess
  52: <unknown>
  53: rustc_driver::driver::compile_input
  54: rustc_driver::run_compiler
  55: rustc_driver::target_features::add_configuration
  56: <rustc_driver::pretty::IdentifiedAnnotation<'hir> as rustc_driver::pretty::PrinterSupport>::sess
  57: _rust_maybe_catch_panic
  58: <rustc_driver::derive_registrar::Finder as rustc::hir::itemlikevisit::ItemLikeVisitor<'v>>::visit_item
  59: rustc_driver::main
  60: <unknown>
  61: std::panicking::update_panic_count
  62: _rust_maybe_catch_panic
  63: std::rt::lang_start_internal
  64: <unknown>
  65: <unknown>
  66: BaseThreadInitThunk
  67: RtlUserThreadStart
query stack during panic:
#0 [normalize_ty_after_erasing_regions] normalizing `ParamEnvAnd { param_env: ParamEnv { caller_bounds: [], reveal: All }, value: impl std::ops::Fn<()> }`
#1 [collect_and_partition_mono_items] collect_and_partition_mono_items
#2 [exported_symbols] exported_symbols
end of query stack

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.28.0 (9634041f0 2018-07-30) running on x86_64-pc-windows-msvc

note: compiler flags: -C debuginfo=2 -C incremental --crate-type lib

note: some of the compiler flags provided by cargo are hidden

error: Could not compile `test_bugs`.

To learn more, run the command again with --verbose.

[earthengine]

I can see how this happen - the compiler working hard to find a type to wrap with impl Fn() etc, but it is never given. As there is already a warning issues for the recusing nature, I guess we can default the type to ! in such a detectable case?

[eddyb]

Where's the ICE? All I'm seeing is an error - you have a cyclic dependency in types.

EDIT: oh, the ICE is hidden in the backtrace, it's this (I'll also edit the issue description):

error: internal compiler error: librustc\traits\query\normalize.rs:124: infinite recursion generic_ty: impl std::ops::Fn<()>, substs: [], concrete_ty: impl std::ops::Fn<()>, ty: impl std::ops::Fn<()>

[pnkfelix]

discussed at meeting. P-high. Assigning to @nikomatsakis