[Issue 24809] New: In some cases, stable sort assigns to unininitialized elements

[d-bugmail at puremagic.com]

https://issues.dlang.org/show_bug.cgi?id=24809

          Issue ID: 24809
           Summary: In some cases, stable sort assigns to unininitialized
                    elements
           Product: D
           Version: D2
          Hardware: All
                OS: All
            Status: NEW
          Severity: normal
          Priority: P1
         Component: phobos
          Assignee: nobody at puremagic.com
          Reporter: issues.dlang at jmdavisProg.com

This is essentially an extension of
https://issues.dlang.org/show_bug.cgi?id=24773

The fix for that one partially fixed the problem, but sort has a lot of
branches depending on the types used and the actual set of elements being
sorted, and there's another branch that's much harder to hit which also uses
uninitializedArray in spite of a type defining opAssign (which it will if the
type has a destructor).

The test case that I came up with is

---
void main()
{
    static struct E
    {
        int value;
        int valid = 42;

        ~this()
        {
            assert(valid == 42);
        }
    }

    import std.array : array;
    import std.range : chain, only, repeat;
    auto arr = chain(repeat(E(41), 18),
                     only(E(39)),
                     repeat(E(41), 16),
                     only(E(1)),
                     repeat(E(42), 33),
                     only(E(33)),
                     repeat(E(42), 16),
                     repeat(E(43), 27),
                     only(E(33)),
                     repeat(E(43), 34),
                     only(E(34)),
                     only(E(43)),
                     only(E(63)),
                     repeat(E(44), 42),
                     only(E(27)),
                     repeat(E(44), 11),
                     repeat(E(45), 64),
                     repeat(E(46), 3),
                     only(E(11)),
                     repeat(E(46), 7),
                     only(E(4)),
                     repeat(E(46), 34),
                     only(E(36)),
                     repeat(E(46), 17),
                     repeat(E(47), 36),
                     only(E(39)),
                     repeat(E(47), 26),
                     repeat(E(48), 17),
                     only(E(21)),
                     repeat(E(48), 5),
                     only(E(39)),
                     repeat(E(48), 14),
                     only(E(58)),
                     repeat(E(48), 24),
                     repeat(E(49), 13),
                     only(E(40)),
                     repeat(E(49), 38),
                     only(E(18)),
                     repeat(E(49), 11),
                     repeat(E(50), 6)).array();

    import std.algorithm.mutation : SwapStrategy;
    import std.algorithm.sorting : sort;
    arr.sort!((a, b) => a.value < b.value, SwapStrategy.stable)();
}
---

It's not terribly pretty, and there's probably a shorter list of values which
would trigger the problem, but I found it to be quite difficult to purposefully
hit the branch that has the problem, and this list of values does it.

--