digitalmars.D - Serious problem with opCmp
I am starting to learn D language. And first thing I can not still understand
is how "opCmp" works indeed?
If we look in documentation we find: define opCmp(S) or opCmp(S*) and it will
works
int opCmp(Object o);
Compare with another Object obj.
Returns:
this < obj < 0
this == obj 0
this > obj > 0
Here is a test code based on D documentation example from "array.html"
/* http://www.digitalmars.com/d/2.0/arrays.html
Using Structs or Unions as the KeyType
Structs or unions can be used as the KeyType. For this to work, the struct or
union definition must define the following member functions:
* hash_t toHash()
* int opEquals(S) or int opEquals(S*)
* int opCmp(S) or int opCmp(S*)
Note that the parameter to opCmp and opEquals can be either the struct or union
type, or a pointer to the struct or untion type.
For example:
*/
struct S
{
int a, b;
hash_t toHash() { return a + b; }
int opEquals(S s)
{
return a == s.a && b == s.b;
}
int opCmp(S* s)
{
if (a == s.a)
return b - s.b;
return a - s.a;
}
}
/*
The implementation may use either opEquals or opCmp or both. Care should be
taken so that the results of opEquals and opCmp are consistent with each other
when the struct/union objects are the same or not.
*/
// define same struct but with opCmp(T) oposite to opCmp(T*)
struct SS
{
int a, b;
hash_t toHash() { return a + b; }
int opEquals(SS s)
{
return a == s.a && b == s.b;
}
int opCmp(SS s)
{
if (a == s.a)
return b - s.b;
return a - s.a;
}
}
void chk(S *a, S *b) {
int z=a.opCmp(b);
char c0=z<0?'<': z>0?'>' : '=';
char cc=a<b?'<': a>b?'>' : '=';
printf("%11d %c %11d (%11d%c0)\n",a.b,cc,b.b,z,c0);
}
void chk(SS a, SS b) {
int z=a.opCmp(b);
char c0=z<0?'<': z>0?'>' : '=';
char cc=a<b?'<': a>b?'>' : '=';
printf("%11d %c %11d (%11d%c0)\n",a.b,cc,b.b,z,c0);
}
// let's test that will be
int main(char[][] args) {
printf("opCmp(T)\n");
SS ss1; ss1.a=0; ss1.b=int.min;
SS ss2; ss2.a=0; ss2.b=int.max;
chk(ss1,ss2);
chk(ss2,ss1);
printf("opCmp(T*) -- why it works this way?\n");
S s1; s1.a=0; s1.b=int.min;
S s2; s2.a=0; s2.b=int.max;
chk(&s1,&s2);
chk(&s2,&s1);
return +1;
}
I am expecting the same behaviour but I was surprized:
This code outputs:
opCmp(T)
-2147483648 > 2147483647 ( 1>0)
2147483647 < -2147483648 ( -1<0)
opCmp(T*) -- why it works this way?
-2147483648 < 2147483647 ( 1>0)
2147483647 > -2147483648 ( -1<0)
First 3 lines show predictable result and I expect this error.
But second 3 lines are unexpected to me. Surprize. They works without error. Is
this a some kind of fixup?
This is well known bug with compare functions:
int cmp_a(int a,int b) {
if (a<b) return -1;
if (b<a) return +1;
return 0;
}
int cmp_b(int a,int b) {
return a-b;
}
function cmp_b holds hidden bug. It caused by arithmetic overflow.
This type of compare function may used only in assembler code where we have
FLAGS of operation done.
But in high level language the only possible code is cmp_a.
If looks on input values plane and separete on 2 areas A and B
<pre>[code]
int.min
+--------0--------+--> a
|0 B : \ A |
| 0 : \ |
| 0 : B \ |
| B 0 : \|
0........0........0 zero
|\ : 0 B |
| \ B : 0 |
| \ : 0 |
| A \ : B 0|
+--------0--------+ int.max
|
v b
[/code]</pre>
Will see that:
function cmp_a will be correct with all acceptable values a and b.
function cmb_b will correct only in area B, and will return oposite result for
area A.
It's extremly strange D shows 2 different behaviours simultaneously.
I think we should not hide this problem by some kind of fixup. It may couse
serious problems in future.
More over it should be removed from examples and changed on predictable code.
Because existing code contains hidden problem and undocumented workaround.
Anyway we must do something with this.
Mar 02 2008
void chk(S *a, S *b) {
int z=a.opCmp(b);
char c0=z<0?'<': z>0?'>' : '=';
char cc=a<b?'<': a>b?'>' : '=';
printf("%11d %c %11d (%11d%c0)\n",a.b,cc,b.b,z,c0);
}
One answer I've found. This code compares addresses of a and b. But I suppose
it will use opCmp(T*) to compare them. But it compares something else.
But more general problem still remain:
If I use opCmp for sort algorithm or for some kind of ordered stucture. Every
thing will works untill I tring to use wide spead values for example hash
codes. Hash values may have any aceptable values. And program will work
incorrect and unpredictable. And will be hard to locate problem and will be
hard explain this problem to everyone how followed the wrong example without
any doubt in its validity.
Here the instance of such inherience
http://team0xf.com:8080/omg?f=1b291ae58034;file=core/Fixed.d;style=gitweb
...
127 int opCmp(fixed32T rhs) {
128 return store - rhs.store;
129 }
...
Or am I panic without reason?
Mar 02 2008
kov_serg <kov_serg freemail.ru>
Bill Baxter Wrote:
In C++ code solution may looks like:
template<class T>int compare(const T& lv,const T& rv) {
return lv<rv?-1: rv<lv?+1: 0;
}
and using it like this
struct S {
int a,b;
static int cmp(const S& lv,const S& rv) {
int t=compare(lv.a,rv.a); if (t) return t;
return compare(lv.b,rv.b);
}
};
any case it will requires from me only operator<
Mar 02 2008
Bill Baxter Wrote: ...But I do think the examples of using opCmp should be changed to be more like "return lv<rv?-1: rv<lv?+1: 0;" as you said (where lv is member of 'this' in the D version).Yes. I've just pointed out the problem exist and I want to eliminate this mistake and prevent other people to copy it into their code. It requires to review and rewrite documentation and codes have been writen by people till now.
Mar 02 2008
Bill Baxter Wrote:If you want to help you can start by editing the comment page for operator overloading: http://www.prowiki.org/wiki4d/wiki.cgi?DocComments/OperatorOverloading (which I added just a week or two ago, trying to be helpful because I couldn't find any examples of how to write an opCmp... but apparently they live in the "array" section of the documentation for some reason.)I'll try to write something soon. But I am only start to lean D language. Here is an test code (opCmp.and.Sort.problem.zip) with output for cmp and sort for v1 and v2. And it shows the strange behaviour not only for opCmp but for buildin sort for dinamic array.
Mar 03 2008
Bill Baxter Wrote: http://www.prowiki.org/wiki4d/wiki.cgi?DocComments/OperatorOverloadingI went ahead and did it. I don't think it requires a novel or anything. Just a few sentences.Sorry, I am asking such silly question. But how to insert image in proWiki?
Mar 03 2008