"Overlapping array copy" exception sorting an array of Tuples

[Jonathan M Davis]

On Monday, March 07, 2011 06:36:31 Andr� Stein wrote:
> 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!

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.

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.

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.

- Jonathan M Davis