I'm new to D and I'm having some trouble with an access violation error that I can't figure out. Either I'm misunderstanding something basic about D's semantics (which is very possible) or perhaps there is a compiler bug.

I'm using dmd v1.020 and I'm trying to write a simple binary tree
template as an exercise. The problem is in the insert method. The full
text of tree.d is below. My complete test program, named tree_driver.d, is:

---> tree_driver.d <---
import tree;

int main( )
{
    Tree!(int) my_tree = new Tree!(int);

    my_tree.insert( 5 );
    my_tree.insert( 3 );
    return( 0 );
}
---> end <---

I compile this with the command

dmd tree_driver.d

There are no errors or warnings during compilation. When I execute this program I get the following output:

A: new_item = 5
B:
A: new_item = 3
C:
D: current.data = 5
Error: Access Violation

The first two trace points (A and B) are when the root node is created. That is handled as a special case. When the three is inserted, there is an access violation between point D and the upcoming point E (see tree.d below). It seems like the critical statement is:

if( new_item < current.data ) current = current.left;

The values of new_item and current.data appear to be correct. Thus the condition is true. The reference current points at the root node (at this time) and thus current.left should be null because of the way the root node was initialized earlier. In that case the while loop should end normally and "E:" should be printed.

Any suggestions as to where the problem might be?

Thanks!

Peter

---> tree.d <---
import std.stdio;

class Tree(T) {
    private {

        // Nodes are handled by reference.
        class Node {
            public:
                Node left;
                Node right;
                Node parent;
                T    data;
        };

        Node  root;
        uint  count;
    }

    this( )
    {
        root  = null;
        count = 0;
    }

    // Adds a copy of the new_item to the tree.
    void insert( T new_item )
    {
        Node  fresh = new Node;
        fresh.data  = new_item;
        fresh.left  = null;
        fresh.right = null;

        writefln("A: new_item = %d", new_item);
        if( count == 0 ) {
            writefln("B:");
            root = fresh;
            fresh.parent = null;
            count = 1;
        }
        else {
            Node current = root;
            Node previous;
            writefln("C:");
            while( current != null ) {
                previous = current;
                writefln("D: current.data = %d", current.data);
                if( new_item < current.data ) current = current.left;
                else if( new_item > current.data ) current = current.right;
                else return;
            }
            writefln("E:");
            fresh.parent = previous;
            if( new_item < previous.data ) previous.left = fresh;
            else if( new_item > previous.data ) previous.right = fresh;
            ++count;
            writefln("F: count = %d", count);
        }
    }
}

Peter C. Chapin wrote:
> I'm new to D and I'm having some trouble with an access violation error
> that I can't figure out. Either I'm misunderstanding something basic
> about D's semantics (which is very possible) or perhaps there is a
> compiler bug.
> 
> I'm using dmd v1.020 and I'm trying to write a simple binary tree
> template as an exercise. The problem is in the insert method. The full
> text of tree.d is below. My complete test program, named tree_driver.d, is:
> 
> ---> tree_driver.d <---
> import tree;
> 
> int main( )
> {
>     Tree!(int) my_tree = new Tree!(int);
> 
>     my_tree.insert( 5 );
>     my_tree.insert( 3 );
>     return( 0 );
> }
> ---> end <---
> 
> I compile this with the command
> 
> dmd tree_driver.d
> 
> There are no errors or warnings during compilation. When I execute this
> program I get the following output:
> 
> A: new_item = 5
> B:
> A: new_item = 3
> C:
> D: current.data = 5
> Error: Access Violation
> 
> The first two trace points (A and B) are when the root node is created.
> That is handled as a special case. When the three is inserted, there is
> an access violation between point D and the upcoming point E (see tree.d
> below). It seems like the critical statement is:
> 
> if( new_item < current.data ) current = current.left;
> 
> The values of new_item and current.data appear to be correct. Thus the
> condition is true. The reference current points at the root node (at
> this time) and thus current.left should be null because of the way the
> root node was initialized earlier. In that case the while loop should
> end normally and "E:" should be printed.
> 
> Any suggestions as to where the problem might be?
> 
> Thanks!
> 
> Peter
> 
> ---> tree.d <---
> import std.stdio;
> 
> class Tree(T) {
>     private {
> 
>         // Nodes are handled by reference.
>         class Node {
>             public:
>                 Node left;
>                 Node right;
>                 Node parent;
>                 T    data;
>         };
> 
>         Node  root;
>         uint  count;
>     }
> 
>     this( )
>     {
>         root  = null;
>         count = 0;
>     }
> 
>     // Adds a copy of the new_item to the tree.
>     void insert( T new_item )
>     {
>         Node  fresh = new Node;
>         fresh.data  = new_item;
>         fresh.left  = null;
>         fresh.right = null;
> 
>         writefln("A: new_item = %d", new_item);
>         if( count == 0 ) {
>             writefln("B:");
>             root = fresh;
>             fresh.parent = null;
>             count = 1;
>         }
>         else {
>             Node current = root;
>             Node previous;
>             writefln("C:");
>             while( current != null ) {
>                 previous = current;
>                 writefln("D: current.data = %d", current.data);
>                 if( new_item < current.data ) current = current.left;
>                 else if( new_item > current.data ) current = current.right;
>                 else return;
>             }
>             writefln("E:");
>             fresh.parent = previous;
>             if( new_item < previous.data ) previous.left = fresh;
>             else if( new_item > previous.data ) previous.right = fresh;
>             ++count;
>             writefln("F: count = %d", count);
>         }
>     }
> }
> 

The problem is the line:
  while( current != null ) {

this is an equality comparrison and therefore calls:

  current.opEquals

and as current is null that's a null dereference.

What you want is:

while( current !is null ) {

which does an 'identity' comparrison on the reference against null.

Regan

Hi, welcome to D ;)

Line 45 in tree.d:
while( current != null ) {

If you use the == operator on objects, the opEqual method
of the class will be called.
Now if your object was not instantiated, this will fail of course.

Instead of this, you have to check whether the reference is null:
while( current !is null ) {


Another hint:
Tree!(int) my_tree = new Tree!(int);
don't know whether you know it, but you could use:
auto my_tree = new Tree!(int);

D supports type inference by using the keyword auto.


Best regards,
Daniel

Daniel919 wrote:

> Hi, welcome to D ;)

Thanks!

> Line 45 in tree.d:
> while( current != null ) {
> 
> If you use the == operator on objects, the opEqual method of the class will be called.

Interesting. Okay, so I'm trying to compare the Node referenced by currrent to null. I didn't define an opEqual for class Node so does that mean the compiler gives me a default one? I guess I would have expected some sort of type mismatch error ('null' isn't a Node, after all).

> Now if your object was not instantiated, this will fail of course.
> 
> Instead of this, you have to check whether the reference is null:
> while( current !is null ) {

Yep. That works. Thanks (to both of you who replied).

> Another hint:
> Tree!(int) my_tree = new Tree!(int);
> don't know whether you know it, but you could use:
> auto my_tree = new Tree!(int);
> 
> D supports type inference by using the keyword auto.

Cool.

Peter

Peter C. Chapin wrote:

> Interesting. Okay, so I'm trying to compare the Node referenced by currrent to null. I didn't define an opEqual for class Node so does that mean the compiler gives me a default one? I guess I would have expected some sort of type mismatch error ('null' isn't a Node, after all).

I think I answered my own question on this. I now understand that == and != do value comparisons. Thus even though the right parameter is a reference, the operator is intended to access the object pointed at by that reference to render its decision. Thus something like

	current == null

is doomed to failure even if 'current' refers to a real object because opEqual is going to want to dereference null.

Peter

Peter C. Chapin wrote:
> I think I answered my own question on this. I now understand that == and
> != do value comparisons. Thus even though the right parameter is a
> reference, the operator is intended to access the object pointed at by
> that reference to render its decision. Thus something like
> 
> 	current == null
> 
> is doomed to failure even if 'current' refers to a real object because
> opEqual is going to want to dereference null.

That particular case depends on the opEquals implementation, eg.

import std.stdio;

class A
{
	int i;
	
	int opEquals(A rhs)
	{
		//return i == rhs.i;
		if (rhs) return i == rhs.i;
		return 0;
	}
}

void main()
{
	A a = new A();
	A b = null;
	
	if (a == b) writefln("equal");
	else writefln("not");
}

If opEquals was implemented as commented it would crash, if it was implemented as written it wouldn't.

I wouldn't rely on opEquals being written in a non-crashing way, after all even if it were the statement:

if (b == a)

will always crash.

Regan

Regan Heath wrote:

> I wouldn't rely on opEquals being written in a non-crashing way, after all even if it were the statement:
> 
> if (b == a)
> 
> will always crash.

Got it!

Thanks,
Peter

On Fri, 10 Aug 2007 09:08:21 -0400, Peter C. Chapin wrote:

> I'm using dmd v1.020 and I'm trying to write a simple binary tree template as an exercise.

I had a go at a different implementation ...

// --- tree.d ----
class Tree(T) {
    private {

        // Nodes are handled by reference.
        class Node {
            private{
                Node left;
                Node right;
                Node parent;
                T    data;
            }
                this(T new_item, Node p = null)
                {
                    data  = new_item;
                    parent = p;
                    ++count;
                }
        };

        Node  root;
        uint  count;
    }

    this( )
    {
        root  = null;
        count = 0;
    }

    uint size()
    {
        return count;
    }

    // Adds a copy of the new_item to the tree.
    void insert( T new_item )
    {
        Node current;

        if (root is null)
        {
            root = new Node(new_item);
            return;
        }

        current = root;
        while( current !is null )
        {
            Node* p;
            if( new_item < current.data )
            {
                p = &current.left;
            }
            else if( new_item > current.data )
            {
                p = &current.right;
            }
            else return; // Duplicates not permitted

            if ((*p) is null)
            {
                (*p) = new Node(new_item, current);
                current = null;
            }
            else
            {
                current = (*p);
            }
        }
    }

    T[] list()
    {
        return list(root);
    }

    T[] list( Node x )
    {
        T[] l;
        if (x !is null)
        {
            l ~= list(x.left);
            l ~= x.data;
            l ~= list(x.right);
        }
        return l;
    }
}

// -- tree_driver.d
import tree;
import std.stdio;
void main( )
{
    auto my_tree = new Tree!(string);
    my_tree.insert( "david" );
    my_tree.insert( "john" );
    my_tree.insert( "colleen" );
    my_tree.insert( "debra" );
    my_tree.insert( "rosie" );
    my_tree.insert( "bevan" );
    my_tree.insert( "eric" );
    my_tree.insert( "roger" );
    my_tree.insert( "anne" );
    my_tree.insert( "michael" );

    writefln("Tree has %s elements", my_tree.size);
    writefln("Tree contains %s", my_tree.list);
}



-- 
Derek Parnell
Melbourne, Australia
skype: derek.j.parnell