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

           Summary: sorting arrays of structs is broken
           Product: D
           Version: 2.000
          Platform: PC
        OS/Version: Windows
            Status: NEW
          Keywords: wrong-code
          Severity: regression
          Priority: P2
         Component: DMD
        AssignedTo: bugzilla@digitalmars.com
        ReportedBy: thecybershadow@gmail.com


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.


-- 

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





------- Comment #1 from wbaxter@gmail.com  2008-11-28 13:11 -------
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.


-- 

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





------- Comment #2 from wbaxter@gmail.com  2008-11-28 13:16 -------
(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.


-- 

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





------- Comment #3 from gide@nwawudu.com  2009-04-07 04:13 -------
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?


-- 

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


Rob Jacques <sandford@jhu.edu> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |sandford@jhu.edu




--- Comment #4 from Rob Jacques <sandford@jhu.edu>  2009-07-17 13:22:53 PDT ---
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).

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

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


David Simcha <dsimcha@yahoo.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dsimcha@yahoo.com




--- Comment #5 from David Simcha <dsimcha@yahoo.com>  2009-07-17 13:57:09 PDT ---
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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

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


Koroskin Denis <2korden@gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |2korden@gmail.com


--- Comment #6 from Koroskin Denis <2korden@gmail.com> 2010-09-18 15:50:15 PDT ---
int opCmp(ref const Foo other) const works for me. Is the issue still open?

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

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


bearophile_hugs@eml.cc changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bearophile_hugs@eml.cc


--- Comment #7 from bearophile_hugs@eml.cc 2010-09-19 17:59:08 PDT ---
I think this bug may be closed, but see also bug 4290.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

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


Kenji Hara <k.hara.pg@gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
                 CC|                            |k.hara.pg@gmail.com
         Resolution|                            |FIXED


--- Comment #8 from Kenji Hara <k.hara.pg@gmail.com> 2011-04-12 02:36:01 PDT ---
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);
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------