thread 'rustc' panicked at 'Box<Any>'

[tubo28]

rustc panicked when I was trying to write RBST (a kind of balanced binary search tree).

I tried this code:

#[derive(Clone)]
struct Node {
    val: i32,
    size: usize,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>
}

impl Node {
    pub fn show(&self, indent: usize) {
        println!("{}", self.val);
        if self.left.is_some() {
            self.left.as_ref().unwrap().show(indent + 1);
        }
        for _ in 0..indent { print!(" "); }
        if self.right.is_some() {
            self.right.as_ref().unwrap().show(indent + 1);
        }
    }

    fn singleton(val: i32) -> Node {
        Node {
            val: val,
            size: 1,
            left: None,
            right: None,
        }
    }
}

struct RBST {
    root: Option<Box<Node>>,
}

fn rand() -> usize {
    10000 // omitted
}

impl RBST {
    pub fn insert(&mut self, n: Option<Box<Node>>, new_val: i32)
                  -> Option<Box<Node>> {
        let (left, right) = RBST::split(n, new_val);
        let n = RBST::merge(left, Some(Box::new(Node::singleton(new_val))));
        RBST::merge(n, right)
    }

    fn merge(left: Option<Box<Node>>, right: Option<Box<Node>>)
                 -> Option<Box<Node>>
    {
        match (&left, &right) {
            (&None, &None) => None,
            (&None, &Some(ref mut r)) => Some(*r),
            (&Some(ref mut l), &None) => Some(*l),
            _ => {
                let mut left = left.unwrap().clone();
                let mut right = right.unwrap().clone();
                if rand() % (left.size + right.size) < left.size {
                    let new_right = RBST::merge(left.right.clone(), Some(right));
                    left.right = new_right;
                    Some(left)
                } else {
                    right.left = RBST::merge(Some(left), right.left.clone());
                    Some(right)
                }
            }
        }
    }

    fn split(n: Option<Box<Node>>, val: i32)
             -> (Option<Box<Node>>, Option<Box<Node>>)
    {
        (None, None) // omitted
    }
}

fn main() {}

I expected to see this happen: rustc reports syntax errors

Instead, this happened: it panicked

Meta

rustc --version --verbose:

rustc 1.18.0-nightly (5309a3e31 2017-04-03)
binary: rustc
commit-hash: 5309a3e31d88def1f3ea966162ed4f81f161d500
commit-date: 2017-04-03
host: x86_64-unknown-linux-gnu
release: 1.18.0-nightly
LLVM version: 3.9

Backtrace:

error: internal compiler error: /checkout/src/librustc/middle/mem_categorization.rs:208: interior cmt {rvalue(ReScope(CodeExtent(208/Misc(NodeId(429)))), ReScope(CodeExtent(208/Misc(NodeId(429))))) id:138 m:McDeclared ty:(&std::option::Option<std::boxed::Box<Node>>, &std::option::Option<std::boxed::Box<Node>>)} is not an ADT

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 'Box<Any>', /checkout/src/librustc_errors/lib.rs:416
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
stack backtrace:
   0: rustc_errors::Handler::bug
   1: rustc::session::opt_span_bug_fmt::{{closure}}
   2: rustc::session::opt_span_bug_fmt
   3: rustc::session::bug_fmt
   4: rustc::middle::mem_categorization::cmt_::immutability_blame
   5: rustc::middle::mem_categorization::cmt_::immutability_blame
   6: rustc::middle::mem_categorization::cmt_::immutability_blame
   7: rustc_borrowck::borrowck::BorrowckCtxt::report
   8: rustc_borrowck::borrowck::gather_loans::check_mutability
   9: <rustc_borrowck::borrowck::gather_loans::GatherLoanCtxt<'a, 'tcx> as rustc::middle::expr_use_visitor::Delegate<'tcx>>::borrow
  10: rustc::middle::mem_categorization::MemCategorizationContext::cat_pattern_
  11: rustc::middle::mem_categorization::MemCategorizationContext::cat_pattern_
  12: rustc::middle::mem_categorization::MemCategorizationContext::cat_pattern_
  13: rustc::middle::mem_categorization::MemCategorizationContext::cat_pattern_
  14: rustc::middle::expr_use_visitor::ExprUseVisitor::walk_pat
  15: rustc::middle::expr_use_visitor::ExprUseVisitor::walk_expr
  16: rustc::middle::expr_use_visitor::ExprUseVisitor::consume_expr
  17: rustc::middle::expr_use_visitor::ExprUseVisitor::walk_expr
  18: rustc::middle::expr_use_visitor::ExprUseVisitor::consume_body
  19: rustc_borrowck::borrowck::build_borrowck_dataflow_data
  20: rustc_borrowck::borrowck::check_crate
  21: rustc_driver::driver::phase_3_run_analysis_passes::{{closure}}
  22: rustc::ty::context::TyCtxt::create_and_enter
  23: rustc_driver::driver::phase_3_run_analysis_passes
  24: rustc_driver::driver::compile_input
  25: rustc_driver::run_compiler
  26: std::panicking::try::do_call
  27: __rust_maybe_catch_panic
             at /checkout/src/libpanic_unwind/lib.rs:98
  28: <F as alloc::boxed::FnBox<A>>::call_box
  29: std::sys::imp::thread::Thread::new::thread_start
             at /checkout/src/liballoc/boxed.rs:650
             at /checkout/src/libstd/sys_common/thread.rs:21
             at /checkout/src/libstd/sys/unix/thread.rs:84
  30: start_thread
  31: clone

[TimNN]

Produces an (non-ice) error on stable / beta.

Minimised:

struct Node;

struct RBST {
    root: Option<Node>,
}

impl RBST {
    fn merge(right: Option<Node>) -> Option<Node> {
        match (&right,) {
            (&Some(ref mut r),) => Some(*r),
            _ => loop {}
        }
    }
}

fn main() {}