Bug 1309 – sorting arrays of structs is broken

Code: import std.stdio; import std.random; struct MyStruct { uint field; int opCmp(MyStruct* m) { writefln("This is opCmp"); return field - m.field; } } void main() { MyStruct[] structs; for(int i=0;i<50;i++) structs ~= MyStruct(50-i); structs.sort; foreach(s;structs) writefln(s.field); } opCmp doesn't get called. From analyzing the resulting binary, it seems that opCmp is never referenced anywhere in the executable. It seems that it doesn't make it into the struct's VTBL (if I understood correctly that struct typeinfos have one). This happens on all 2.x versions since 2.000. Doesn't happen on latest 1.x.

Just a stab in the dark, but you might try making the argument to opCmp 'const MyStruct' or 'const MyStruct*'. An opCmp shouldn't generally modify its argument so maybe DMD expects a 'const' in the signature. Also, when it comes to opCmp be aware of #1861. At least in D1, using a pointer argument works for .sort, but it doesn't work for regular a<b struct comparisons.

(In reply to comment #1) > Just a stab in the dark, but you might try making the argument to opCmp 'const > MyStruct' or 'const MyStruct*'. An opCmp shouldn't generally modify its > argument so maybe DMD expects a 'const' in the signature. > Actually, if the above hypothesis is true, then probably 'this' should be const, too: int opCmp(const MyStruct x) const { ... } (if that's how you make this constant in D2 these days...} There might be another problem, though, with the most recent D2, since 'this' is now a reference. As mentioned in bug 1861, using ref arguments in your opCmp never worked with .sort, this might affect D2 now that this is a reference.

The documentation for structs in associative array mentions that opCmp should be declared as 'int opCmp(ref const MyStruct x) const', this definition should be applied to standard arrays as well. The section 'Using Structs or Unions as the KeyType' should be applied to standard and associative arrays. So maybe this isue should be marked as a spec change?

I was just bitten by this bug (porting some D1 code). However, switching 'int opCmp(myStruct b)' to 'int opCmp(ref const myStruct b) const' fixed the issue. So I agree this is a spec change and not wrong code generation. The operator overloading documentation needs to be updated: Both the example: struct Pair { int a, b; int opCmp(ref const Pair rhs)const { if (a!=rhs.a) return a-rhs.a; return b-rhs.b; } } And Text: The parameter to opEquals and opCmp for class definitions must be of type Object, rather than the type of the particular class, in order to override the Object.opEquals and Object.opCmp functions properly. The opEquals and opCmp definitions for structs must be of type const and the parameter must be of type ref const in order for array sorting or associative array key ordering to work properly. Array documentation needs to be updated: For the .sort property to work on arrays of structs or unions, the struct or union definition must define the function: const int opCmp(ref const S). The type S is the type of the struct or union. This function will determine the sort ordering. Note that none of the following work: int opCmp(ref const myStruct b) int opCmp( const myStruct* b) const int opCmp( const myStruct b) const int opCmp( const myStruct b) int opCmp( myStruct b) const int opCmp( myStruct b) As this issue causes D1 code to silently fail when ported to D2, it might be justified to add a compiler warning when a struct contains an incorrect opCmp function, similar to the runtime error that occurs when opCmp(MyClass c) is defined instead of opCmp(Object o).

Technically this is a spec issue, but if that's the case the spec is so unnecessarily restrictive that this really qualifies as a bona fide bug. Furthermore, other forms of opCmp work for everything but builtin sort, so we have an inconsistency here. IMHO the solution is to get rid of the (highly inflexible and fairly slow) builtin sort altogether and, for convenience and backwards compatibility, put std.algorithm.sort, along with a few other very simple, frequently used things (reverse, min, max come to mind) in Object so they're imported implicitly.

int opCmp(ref const Foo other) const works for me. Is the issue still open?

I think this bug may be closed, but see also bug 4290.

On trunk dmd, this code works. ---- import std.stdio; import std.random; struct MyStruct { uint field; //int opCmp(MyStruct* m) int opCmp(ref const(MyStruct) m) const { writeln("This is opCmp"); return field - m.field; } } void main() { MyStruct[] structs; for(int i=0;i<50;i++) structs ~= MyStruct(50-i); structs.sort; foreach(s;structs) writeln(s.field); }