digitalmars.D.learn - Misunderstanding, silly error, or compiler bug?
- Peter C. Chapin (94/94) Aug 10 2007 I'm new to D and I'm having some trouble with an access violation error
- Regan Heath (10/126) Aug 10 2007 The problem is the line:
- Daniel919 (15/15) Aug 10 2007 Hi, welcome to D ;)
- Peter C. Chapin (9/25) Aug 10 2007 Interesting. Okay, so I'm trying to compare the Node referenced by
- Peter C. Chapin (9/13) Aug 10 2007 I think I answered my own question on this. I now understand that == and
- Regan Heath (29/38) Aug 10 2007 That particular case depends on the opEquals implementation, eg.
- Peter C. Chapin (4/10) Aug 10 2007 Got it!
- Derek Parnell (104/106) Aug 11 2007 I had a go at a different implementation ...
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
Regan Heath <regan netmail.co.nz>
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
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
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
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
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
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
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 = ¤t.left; } else if( new_item > current.data ) { p = ¤t.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