Associative arrays do not correctly handle keys with copy constructors

[dlangBugzillaToGithub]

Jonathan M Davis (@jmdavis) reported this on 2024-10-18T09:56:56Z

Transferred from https://issues.dlang.org/show_bug.cgi?id=24820

Description

This code

```
import std.stdio;

void main()
{
    auto count = new Count;

    string[S] aa;
    aa[S(count, 42)] = "foo";

    writeln("---");
    writeln(*count);
    assert(count.refCount == 1);

    writeln("---");
    assert(S(count, 42) in aa);
    writeln("---");
    writeln(*count);
    assert(count.refCount == 1);

    writeln("---");
    assert(S(new Count, 22) !in aa);
    writeln("---");
    writeln(*count);
    assert(count.refCount == 1);
}

struct Count
{
    int constructed;
    int copyConstructed;
    int assignedFrom;
    int assignedTo;
    int destroyed;
    int refCount;

    string toString()
    {
        import std.format : format;

        return format("Constructed: %s times
", constructed) ~
               format("Copy Constructed: %s times
", copyConstructed) ~
               format("Assigned From: %s times
", assignedFrom) ~
               format("Assigned To: %s times
", assignedTo) ~
               format("Destroyed: %s times
", destroyed) ~
               format("refCount: %s", refCount);
    }
}

struct S
{
    Count* count;
    int i;
    bool destroyed;

    this(Count* count, int i)
    {
        this.count = count;
        this.i = i;
        ++count.constructed;
        ++count.refCount;
        writefln("Constructing: %s, count(%s)", i, count);
    }

    this(ref S rhs)
    {
        this.count = rhs.count;
        this.i = rhs.i;

        ++count.copyConstructed;
        ++count.refCount;
        writefln("Copy Constructing: %s, count(%s)", i, count);
    }

    ~this()
    {
        writefln("Destroying: %s, count(%s)", i, count);

        if(count)
        {
            ++count.destroyed;
            --count.refCount;
        }

        destroyed = true;
    }

    void opAssign()(auto ref S rhs)
    {
        writefln("Assigning %s, count(%s) to %s, count(%s)",
                 rhs.i, rhs.count, this.i, this.count);

        if(this.count)
        {
            ++this.count.assignedTo;
            --this.count.refCount;
        }

        if(rhs.count)
        {
            ++this.count.assignedFrom;
            ++this.count.refCount;
        }

        this.count = rhs.count;
        this.i = rhs.i;
    }

    invariant
    {
        assert(!destroyed);
    }

    bool opEquals()(const auto ref S rhs) const {
        return this.i == rhs.i;
    }

    size_t toHash() const {
        return 0;
    }
}
```

has this output:

```
Constructing: 42, count(7F7AF01A9000)
Destroying: 42, count(7F7AF01A9000)
---
Constructed: 1 times
Copy Constructed: 0 times
Assigned From: 0 times
Assigned To: 0 times
Destroyed: 1 times
refCount: 0
[email protected](12): Assertion failure
----------------
??:? _d_assertp [0x5e7bf2fe9c74]
??:? _Dmain [0x5e7bf2fc99ca]
Destroying: 42, count(7F7AF01A9000)
```

Pretty clearly, the issue is this line:

    aa[S(count, 42)] = "foo";

Ideally, the temporary would just be moved, and no copies would be necessary, but the AA does need to have a copy of the key so that it can compare against it when doing look-ups later. So, depending on the implementation, it would make sense if the temporary were copied at some point in the process rather than moved, and then the temporary would need to be destroyed. But that means that one of two things should be happening here. Either, the temporary should be moved, and there should be no destructor calls, or the temporary should be copied, resulting in a copy constructor call to get the copy that the AA stores and then a destructor call for the temporary. However, it looks like a copy is probably being made via blitting, and then the temporary is destroyed, which is obviously going to result in the wrong behavior in any case where a copy constructor is actually needed.

Changing the copy constructor to a postblit constructor fixes the problem, so it would appear that AAs simply weren't updated to take copy constructors into account.

And commenting out the assertions for the reference count (so that the code which is checking what happens with the in operator can run) clearly indicates that the in operator isn't handling copy constructors properly either.

[dlangBugzillaToGithub]

issues.dlang (@jmdavis) commented on 2024-10-18T10:05:52Z

FYI, opAssign should have been

```
    void opAssign()(auto ref S rhs)
    {
        writefln("Assigning %s, count(%s) to %s, count(%s)",
                 rhs.i, rhs.count, this.i, this.count);

        if(this.count)
        {
            ++this.count.assignedTo;
            --this.count.refCount;
        }

        if(rhs.count)
        {
            ++rhs.count.assignedFrom;
            ++rhs.count.refCount;
        }

        this.count = rhs.count;
        this.i = rhs.i;
    }

```

I screwed it up and mutated this.count instead of rhs.count in the rhs.count section, but it doesn't actually get triggered with what main is doing, so it doesn't really matter. The example has more than is strictly necessary to show the bug, because I was trying to show exactly what was going on without knowing for sure which operations the AA would be using.

[dlangBugzillaToGithub]

issues.dlang (@jmdavis) commented on 2024-10-18T10:15:26Z

It looks like the AA implementation currently has a test to verify that it handles postblits correctly. Presumably, that could be copied and reworked to verify that copy constructors get called correctly:

https://github.com/dlang/dmd/blob/master/druntime/src/rt/aaA.d#L935