Can force segfault with basic features

[pnathan]

Hi,

I am using

$ rustc --version
rustc 0.4 (39c0d35 2012-10-11 21:01:16 -0700)
host: x86_64-apple-darwin

and when I create this program and compile/execute it, I get a segfault (code 11):

extern mod std;
use core::cmp::{Eq, Ord};
use core::option;


// A binary tree node.
enum MaybeNode<T>
{
    Empty,
    // Data, parent, left, right
    Node(@T, @MaybeNode<T>,@MaybeNode<T>, @MaybeNode<T>)
}


impl<T: Ord Eq> MaybeNode<T>: Eq {

    pure fn eq(other: &MaybeNode<T>)-> bool {
        match (self, other) {
          ( Empty, &Empty ) => { true }
          ( Empty, _ )  => { false }
          ( Node(_, _, _, _), &Empty ) => { false }
          ( Node(selfdata, _, selfLeft, selfRight),
           &Node(otherdata, _, otherLeft, otherRight) ) => {

            // We don't check parent equality. If we did, we'd have to
            // recurse into ourselves. Ungood.

            if (selfdata == otherdata) {

                // Note that this kicks out the equality question to
                // T's specification. If that happens to be a
                // MaybeNode, we just recurse and have done with
                // it. :-)
                return (true
                        && (selfLeft == otherLeft)
                        && (selfRight == otherRight))
            }
            else { false }
          }
        }
    }

    pure fn ne(other: &MaybeNode<T>)-> bool {
        ! self.eq(other)
    }
}

fn node_data<T> (node: @MaybeNode<T>) -> Option<@T> {
    match node {
      @Empty => {None}
      @Node(data, _, _, _) => { Some(data) }
    }
}


fn insert<T: Eq Ord> (newdata: @T,
                      node: @MaybeNode<T>) -> @MaybeNode<T> {
    // workaround to use @empty as the default argument
    insert_under(newdata, node, @Empty)
}

fn insert_under<T: Eq Ord> (newdata: @T,
                      node: @MaybeNode<T>,
                      node_parent: @MaybeNode<T>) -> @MaybeNode<T> {
    @match node {
      @Empty => {
        Node(newdata, node_parent, @Empty, @Empty)
      }
      @Node(data, parent, left, right) => {
        if (data == newdata) {
            // a bst doesn't have duplicates
            Node(data, parent, left, right)
        }
        else if ( data > newdata ) {
            Node(data, parent, insert_under(newdata, left, node), right)
        }
        else {
            Node(data, parent, left, insert_under(newdata, right, node))
        }
      }
    }
}



fn cause_segfault() {

    let mut tree = insert(@0, @Empty);
    tree = insert(@-10, tree);
    tree = insert(@10, tree);
    tree = insert(@11, tree);
    tree = insert(@5, tree);

    // After uncommenting this insert, we segfault
    tree = insert(@-5, tree);
/*    tree = insert(@-20, tree);
    tree = insert(@-15, tree);
    tree = insert(@-30, tree);*/
    match node_data(tree) {
      None => { fail(~"Rong") }
      Some(data) => { assert data == @-30 }
    }
    // end segfault block
}

fn main(){
    cause_segfault();
}

[pnathan]

Other poking with the original program managed to get a compiler assert thrown (woo!):

Assertion failed: (box->td != NULL), function free, file /Users/pnathan/external-software/rust/src/rt/boxed_region.cpp, line 63.

Further poking:

If I add let result = match node in insert_under, then afterwards add let _ = fmt!("++\n%?",node); return result, the segfault goes away.

Some quality time with print statements suggests that the error is occurring in the call stack as it derecurses itself up insert_delete.

[brson]

I verified the segfault on x86_64 linux using the commit in your rustc version (good thinking including that!), but I can't reproduce it on the current incoming branch. Can you update and try building again?

[vertexclique]

Yes also I am on macos 10.8. I can't reproduce it.

[pnathan]

Using

rustc 0.5 (07edf90 2012-10-13 05:57:13 -0700)
host: x86_64-apple-darwin

I don't get the segfault.

[brson]

Ok. Considering this fixed. Thanks!