www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 4789] New: std.algorithm.sort bug

reply d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4789

           Summary: std.algorithm.sort bug
           Product: D
           Version: D2
          Platform: Other
        OS/Version: Windows
            Status: NEW
          Severity: normal
          Priority: P2
         Component: DMD
        AssignedTo: nobody puremagic.com
        ReportedBy: soarowl yeah.net



private import 
    std.algorithm,
    std.stdio;

void main()
{
    int[2][] a;
    a ~= [1, 2];
    a ~= [2, 3];
    a ~= [3, 4];
    a ~= [1, 1];

    std.algorithm.sort(a);
    std.stdio.writefln("%s", a);
}


When I compile without any arguments, the runtime has an "object.Exception:
overlapping array copy" exception;

But when I compile with -release or -release -inline arguments, the result is
correct.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Sep 02 2010
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4789


David Simcha <dsimcha yahoo.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
                 CC|                            |dsimcha yahoo.com
         Resolution|                            |FIXED



Here's the swap algorithm used in the int[] instantiation in std.algorithm:

auto t = a;
a = b;
b = t;

This function is broken for static arrays if a and b are the same array, and in
your example, swap() gets called with the rhs and lhs being the same array. 
This is probably related to using optimized memcpy() routines under the hood
for copying static arrays.  The language should arguably do the right thing
when a static array is assigned to itself instead of this kind of crazy
behavior. 

In the mean time, I've inserted a trivial check into swap() that only gets
compiled in for static arrays.  It's a kludge, but it's a trivial,
well-encapsulated kludge and can be removed when the deeper issue gets solved.

http://dsource.org/projects/phobos/changeset/1948

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Sep 02 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4789


dawg dawgfoto.de changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |REOPENED
                 CC|                            |dawg dawgfoto.de
         Resolution|FIXED                       |



import std.traits : hasElaborateAssign;
import std.algorithm : swap;

struct Elem {
  ~this() {}
}
static assert(hasElaborateAssign!Elem);

void main() {
  auto elem = Elem();
  swap(elem, elem);
}

----

This bug still exists for structs with elaborate assign.

It throws an "object.Exception: overlapping array copy".

Before changeset 1948 the implementation used memcpy which would have also led
to undefined behavior on some platforms.
Now swap uses _d_arraycopy which throws the overlapping exception.

Proposed fix is to add an "if (lhs !is rhs)" around the struct copy code.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jan 11 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4789





 Before changeset 1948 the implementation used memcpy which would have also led
 to undefined behavior on some platforms.


This was changeset 2180 that changed the implementation. But as stated is
essentially broken in both versions.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jan 11 2011
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4789


dawg dawgfoto.de changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|REOPENED                    |RESOLVED
         Resolution|                            |DUPLICATE



*** This issue has been marked as a duplicate of issue 5705 ***

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