Issue 24809 - In some cases, stable sort assigns to unininitialized elements
Summary: In some cases, stable sort assigns to unininitialized elements
Status: RESOLVED FIXED
Alias: None
Product: D
Classification: Unclassified
Component: phobos (show other issues)
Version: D2
Hardware: All All
: P1 normal
Assignee: No Owner
URL:
Keywords: pull
Depends on:
Blocks:
 
Reported: 2024-10-13 10:13 UTC by Jonathan M Davis
Modified: 2024-10-28 13:22 UTC (History)
0 users

See Also:


Attachments

Note You need to log in before you can comment on or make changes to this issue.
Description Jonathan M Davis 2024-10-13 10:13:22 UTC
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.
Comment 1 Dlang Bot 2024-10-13 12:18:56 UTC
@jmdavis created dlang/phobos pull request #9057 "Fix bugzilla issue 24809: In some cases, stable sort assigns to unininitialized elements" fixing this issue:

- Fix bugzilla issue 24809: In some cases, stable sort assigns to unininitialized elements

https://github.com/dlang/phobos/pull/9057
Comment 2 Dlang Bot 2024-10-18 03:00:08 UTC
dlang/phobos pull request #9057 "Fix bugzilla issue 24809: In some cases, stable sort assigns to unininitialized elements" was merged into master:

- be532da54bff035b68adc2be5d6e6d21055af818 by Jonathan M Davis:
  Fix bugzilla issue 24809: In some cases, stable sort assigns to unininitialized elements

https://github.com/dlang/phobos/pull/9057
Comment 3 Dlang Bot 2024-10-28 13:22:18 UTC
dlang/phobos pull request #9076 "[stable] Cherry-pick 2 master fixes" was merged into stable:

- ef6a991534e085d82eebc65a9b09af68c05b0906 by Jonathan M Davis:
  Fix bugzilla issue 24809: In some cases, stable sort assigns to unininitialized elements (#9057)

https://github.com/dlang/phobos/pull/9076