http://d.puremagic.com/issues/show_bug.cgi?id=323

           Summary: Error: need opCmp for class Bar
           Product: D
           Version: unspecified
          Platform: PC
        OS/Version: Linux
            Status: NEW
          Severity: normal
          Priority: P2
         Component: DMD
        AssignedTo: bugzilla@digitalmars.com
        ReportedBy: someanon@yahoo.com


I think this use to work; now on Linux dmd.166, it reports:

Error: need opCmp for class Bar

============================================
template Valuable(T) {
protected:
  float m_value = 0.0;

public:
  float value()  {return m_value;}
  void  value(float v)  {m_value=v;}
  int opCmp(T other) {
    int r;

    if      (value < other.value)  {r = -1;}
    else if (value > other.value)  {r =  1;}

    return r;
  }
}

class Foo {
}

class Bar : Foo {
  mixin  Valuable!(Bar);  // defined opCmp to compare Bar

public:
  this(float v) {
    m_value = v;
  }
}

int main(char[][] args) {
  Bar[3] bars;

  for (int i = 0; i < 3; i++) {
    bars[i] = new Bar(i);
  }
  bars.sort;

  return 0;
}

============================================


-- 

http://d.puremagic.com/issues/show_bug.cgi?id=323





------- Comment #1 from someanon@yahoo.com  2006-09-03 14:25 -------
Same problem on WindowsXP:

Error: need opCmp for class Bar


-- 

http://d.puremagic.com/issues/show_bug.cgi?id=323





------- Comment #2 from someanon@yahoo.com  2006-09-03 16:48 -------
Two more questions:

1) this is reported at compile time, but errors out at run-time. Maybe the compiler does see the opCmp, but other things goes wrong.

2) Before I isolate the problem, in my real program: on Linux, it builds and errors out at run-time.  But on WinXP, I have a link time error: "Unexpected OPTLINK Termination at EIP=0044C37B".  Not sure if it's related to this opCmp issue.


-- 

http://d.puremagic.com/issues/show_bug.cgi?id=323





------- Comment #3 from someanon@yahoo.com  2006-09-03 16:50 -------
Sorry, typo:

1) this is reported at compile time ...

should be:

1) this is NOT reported at compile time ...


-- 

d-bugmail@puremagic.com schrieb am 2006-09-03:
> http://d.puremagic.com/issues/show_bug.cgi?id=323

> I think this use to work; now on Linux dmd.166, it reports:

http://www.digitalmars.com/d/changelog.html#new0163
#
# Object.opCmp now throws an error. Should override it
# if used. Breaks existing code.
#

> Error: need opCmp for class Bar
>

<snip>
>   int opCmp(T other) {
>     int r;
>
>     if      (value < other.value)  {r = -1;}
>     else if (value > other.value)  {r =  1;}
>
>     return r;
>   }

The cause is a nasty result of D's function inheritance and overriding.

http://www.digitalmars.com/d/function.html
#
# A functions in a derived class with the same name and parameter types
# as a function in a base class overrides that function.
#

Thus "int T.opCmp(T other)" dosen't override "int Object.opCmp(Object o)" ...

Should do the trick:
#
# int opCmp(Object o){
#    T t = cast(T) o;
#    if(t is null){
#       return super.opCmp(o);
#    }else{
#       return opCmp(t);
#    }
# }
#
#   int opCmp(T other) {
#     int r;
#
#     if      (value < other.value)  {r = -1;}
#     else if (value > other.value)  {r =  1;}
#
#     return r;
#   }
#

Thomas

Since D's associative arrays use opCmp to resolve collisions, any class that has opEquals defined should probably have opCmp defined also.  The old default implementation of Object.opCmp in Phobos was not compatible with compacting GCs so it was replaced with a version that throws an exception on use.  However, there is a default implementation that actually works and is compatible with compacting GCs:

    int opCmp(Object o)
    {
	return this !is o;
    }

Compare to opEquals:

    int opEquals(Object o)
    {
        return this is o;
    }

The opCmp function above forces the binary tree chaining mechanism into a linked-list, and equivalence is resolved by pointer equality rather than some ordering mechanism.  It won't be as fast as an ordering implementation of opCall for the degenerate case but it has the benefit of being immune to object movement.  If a default implementation of opEquals is to remain in Phobos then I suggest adopting the default opCmp implementation above as well.

Sean Kelly wrote:
> Since D's associative arrays use opCmp to resolve collisions, any class that has opEquals defined should probably have opCmp defined also.  The old default implementation of Object.opCmp in Phobos was not compatible with compacting GCs so it was replaced with a version that throws an exception on use.  However, there is a default implementation that actually works and is compatible with compacting GCs:
> 
>     int opCmp(Object o)
>     {
>     return this !is o;
>     }

That's not a really good solution, as no usable ordering is defined (a>b and b>a will always be true whenever a !is b). While it may work for (degenerate) insertion into a binary tree, it's (imho) worse than throwing an exception in practically all other cases. For example, a quick sort will not only run really slow in O(n^2) time but also produce an unsorted result without any indication of error.


xs0

xs0 wrote:
> Sean Kelly wrote:
>> Since D's associative arrays use opCmp to resolve collisions, any class that has opEquals defined should probably have opCmp defined also.  The old default implementation of Object.opCmp in Phobos was not compatible with compacting GCs so it was replaced with a version that throws an exception on use.  However, there is a default implementation that actually works and is compatible with compacting GCs:
>>
>>     int opCmp(Object o)
>>     {
>>     return this !is o;
>>     }
> 
> That's not a really good solution, as no usable ordering is defined (a>b and b>a will always be true whenever a !is b). While it may work for (degenerate) insertion into a binary tree, it's (imho) worse than throwing an exception in practically all other cases. For example, a quick sort will not only run really slow in O(n^2) time but also produce an unsorted result without any indication of error.

Ah good point.  So any ideas?  Personally, I'd be happy if the default AA used a linked-list for chaining and opEquals for comparison so this wasn't an issue, but that seems a foregone conclusion.  I'm mostly concerned about providing default behavior that makes sense for the common case.  The problem I've run into is that I have objects which need to be used as keys in an AA but are not inherently sortable.

Sean Kelly wrote:
> xs0 wrote:
> Ah good point.  So any ideas?  Personally, I'd be happy if the default AA used a linked-list for chaining and opEquals for comparison so this wasn't an issue, but that seems a foregone conclusion.  I'm mostly concerned about providing default behavior that makes sense for the common case.  The problem I've run into is that I have objects which need to be used as keys in an AA but are not inherently sortable.

Well, one possibly good solution would be to templatize AAs and remove opCmp from Object. That way, you'd get an error when using comparison on objects without opCmp (most other operators work that way) and the template could test for its presence and use different implementations for each.

Another nice consequence would be the possibility of having optimized implementations for specific types; most probably even a single implementation could be considerably faster, because the compiler would know the exact type at compile-time, producing an optimized version of code for each.


xs0

xs0 wrote:
> Sean Kelly wrote:
>> xs0 wrote:
>> Ah good point.  So any ideas?  Personally, I'd be happy if the default AA used a linked-list for chaining and opEquals for comparison so this wasn't an issue, but that seems a foregone conclusion.  I'm mostly concerned about providing default behavior that makes sense for the common case.  The problem I've run into is that I have objects which need to be used as keys in an AA but are not inherently sortable.
> 
> Well, one possibly good solution would be to templatize AAs and remove opCmp from Object. That way, you'd get an error when using comparison on objects without opCmp (most other operators work that way) and the template could test for its presence and use different implementations for each.

Some fancier AA support would be nice, but I'm not sure how to add templates to the built-in syntax.  I just noticed something confusing in the spec however.  Why are classes intended to be used as keys in an AA required to implement both opCmp *and* opEquals?  Since the AA is backed by a binary tree I would expect it determine 'equality' as equivalence using opCmp.  It's quite common for me to define classes that are equivalent but not equal, and also classes that can be compared for equality but not sorted.  But it sounds like both would not be compatible with D's built-in AA implementation.  I'm beginning to feel that any possible performance advantage that can be offered from binary tree chaining over linked list chaining is overshadowed by the limitations it imposes on the use of AAs in general.  Can someone suggest an alternate default implementation for opCmp that solves these problems?


Sean