www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Misunderstanding, silly error, or compiler bug?

reply "Peter C. Chapin" <pchapin sover.net> writes:
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);
        }
    }
}
Aug 10 2007
next sibling parent Regan Heath <regan netmail.co.nz> writes:
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
Aug 10 2007
prev sibling next sibling parent reply Daniel919 <Daniel919 web.de> writes:
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
Aug 10 2007
parent reply "Peter C. Chapin" <pchapin sover.net> writes:
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
Aug 10 2007
parent reply "Peter C. Chapin" <pchapin sover.net> writes:
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
Aug 10 2007
parent reply Regan Heath <regan netmail.co.nz> writes:
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
Aug 10 2007
parent "Peter C. Chapin" <pchapin sover.net> writes:
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
Aug 10 2007
prev sibling parent Derek Parnell <derek psych.ward> writes:
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
Aug 11 2007