ICE: assertion failed: bound_list_is_sorted(&bounds.projection_bounds)

[hawkw]

When trying to compile a crate using cargo build, rustc fails with an unexpected panic. Cargo prints this message:

$ cargo build
   Compiling mnemosyne-parser v0.1.0 (file:///Users/hawk/Development/mnemosyne)
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: run with `RUST_BACKTRACE=1` for a backtrace
thread 'rustc' panicked at 'assertion failed: bound_list_is_sorted(&bounds.projection_bounds)', ../src/librustc/middle/ty.rs:4138


Could not compile `mnemosyne-parser`.

I'm not sure which part of my code is causing the panic; so I don't have a code snippet to show. It's a reasonably large project and the error message doesn't reference a line number or source code file.

Here's a gist containing the source for the mnemosyne-parser crate that causes this error. Do note, however, that this code depends on the rest of my project and on @Marwes' library combine-language; the error could be a result of some interaction between my code and some of its dependencies.

Meta

$ rustc --version --verbose
rustc 1.4.0-nightly (f6aac8037 2015-09-06)
binary: rustc
commit-hash: f6aac80375ee8ec63522affc09e0cd5c4f888b44
commit-date: 2015-09-06
host: x86_64-apple-darwin
release: 1.4.0-nightly

$ cargo --version
cargo 0.5.0-nightly (ec59a6c 2015-09-04)

Backtrace:

$ RUST_BACKTRACE=1 cargo build 
   Compiling mnemosyne-parser v0.1.0 (file:///Users/hawk/Development/mnemosyne)
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
thread 'rustc' panicked at 'assertion failed: bound_list_is_sorted(&bounds.projection_bounds)', ../src/librustc/middle/ty.rs:4138

stack backtrace:
   1:        0x10464f820 - sys::backtrace::tracing::imp::write::h8eb606f0676b1c68Sqs
   2:        0x10465663b - panicking::on_panic::h439344cab6a0722eKXw
   3:        0x104618362 - rt::unwind::begin_unwind_inner::h208ecd91d43787c9Msw
   4:        0x1011b4604 - rt::unwind::begin_unwind::h12229588307658574478
   5:        0x1013562f2 - middle::ty::ctxt<'tcx>::mk_trait::hd7c74b8cf28143aaEK9
   6:        0x10129fe51 - metadata::tydecode::TyDecoder<'a, 'tcx>::parse_ty::hbceddcd91e13671d1Pi
   7:        0x10129fe61 - metadata::tydecode::TyDecoder<'a, 'tcx>::parse_ty::hbceddcd91e13671d1Pi
   8:        0x1012a1837 - metadata::tydecode::TyDecoder<'a, 'tcx>::parse_ty::hbceddcd91e13671d1Pi
   9:        0x1012a3947 - metadata::tydecode::TyDecoder<'a, 'tcx>::parse_substs::hf84734e7d241ab27pii
  10:        0x10129f116 - metadata::tydecode::TyDecoder<'a, 'tcx>::parse_ty::hbceddcd91e13671d1Pi
  11:        0x1014ca0b9 - metadata::decoder::get_type::h9bc99763ccabd3297in
  12:        0x1014c9a34 - metadata::decoder::get_adt_def::hf768ac5cc0283af8r4m
  13:        0x1014897a2 - middle::ty::lookup_locally_or_in_crate_store::h6918118975728751697
  14:        0x10129f174 - metadata::tydecode::TyDecoder<'a, 'tcx>::parse_ty::hbceddcd91e13671d1Pi
  15:        0x1014ca0b9 - metadata::decoder::get_type::h9bc99763ccabd3297in
  16:        0x10134a7c2 - middle::ty::ctxt<'tcx>::lookup_item_type::h584b28e10fe974afE2b
  17:        0x100e116fb - collect::ItemCtxt<'a, 'tcx>.AstConv<'tcx>::get_item_type_scheme::h25e83bfb951fdb6eQIy
  18:        0x100dfa38c - astconv::ast_path_to_ty::ha90d8db44138224aUzw
  19:        0x100de7390 - astconv::finish_resolving_def_to_ty::habd24143c000f312Phx
  20:        0x100dafbc6 - astconv::ast_ty_to_ty::hada14901c0f4821eDjx
  21:        0x100dae181 - astconv::ast_ty_to_ty::hada14901c0f4821eDjx
  22:        0x100dfff9b - vec::Vec<T>.FromIterator<T>::from_iter::h5055382868124544705
  23:        0x100dff2f7 - astconv::ty_of_method_or_bare_fn::h2c0878afd874c94eIBx
  24:        0x100dae24e - astconv::ast_ty_to_ty::hada14901c0f4821eDjx
  25:        0x100e22751 - collect::type_scheme_of_item::h0b3a39c213793d31Y9z
  26:        0x100e1a525 - collect::convert_typed_item::h7661c1b9841f26c6IeA
  27:        0x100e070d5 - collect::convert_item::h3f73c8e5e799866828y
  28:        0x100e02046 - collect::collect_item_types::hf613ec7bdae269e2yky
  29:        0x100e4e84d - check_crate::hfc612f2e81e3f3ec1BE
  30:        0x1005be6ea - driver::phase_3_run_analysis_passes::closure.21865
  31:        0x1005a032a - middle::ty::ctxt<'tcx>::create_and_enter::h6505823895643553779
  32:        0x10059bb35 - driver::phase_3_run_analysis_passes::h17336765353748147307
  33:        0x10057c525 - driver::compile_input::h3b979784345acc550ba
  34:        0x1006e1260 - run_compiler::h012c5a96476d1167qqc
  35:        0x1006deb59 - boxed::F.FnBox<A>::call_box::h11466729629495619760
  36:        0x1006de552 - rt::unwind::try::try_fn::h8911238048273806355
  37:        0x1046561f8 - __rust_try
  38:        0x104642400 - rt::unwind::try::inner_try::h1851ddf9ecd93c2fFow
  39:        0x1006de702 - boxed::F.FnBox<A>::call_box::h9417331057773949790
  40:        0x10465556d - sys::thread::Thread::new::thread_start::hc131c4deb753ff20oNv
  41:     0x7fff8ce0f059 - _pthread_body
  42:     0x7fff8ce0efd6 - _pthread_start

Could not compile `mnemosyne-parser`.

Please let me know if there's any additional information I can provide!

[Marwes]

This is probably rooted in combine-language (Marwes/combine-language#4) though I have not been able to figure out what causes it. It has only affected me in the tests (and only some of the tests!).

More issues for this ICE:
#25467
#27222
#24063

[hawkw]

I'm trying to make sense of this, and it seems like a lot of the other issues for this ICE involve associated types. That's interesting, because my code currently doesn't make use of associated types. Either there are additional causes for this ICE, or it's hitting something in combine-language, I suppose?

[arielb1]

Got it. The sort-order of bounds depends on the order of DefIds. The order can change between a parent and child crate.

crate foo:

pub trait Foo { type FooT; }

crate bar:

pub trait Bar { type BarT; }

crate baz:

extern crate foo;
extern crate bar;

pub trait Baz : foo::Foo + bar::Bar {}
pub type BazT = Baz<FooT=(), BarT=u32>;

crate main:

extern crate bar;
extern crate foo; // note different order
extern crate baz;

fn main() {
    let t: Option<Box<baz::BazT>> = None;
}

I guess we should just sort the bounds-list.

[Marwes]

Found what was causing this in combine-language from @arielb1's hint, it wasn't the order of crate declarations though. For the types I implemented Parser for I had declared the associated types in the reverse order of how they were implemented/written in combine. After switching that (and fixing a few compilation errors which this ICE had hidden) I could compile the tests again.

(See Marwes/combine-language@28d791b#diff-b4aea3e418ccdb71239b96952d9cddb6L55),

The project where I used combine-language also had the same reverse order which seems to be the reason it did not run into the ICE. After updating that to use the version of combine-language with the fix it now ceases to compile (and fixing the order there makes it work again). Unforutunately, the next crate which includes the parser crate is now broken by the same error which I haven't figured out the cause for.

[arielb1]

Actually we also depend on Name interning order.

crate aux:

pub trait Trait {
    type FooT;
    type BarT;
}

pub type Object = Option<Box<Trait<FooT=(),BarT=()>>>;

crate main

pub type BarT = ();
pub type FooT = ();

extern crate aux;
fn main() {
    let o: aux::Object = None;
}

[Marwes]

Not getting this ICE any longer from using combine-langauge, thanks for fixing this!

[hawkw]

Yeah, I can confirm, everything works fine on the latest nightly (e629dba0e 2015-09-14).