ICE (unwrap of None) after type error with aggressive use of higher-kinded types and variance

[arielb1]

Will minify later

http://is.gd/B0NXIN

pub mod ltseal {
    use std::marker::PhantomData;

    #[derive(Copy)]
    pub struct ContraLifetimeCell<'a, T>(T, PhantomData<*mut FnOnce(&'a ())>);

    #[derive(Copy)]
    pub struct ContraLifetimeSeal<'a>(PhantomData<*mut FnOnce(&'a ())>);

    impl<'s> ContraLifetimeSeal<'s> {
        pub fn seal<'a, T>(&'a self, t: T) -> ContraLifetimeCell<'s, T> {
            ContraLifetimeCell(t, PhantomData)
        }

        pub fn unseal<'a, T>(&'a self, c: ContraLifetimeCell<'s, T>) -> T {
            c.0
        }

        pub fn ref_unseal<'a, 'b, T>(&'a self,
                                     c: &'b ContraLifetimeCell<'s, T>)
                                     -> &'b T {
            &c.0
        }

        pub fn with_seal<T, F: for<'a> FnOnce(ContraLifetimeSeal<'a>) -> T>
                (f: F) -> T {
            f(ContraLifetimeSeal(PhantomData))
        }
    }
}

pub mod deep {
    /* language with only let, variables, addition as PoC */
    use ltseal::ContraLifetimeCell as CLC;

    pub enum Op {
        Add,
    }

    pub enum Expr<'var, VAR> {
        Lit(u32),
        Op(Op, Box<Expr<'var, VAR>>, Box<Expr<'var, VAR>>),
        Var(CLC<'var, VAR>),
        Let(Box<Expr<'var, VAR>>,
            Box<for<'v: 'var> Fn(Expr<'v, VAR>) -> Expr<'v, VAR> + 'var>)
    }

    pub fn add<'var, VAR, E1: ExprLike<'var, VAR>,
                          E2: ExprLike<'var, VAR>>
                          (a: E1, b: E2) -> Expr<'var, VAR> {
        Expr::Op(Op::Add, a.as_expr(), b.as_expr())
    }

    pub fn let_<'var, VAR, E: ExprLike<'var, VAR>,
                           F: for<'v: 'var>
                             Fn(Expr<'v, VAR>) -> Expr<'v, VAR>>
                           (a: E, b: F) -> Expr<'var, VAR> {
        Expr::Let(a.as_expr(), Box::new(b))
    }


    pub trait ExprLike<'var, VAR> {
        fn as_expr(self) -> Box<Expr<'var, VAR>>;
    }

    impl<'var, VAR> ExprLike<'var, VAR> for u32 {
        fn as_expr(self) -> Box<Expr<'var, VAR>> { Box::new(Expr::Lit(self)) }
    }

    impl<'var, VAR> ExprLike<'var, VAR> for Expr<'var, VAR> {
        fn as_expr(self) -> Box<Expr<'var, VAR>> { Box::new(self) }
    }



}

pub use deep::Expr as E;
pub use deep as d;

fn main() {
//let x=5 in let y=3 in let x=x+y in x
    let ex = d::let_(5, |x| {
        d::let_(3, |y| {
            d::let_(d::add(x, y), |x|x
        )})
    });
    drop(ex);
}

Errors:

rror: 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 'called `Option::unwrap()` on a `None` value', /home/rustbuild/src/rust-buildbot/slave/nightly-dist-rustc-linux/build/src/libcore/option.rs:362

[arielb1]

Minified:

pub enum Expr<'var, VAR> {
    Let(Box<Expr<'var, VAR>>,
        Box<for<'v: 'var> Fn(Expr<'v, VAR>) -> Expr<'v, VAR> + 'var>)
}

pub fn add<'var, VAR>
                      (a: Expr<'var, VAR>, b: Expr<'var, VAR>) -> Expr<'var, VAR> {
    loop {}
}

pub fn let_<'var, VAR, F: for<'v: 'var> Fn(Expr<'v, VAR>) -> Expr<'v, VAR>>
                       (a: Expr<'var, VAR>, b: F) -> Expr<'var, VAR> {
    loop {}
}

fn main() {
    let ex =  (|x| {
        let_(add(x,x), |y| {
            let_(add(x, x), |x|x)})});
}

[m-r-r]

Hello,

I think I have the same bug. It happens when I try to compile this piece of code:

use std::collections::HashMap;
use std_test::Bencher;
use std::convert::AsRef;

use SequenceTrie;

macro_rules! u32_benchmark {
    ($map_constructor: expr, $test_id: ident, $num_keys: expr, $key_length: expr) => (
        #[bench]
        fn $test_id(b: &mut Bencher) {
            let mut test_data = Vec::<Vec<u32>>::with_capacity($num_keys);
            let mut map = $map_constructor;
            for i in 0 .. $num_keys {
                let mut key = Vec::<u32>::with_capacity($key_length);
                for j in 0 .. $key_length {
                    key.push(i * j);
                }

                test_data.push(key);
            }

            b.iter(|| {
                for key in &test_data {
                    map.insert(key.as_ref(), 7u32);
                }
            });
        }
    )
}

u32_benchmark! { HashMap::new(), hashmap_k1024_l16, 1024, 16 }
u32_benchmark! { SequenceTrie::new(), trie_k1024_l16, 1024, 16 }

u32_benchmark! { HashMap::new(), hashmap_k64_l128, 64, 128 }
u32_benchmark! { SequenceTrie::new(), trie_k64_l128, 64, 128 }

The version of Rust I'm using is:

rustc 1.0.0-nightly (552080181 2015-03-27) (built 2015-03-28)
binary: rustc
commit-hash: 552080181c58beef03493a110b4a38b20b6b5da5
commit-date: 2015-03-27
build-date: 2015-03-28
host: x86_64-unknown-linux-gnu
release: 1.0.0-nightly

And the compiler output:

$ rustc src/lib.rs --crate-name sequence_trie --crate-type lib -g --test -C metadata=0808f6f1b57c7e83 -C extra-filename=-0808f6f1b57c7e83 --out-dir ./overrides/rust_sequence_trie/target/debug --emit=dep-info,link -L dependency=./overrides/rust_sequence_trie/target/debug -L dependency=./overrides/rust_sequence_trie/target/debug/deps
src/benchmark.rs:23:36: 23:44 error: type annotations required: cannot resolve `collections::vec::Vec<u32> : core::convert::AsRef<_>` [E0283]
src/benchmark.rs:23                     map.insert(key.as_ref(), 7u32);
                                                       ^~~~~~~~
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 'called `Option::unwrap()` on a `None` value', /home/rustbuild/src/rust-buildbot/slave/nightly-dist-rustc-linux/build/src/libcore/option.rs:364

stack backtrace:
   1:     0x7fefb1602319 - sys::backtrace::write::hce2635debe4f9308BBD
   2:     0x7fefb162cc3c - panicking::on_panic::h684283a75db74f52HRJ
   3:     0x7fefb1552553 - rt::unwind::begin_unwind_inner::h5840ea28733d246foxJ
   4:     0x7fefb155293f - rt::unwind::begin_unwind_fmt::hb23a1ee6fe217791ZvJ
   5:     0x7fefb162c857 - rust_begin_unwind
   6:     0x7fefb167ccb4 - panicking::panic_fmt::he15400e7c822c131brB
   7:     0x7fefb1677a44 - panicking::panic::h143696e2c54ef9a4IpB
   8:     0x7fefb022a4f5 - check::regionck::type_must_outlive::h7cf4171efdcb16b9n1e
   9:     0x7fefb0270eab - check::regionck::type_of_node_must_outlive::h3b07938907cd8203Xqe
  10:     0x7fefb026d6c2 - check::regionck::visit_expr::h9151012217c93467RHd
  11:     0x7fefb0269f30 - check::regionck::Rcx<'a, 'tcx>::visit_fn_body::hf123615d02fb21bf4jd
  12:     0x7fefb0301601 - check::check_bare_fn::h0c144619db1f6b78Rnn
  13:     0x7fefb02f9235 - check::check_item::hfc51974e981a39ceCGn
  14:     0x7fefb02ff822 - visit::walk_item::h16090704992959972715
  15:     0x7fefb03db271 - check_crate::closure.36029
  16:     0x7fefb03d5633 - check_crate::h4947b34bb4ea3242HlC
  17:     0x7fefb1c653fd - driver::phase_3_run_analysis_passes::ha98c2f61eed776b9pGa
  18:     0x7fefb1c49325 - driver::compile_input::hc85b3d46d8787bc0Rba
  19:     0x7fefb1d00b25 - run_compiler::hcc9e5d244ab00cc3q2b
  20:     0x7fefb1cfe5da - thunk::F.Invoke<A, R>::invoke::h15610588257015573231
  21:     0x7fefb1cfd829 - rt::unwind::try::try_fn::h11610778690058047059
  22:     0x7fefb16a6eb8 - rust_try_inner
  23:     0x7fefb16a6ea5 - rust_try
  24:     0x7fefb1cfdb87 - thunk::F.Invoke<A, R>::invoke::h2134375656366038107
  25:     0x7fefb1617c21 - sys::thread::create::thread_start::had4589224c69738barI
  26:     0x7fefab43b0a4 - start_thread
  27:     0x7fefb11b8cfc - __clone
  28:                0x0 - <unknown>

I think this is the same bug, because in both cases the panic happens at the same place (function check::regionck::type_must_outlive).

I can get rid of the problem by replacing key.as_ref() by (key as &AsRef<[u32]>).as_ref(): Maybe the problem is occurring because key.as_ref() matches more than one trait ?!

[pmarcelll]

Compiling the minified case produces the following output on rustc 1.2.0-nightly (0250ff9a5 2015-06-17) :

test.rs:1:1: 4:2 error: this type cannot be instantiated without an instance of itself [E0073]
test.rs:1 pub enum Expr<'var, VAR> {
test.rs:2     Let(Box<Expr<'var, VAR>>,
test.rs:3         Box<for<'v: 'var> Fn(Expr<'v, VAR>) -> Expr<'v, VAR> + 'var>)
test.rs:4 }
test.rs:1:1: 4:2 help: run `rustc --explain E0073` to see a detailed explanation
test.rs:1:1: 4:2 help: consider using `Option<Expr<'var, VAR>>`
error: aborting due to previous error

[arielb1]

This no longer ICEs, but still doesn't compile, even after the variance is fixed (Var is right-way variant) and implicator is used instead of the non-working for<'v:'var> syntax. It might be worth checking after @nikomatsakis makes his closure inference reform through.

[nikomatsakis]

On nightly I see an error, not an ICE: http://is.gd/qyUHmM

Marking as needs test.

[mitchmindtree]

I've just hit this error in a personal project - I'm using the 1.2.0 stable release on osx.

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 'called `Option::unwrap()` on a `None` value', ../src/libcore/option.rs:362

stack backtrace:
   1:        0x1075d57b5 - sys::backtrace::write::hf5ea20500b66cd24uns
   2:        0x1075de013 - panicking::on_panic::hbe02cb0d925cad49iGw
   3:        0x107599dd2 - rt::unwind::begin_unwind_inner::h12ba0ba9dffdecc2uow
   4:        0x10759ab29 - rt::unwind::begin_unwind_fmt::hadf0dbf11d345ebfAnw
   5:        0x1075ddb9c - rust_begin_unwind
   6:        0x107631d95 - panicking::panic_fmt::h987a4890059dc6e0H8B
   7:        0x10762a7e1 - panicking::panic::hfd3e1c225039d9cae7B
   8:        0x104510932 - check::regionck::type_must_outlive::h5135304db321371czqe
   9:        0x10453e144 - check::regionck::type_of_node_must_outlive::h82fdc64a63ca862cOQd
  10:        0x10453c6fb - check::regionck::visit_expr::ha7c5f37838a301d2P8c
  11:        0x104539c0b - check::regionck::Rcx<'a, 'tcx>::visit_fn_body::ha3a67b8e2a6eacbbALc
  12:        0x1045390b7 - check::regionck::regionck_fn::ha71fc7731cec857eWDc
  13:        0x1045b1272 - check::check_bare_fn::h88c035244660e365WMn
  14:        0x1045bcce7 - check::check_method_body::h069f1c1260fb3f85Qpo
  15:        0x1045aec47 - check::check_item_body::h9873e3da412bca20ydo
  16:        0x1045af212 - visit::walk_item::h2899112994373683709
  17:        0x1045b0bed - check::check_item_types::h63240bfbe991be87tKn
  18:        0x10466ecd9 - check_crate::h117ec0c1269afe619fD
  19:        0x103eb5d16 - driver::phase_3_run_analysis_passes::closure.15766
  20:        0x103eb4204 - middle::ty::with_ctxt::h14728011725879770170
  21:        0x103eaf00a - driver::phase_3_run_analysis_passes::h16713467199444562124
  22:        0x103e92107 - driver::compile_input::hb6d2be5b0fa2247fTba
  23:        0x103f6e13f - run_compiler::h21d74b88eec3fe3bx7b
  24:        0x103f6b9f3 - boxed::F.FnBox<A>::call_box::h1689969825914258414
  25:        0x103f6b1b7 - rt::unwind::try::try_fn::h11273853850686318048
  26:        0x107668cc8 - rust_try_inner
  27:        0x107668cb5 - rust_try
  28:        0x1075c7c95 - rt::unwind::try::inner_try::h480e3107f6a4b5b9nkw
  29:        0x103f6b3e8 - boxed::F.FnBox<A>::call_box::h888215220722514405
  30:        0x1075dca9d - sys::thread::Thread::new::thread_start::hdb3d925f69c5da4aHIv
  31:     0x7fff96b7d059 - _pthread_body
  32:     0x7fff96b7cfd6 - _pthread_start