www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - "Overlapping array copy" exception sorting an array of Tuples

reply André Stein <stone steinsoft.net> writes:
Hi,

I'm trying to sort an array of tuples (Tuple!(uint, string) type) but the
program bails out with the exception "overlapping array copy"
(arraycat.d(40)). To make things short here is the source code:

import std.typecons;
import std.algorithm;
void main(string[] args)
{
    alias Tuple!(uint, "number", string, "text") TestT;
    TestT[] array = [ TestT(50, "test1"), TestT(100, "test2"), TestT(68,
"test3") ];
    sort(array);
}

When I implement a struct TestT which imitates the behaviour of the concrete
Tuple-type the sorting algorithm just works fine:

struct TestT
{
    uint number; string text;

    this(uint number, string text)
    {
        this.number = number;
        this.text = text;
    }

    int opCmp(TestT rhs)
    {
        return number - rhs.number;
    }
}

void main(string[] args)
{
     TestT[] array = [ TestT(50, "test1"), TestT(100, "test2"), TestT(68,
"test3") ];
    sort(array);
}

I don't really understand this error. Am I missing something in the usage of
Tuple? Or might this be a bug in the sort implementation? Btw. I am using the
latest version of the DMD compiler. Compiling and running the source with the
"-release" flag doesn't end with an exception and seems to produce the right
sorted array.

Thanks in advance for any clarifications!

Regards,
André
Mar 07 2011
next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday, March 07, 2011 06:36:31 Andr=EF=BF=BD Stein wrote:

 Hi,
=20
 I'm trying to sort an array of tuples (Tuple!(uint, string) type) but the
 program bails out with the exception "overlapping array copy"
 (arraycat.d(40)). To make things short here is the source code:
=20
 import std.typecons;
 import std.algorithm;
 void main(string[] args)
 {
     alias Tuple!(uint, "number", string, "text") TestT;
     TestT[] array =3D [ TestT(50, "test1"), TestT(100, "test2"), TestT(68,
 "test3") ];
     sort(array);
 }
=20
 When I implement a struct TestT which imitates the behaviour of the
 concrete Tuple-type the sorting algorithm just works fine:
=20
 struct TestT
 {
     uint number; string text;
=20
     this(uint number, string text)
     {
         this.number =3D number;
         this.text =3D text;
     }
=20
     int opCmp(TestT rhs)
     {
         return number - rhs.number;
     }
 }
=20
 void main(string[] args)
 {
      TestT[] array =3D [ TestT(50, "test1"), TestT(100, "test2"), TestT(6=


8,

 "test3") ];
     sort(array);
 }
=20
 I don't really understand this error. Am I missing something in the usage
 of Tuple? Or might this be a bug in the sort implementation? Btw. I am
 using the latest version of the DMD compiler. Compiling and running the
 source with the "-release" flag doesn't end with an exception and seems to
 produce the right sorted array.
=20
 Thanks in advance for any clarifications!


Well, Tuple _is_ a struct, so if it's failing with Tuple, it's not going to=
 work=20
with just any struct (though apparently it works just fine with the struct =
that=20
you wrote). Regardless, it definitely sounds like a bug in sort (or somethi=
ng=20
that sort uses). You should probably open a bug for it:

http://d.puremagic.com/issues/

Though honestly, I don't know why you'd want to use a tuple in this case. I=
 tend=20
to think that if you're going to name the fields, you might as well declare=
 a=20
struct, but whatever.

Oh, on a side note, your opCmp is wrong on two counts. First off, its signa=
ture=20
should be

int opCmp(ref const TestT rhs) const

I don't think that sort even calls you opCmp, because its signature is wron=
g=20
(arguably, the compiler is currently overly picky about the signature for=20
opEquals and opCmp, but they _must_ be exact). So, the default comparison i=
s=20
being used, not your opCmp.

The second problem (which you may know about but not have cared) is that us=
ing=20
subtraction like that in opCmp is going to fail if the numbers are large en=
ough=20
that you get overflow. For a completely correct comparison function which u=
ses=20
integral types, you need to actually do proper comparisons, not subtract th=
em.=20
If you _know_ that your numbers are small enough though, it doesn't actuall=
y=20
matter, since you'll never get an overflow.

=2D Jonathan M Davis
Mar 07 2011
prev sibling next sibling parent =?UTF-8?B?QW5kcsOpIFN0ZWlu?= <stone steinsoft.net> writes:
Hi,

Thanks first for your detailed reply!

On 03/07/2011 07:21 PM, Jonathan M Davis wrote:

 Well, Tuple _is_ a struct, so if it's failing with Tuple, it's not going to
work
 with just any struct (though apparently it works just fine with the struct that
 you wrote). Regardless, it definitely sounds like a bug in sort (or something
 that sort uses). You should probably open a bug for it:

 http://d.puremagic.com/issues/

 Though honestly, I don't know why you'd want to use a tuple in this case. I
tend
 to think that if you're going to name the fields, you might as well declare a
 struct, but whatever.


I started using Tuples only but I used the naming feature to exchange 
the Tuple and struct implementations easily. Anyway this is no 
production code, just test code to learn D :) Anyway I'll open a bug for 
it. Thanks for the link!



 Oh, on a side note, your opCmp is wrong on two counts. First off, its signature
 should be

 int opCmp(ref const TestT rhs) const

 I don't think that sort even calls you opCmp, because its signature is wrong
 (arguably, the compiler is currently overly picky about the signature for
 opEquals and opCmp, but they _must_ be exact). So, the default comparison is
 being used, not your opCmp.


I tried both signatures of opCmp but the result seemed the same (both 
sequences of structs sorted correctly). So I wonder what is the default 
comparison of a user defined struct type? Not implementing an opCmp 
function lead to a compiler error..


 The second problem (which you may know about but not have cared) is that using
 subtraction like that in opCmp is going to fail if the numbers are large enough
 that you get overflow. For a completely correct comparison function which uses
 integral types, you need to actually do proper comparisons, not subtract them.
 If you _know_ that your numbers are small enough though, it doesn't actually
 matter, since you'll never get an overflow.


I actually didn't care about that problem but I _will_ do that in future.

Regards,
André
Mar 07 2011
prev sibling parent bearophile <bearophileHUGS lycos.com> writes:
André Stein:


 I'm trying to sort an array of tuples (Tuple!(uint, string) type) but the
 program bails out with the exception "overlapping array copy"


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

I think Phobos unittests are seriously lacking.

Bye,
bearophile
Mar 07 2011