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

[frankmcsherry]

I'm getting an ICE (using nightly) when building a not-too-complicated program which depends on a crate I have put together (so, not necessarily much tested in the wild). The backtrace is

   Compiling algorithm_3 v0.0.1 (file:///Users/mcsherry/Projects/algorithm_3)
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)', /Users/rustbuild/src/rust-buildbot/slave/nightly-dist-rustc-mac/build/src/librustc/middle/ty.rs:3086

stack backtrace:
   1:        0x10e549df7 - sys::backtrace::write::hcdd8cf990b8f0f0e1LC
   2:        0x10e577ccd - panicking::on_panic::hbbf8c269bccad920HAI
   3:        0x10e49c15e - rt::unwind::begin_unwind_inner::h2f66a36e4dcc3e43iiI
   4:        0x10b3ddecf - rt::unwind::begin_unwind::h6249491716973373080
   5:        0x10b514217 - middle::ty::mk_trait::h7ab8d7163fc0f3c3rK4
   6:        0x10b82069d - metadata::tydecode::parse_ty_::h2933819655758744267
   7:        0x10b81f6d6 - metadata::tydecode::parse_ty_::h2933819655758744267
   8:        0x10b822089 - metadata::tydecode::parse_substs_::h3504023645670576607
   9:        0x10b81fd24 - metadata::tydecode::parse_ty_::h2933819655758744267
  10:        0x10b822089 - metadata::tydecode::parse_substs_::h3504023645670576607
  11:        0x10b81fd24 - metadata::tydecode::parse_ty_::h2933819655758744267
  12:        0x10b822089 - metadata::tydecode::parse_substs_::h3504023645670576607
  13:        0x10b81fd24 - metadata::tydecode::parse_ty_::h2933819655758744267
  14:        0x10b828890 - metadata::decoder::item_type::hc24aea831f59c6091gj
  15:        0x10b7e025f - metadata::csearch::get_field_type::h004add43e10b4a7c8hm
  16:        0x10b7ca410 - middle::ty::lookup_field_type::h000ec0a6485b2953pb8
  17:        0x10b58fa5d - middle::ty::struct_fields::hb9270926f97b7110ke8
  18:        0x10b786b39 - middle::traits::select::SelectionContext<'cx, 'tcx>::builtin_bound::h7c7cae6071215334ouS
  19:        0x10b77ffec - middle::traits::select::SelectionContext<'cx, 'tcx>::assemble_builtin_bound_candidates::hbf0f8dcb327988a0XqS
  20:        0x10b77c1d2 - middle::traits::select::SelectionContext<'cx, 'tcx>::assemble_candidates::h944e97e99b37718aozR
  21:        0x10b76da96 - middle::traits::select::SelectionContext<'cx, 'tcx>::candidate_from_obligation::h2ca16cbf218693a5adR
  22:        0x10b745657 - middle::traits::select::SelectionContext<'cx, 'tcx>::select::h5b0d39ef774af1bdOQQ
  23:        0x10b7422d0 - middle::traits::fulfill::FulfillmentContext<'tcx>::select::he78b2fc01c1100f5uHO
  24:        0x10b741738 - middle::traits::fulfill::FulfillmentContext<'tcx>::select_where_possible::h976e36d2abe2f2b1IGO
  25:        0x10aade383 - check::vtable::select_fcx_obligations_where_possible::h38ef3ab6bc69a37bd4b
  26:        0x10aadded3 - check::vtable::select_all_fcx_obligations_and_apply_defaults::h2f1bbf5631a3aa6aA0b
  27:        0x10ab9d28d - check::check_bare_fn::heb41f0c17b48e486UQn
  28:        0x10aba31b7 - check::check_method_body::hcba8da26f5a17743Koo
  29:        0x10ab9a71f - check::check_item::h4590801d518d170eF9n
  30:        0x10ac735c6 - check_crate::closure.36302
  31:        0x10ac6da37 - check_crate::hf2047274e19fe4f4bwC
  32:        0x10a9902d5 - driver::phase_3_run_analysis_passes::h7ac32f1d1ca0be7dgGa
  33:        0x10a974a05 - driver::compile_input::haed712778d66caf6Qba
  34:        0x10aa32985 - run_compiler::h2df8296b9f7c362fV4b
  35:        0x10aa30152 - boxed::F.FnBox<A>::call_box::h8968837061369711197
  36:        0x10aa2f647 - rt::unwind::try::try_fn::h5695919628988619761
  37:        0x10e601d28 - rust_try_inner
  38:        0x10e601d15 - rust_try
  39:        0x10aa2f93a - boxed::F.FnBox<A>::call_box::h17367168855684310088
  40:        0x10e5611fd - sys::thread::create::thread_start::he0d7c708bf73803bihH
  41:     0x7fff98cbb267 - _pthread_body
  42:     0x7fff98cbb1e4 - _pthread_start

Could not compile `algorithm_3`.

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

Echidnatron% cargo version
cargo 0.0.1-pre-nightly (84d6d2c 2015-03-31) (built 2015-04-01)

The hunk of code that causes the explosion is:

#![allow(dead_code)]
#![feature(core)]

extern crate timely;
// extern crate core;

use std::rc::Rc;
use std::cell::RefCell;

// use core::marker::PhantomFn;

use timely::progress::Graph;
use timely::example::stream::Stream;

// pub trait Graph : PhantomFn<Self> {}
// pub struct Stream<G: Graph, D> { graph: G, data: D }

pub struct Count<Prefix> {
    prefix: Prefix,
    count:  u32,
    ident:  u32,
}

pub trait PrefixExtender<G: Graph, Prefix, Extension> {
    // using a provided identifier, updates counts to reflect the minimum count of the extender
    fn count(&self, &Stream<G, Count<Prefix>>, u32) -> Stream<G, Count<Prefix>>;

    // using a provided identifier, produce the extensions for matching nominations
    fn propose(&self, &Stream<G, Count<Prefix>>) -> Stream<G, (Prefix, Vec<Extension>)>;

    // restrict a set of proposed extensions to reflect the intersection with the extender
    fn intersect(&self, &Stream<G, (Prefix, Vec<Extension>)>) -> Stream<G, (Prefix, Vec<Extension>)>;
}

impl<G: Graph, P, L: Fn(&P)->u32> PrefixExtender<G, P, u32> for (Rc<RefCell<GraphFragment>>, L) {
    fn count(&self, stream: &Stream<G, Count<P>>, ident: u32) -> Stream<G, Count<P>> {

    }
    fn propose(&self, stream: &Stream<G, Count<P>>) -> Stream<G, (P, Vec<u32>)> {

    }
    fn intersect(&self, stream: &Stream<G, (P, Vec<u32>)>) -> Stream<G, (P, Vec<u32>)> {

    }
}

pub struct GraphFragment {
    nodes: Vec<u32>,
    edges: Vec<u32>,
}

Unfortunately the timely crate is not available on crates.io, because it is still in progress, but it is crashing with the version currently available at https://github.com/frankmcsherry/timely-dataflow, with which I've written several other (non-ICE-ing) programs (so it isn't fundamentally broken, possibly only slightly so :)).

As you can possibly see from the code, I tried an empty Graph trait and Stream struct, but that "works fine" (it complains that I haven't finished my impls yet, without an ICE, and compiles if I just throw some panic!s in there instead). I may try to make a more minimal reproduction, but it probably involves moving parts from one crate into this example, yuck! Perhaps an issue is already obvious from the backtrace.

[frankmcsherry]

Ah, I should add: it is the partially completed impl that lead to the ICE. With that commented out, all is well. With it present (empty function bodies or not) we get an ICE.

[frankmcsherry]

The following is smaller and still causes the ICE, but still leaves the other crate untouched.

extern crate timely;

use timely::progress::Graph;
use timely::example::stream::Stream;

pub trait Test<G: Graph> {
    fn test(&mut self) -> Stream<G, u64>;
}

impl<G: Graph> Test<G> for () {
    fn test(&mut self) -> Stream<G, u64> {

    }
}

The associated snippet in the Cargo.toml is

[dependencies.timely]
version="0.0.4"
path="../timely-dataflow"

in case this reveals something incorrect. It occurs to me that the only non-ICEing programs I've written have been part of the timely build (as examples) and that I haven't actually had a non-ICE program use the crate, so maybe I'm just bad at cargo?

I tried creating a simple crate test with a Graph trait and a Stream struct parameterized by it, and then pulled it in with no problems (it doesn't do anything useful, but it doesn't ICE otherwise). So, probably some sort of issue with complexity in the timely crate, I guess?

[frankmcsherry]

Simplifying further (from a repro point of view) the following Cargo.toml snippet also explodes things without requiring mysterious local files from my laptop:

[dependencies.timely]
git="https://github.com/frankmcsherry/timely-dataflow"

Still in effect on

Echidnatron% cargo --version          
cargo 0.0.1-pre-nightly (3499c8e 2015-04-05) (built 2015-04-05)

[aturon]

cc @nikomatsakis

[frankmcsherry]

I have some more information for this (and a fix from my point of view, so not blocking):

The Stream type needs its second argument to implement a Data trait, and adding the following line fixes things.

use timely::communication::Data;

So, still an ICE, but the root cause is definitely user error (and Rust not being able to find out why u64 satisfies the constraint that Stream requires). I wouldn't have guessed that this was needed, but in either case it makes Rust stop exploding. :)

[frankmcsherry]

I have a fairly minimal change that causes the ICE to happen; the actual crate is quite large and I'm not really sure how to simplify it yet. Note, the ICE happens when you try to build against the crate, not when you build the crate itself.

// ICEs with assertion failed: bound_list_is_sorted(&bounds.projection_bounds)
for index in 0..count_map.len() {
    while let Some((ref time, delta)) = count_map[index].pop() {
        self.frontier[index].update(time, delta);
    }
}

If you swap in the following roughly equivalent lines of code (or, weirdly, change self.frontier[index] to self.frontier[0]), the ICE goes away.

// no ICE; I would have thought "identical" to the above...
for index in 0..count_map.len() {
    while let Some((time, delta)) = count_map[index].pop() {
        self.frontier[index].update(&time, delta);
    }
}

Additionally, if you mark the first version as #[inline(always)] the ICE vanishes.

The issue manifests for me against this commit of timely dataflow, uncommenting lines 25-27 in this notificator.rs, using a program that just does

extern crate timely;

use timely::example::*;
use timely::communication::*;
use timely::progress::nested::subgraph::new_graph;

fn triangles<C: Communicator>(communicator: C) {
    let mut computation = new_graph::<u64, C>(communicator);
    let (mut input, mut stream) = computation.new_input::<u32>();
}

My hunch would be that the crate summary Rust produces has some glitches, and forcing the inline avoids them. If nothing else, this keeps me on my toes with respect to testing to avoid mysterious ICE-based regressions. ;)