segfault with small Rust program

[chetmurthy]

I've got a small Rust program, trying to implement a binary search tree. With Rust 0.8, the compiler segfaults. WIth GIT revision 8ea2123, I get a nicer error-message, THEN a segfault. Looks like some sort of infinite stack-recursion.

I'm including the program.

extern mod extra ;
use std::rand;
use std::rand::Rng;
use std::vec ;
use std::str ;
use extra::sort ;

struct bstnode<K, V> {
    k : K,
    v : V,
    l : Option< bstnode<K, V> >,
    r : Option< bstnode<K, V> >
}

impl<K : Clone + Eq + TotalOrd , V : Clone> bstnode<K, V> {
    fn new(k: &K, v: &V) -> bstnode<K,V> {
        bstnode { k: (*k).clone(), v: (*v).clone(), l: None, r: None }
    }
    fn dumbinsert(node: &mut bstnode<K, V>, k : &K, v : &V) {
        if (node.k.cmp(k) == Equal) {
            node.v = v.clone() ;
        }
        else if (k.cmp(&(node.k)) == Less) {
            match node.l {
                None => { node.l = Some(bstnode::new(k, v)) ; }
                Some(ref mut l) => bstnode::dumbinsert(l, k, v)
            }
        }
        else {
            match node.r {
                None => { node.r = Some(bstnode::new(k, v)) ; }
                Some(ref mut r) => bstnode::dumbinsert(r, k, v)
            }
        }
    }
}

fn main() {
    let k = ~"foo";
    let v = ~"bar";
    let mut t = bstnode::new(&k, &v) ;
    let k2 = ~"foo2" ; let v2 = ~"bar2" ;
    bstnode::dumbinsert(&mut t, &k2, &v2) ;
}

[thestinger]

The infinite recursion is a known bug occurring from infinitely sized types #3779, but a stack overflow should not occur.

[thestinger]

cc @alexcrichton

[catamorphism]

Hi @chetmurthy - nice to run into you here (we met at the Berkeley OSQ retreat 10 years ago). The fix is to change Option< bstnode > in your type definition to Option< ~bstnode >. This is actually a known bug (the bug is that the error message is bad) -- as @thestinger said, the bug is #3779 .

@thestinger - #3779 says there's a stack overflow, and it hasn't been closed, so I'm going to treat this as a duplicate.

[thestinger]

I get the task 'rustc has overflowed its stack with both test cases here, so it seems like there's something broken about the stack checks.

[alexcrichton]

I agree that this is a dupe of #3779, the runtime is doing what it should be doing, which is printing that a stack overflow was detected and then aborting.

[thestinger]

@alexcrichton: By something is broken about the stack checks I mean that while it works locally on Linux x86_64, it's not working for the reporter of this bug.

[chetmurthy]

Crap. I should have mentioned my platform. Linux x86 -- 32bit -- Ubuntu 13.04.

[alexcrichton]

I don't believe that we had stack checks in 0.8, I think they're an 0.9-pre thing

[thestinger]

Ah I missed the fact that an error message was printed for them with the git commit. Ignore me! :)