www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 1309] New: sorting arrays of structs is broken

reply d-bugmail puremagic.com writes:
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.


--
Jul 02 2007
next sibling parent d-bugmail puremagic.com writes:
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.


--
Nov 28 2008
prev sibling next sibling parent d-bugmail puremagic.com writes:
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.


--
Nov 28 2008
prev sibling next sibling parent d-bugmail puremagic.com writes:
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?


--
Apr 07 2009
prev sibling next sibling parent d-bugmail puremagic.com writes:
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: -------
Jul 17 2009
prev sibling next sibling parent d-bugmail puremagic.com writes:
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: -------
Jul 17 2009
prev sibling next sibling parent d-bugmail puremagic.com writes:
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: -------
Sep 18 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
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: -------
Sep 19 2010
prev sibling parent d-bugmail puremagic.com writes:
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: -------
Apr 12 2011