Modifying an `Array` being a `Dictionary` key can result in that `Dictionary` having duplicate keys

kleonc commented 2 years ago

Godot version

3.4.4.stable, 3.5.beta3

System information

N/A

Issue description

Title. Dictionary can end up with duplicate keys (many dict entries with the same key). For details see the output of the test script below.

Steps to reproduce

Test script:

tool
extends EditorScript

enum ModificationType {ChangeFirstElement, PushBack}

func _run() -> void:
    test(ModificationType.ChangeFirstElement, false)
    test(ModificationType.ChangeFirstElement, true)
    test(ModificationType.PushBack, false)
    test(ModificationType.PushBack, true)

func test(modification_type: int, assign_new_value: bool) -> void:
    var d := {}
    var a := [-1]
    d[a] = "InitialValue"

    var format_string := "%-22s | d.size == %d | d == %s"
    print("var d := {}")
    print("var a := [-1]")
    print(format_string % ['d[a] = "InitialValue"', d.size(), d])

    for i in 3:
        match modification_type:
            ModificationType.ChangeFirstElement:
                a[0] = i
                print(format_string % ["a[0] = %d" % i, d.size(), d])
            ModificationType.PushBack:
                a.push_back(i)
                print(format_string % ["a.push_back(%d)" % i, d.size(), d])

        if assign_new_value:
            d[a] = i * 10
            print(format_string % ["d[a] = %d * 10" % i, d.size(), d])

    print("-".repeat(120))

Output:

var d := {}
var a := [-1]
d[a] = "InitialValue"  | d.size == 1 | d == {[-1]:InitialValue}
a[0] = 0               | d.size == 1 | d == {[0]:Null}
a[0] = 1               | d.size == 2 | d == {[1]:Null, [1]:Null}
a[0] = 2               | d.size == 3 | d == {[2]:Null, [2]:Null, [2]:Null}
------------------------------------------------------------------------------------------------------------------------
var d := {}
var a := [-1]
d[a] = "InitialValue"  | d.size == 1 | d == {[-1]:InitialValue}
a[0] = 0               | d.size == 1 | d == {[0]:Null}
d[a] = 0 * 10          | d.size == 2 | d == {[0]:0, [0]:0}
a[0] = 1               | d.size == 2 | d == {[1]:Null, [1]:Null}
d[a] = 1 * 10          | d.size == 3 | d == {[1]:10, [1]:10, [1]:10}
a[0] = 2               | d.size == 3 | d == {[2]:Null, [2]:Null, [2]:Null}
d[a] = 2 * 10          | d.size == 4 | d == {[2]:20, [2]:20, [2]:20, [2]:20}
------------------------------------------------------------------------------------------------------------------------
var d := {}
var a := [-1]
d[a] = "InitialValue"  | d.size == 1 | d == {[-1]:InitialValue}
a.push_back(0)         | d.size == 1 | d == {[-1, 0]:Null}
a.push_back(1)         | d.size == 2 | d == {[-1, 0, 1]:Null, [-1, 0, 1]:Null}
a.push_back(2)         | d.size == 3 | d == {[-1, 0, 1, 2]:Null, [-1, 0, 1, 2]:Null, [-1, 0, 1, 2]:Null}
------------------------------------------------------------------------------------------------------------------------
var d := {}
var a := [-1]
d[a] = "InitialValue"  | d.size == 1 | d == {[-1]:InitialValue}
a.push_back(0)         | d.size == 1 | d == {[-1, 0]:Null}
d[a] = 0 * 10          | d.size == 2 | d == {[-1, 0]:0, [-1, 0]:0}
a.push_back(1)         | d.size == 2 | d == {[-1, 0, 1]:Null, [-1, 0, 1]:Null}
d[a] = 1 * 10          | d.size == 3 | d == {[-1, 0, 1]:10, [-1, 0, 1]:10, [-1, 0, 1]:10}
a.push_back(2)         | d.size == 3 | d == {[-1, 0, 1, 2]:Null, [-1, 0, 1, 2]:Null, [-1, 0, 1, 2]:Null}
d[a] = 2 * 10          | d.size == 4 | d == {[-1, 0, 1, 2]:20, [-1, 0, 1, 2]:20, [-1, 0, 1, 2]:20, [-1, 0, 1, 2]:20}
------------------------------------------------------------------------------------------------------------------------

Minimal reproduction project

DictDuplicateKeys.zip

Zylann commented 2 years ago

Same vein as https://github.com/godotengine/godot/issues/44471 Possible duplicate of https://github.com/godotengine/godot/issues/24215

RedHeadphone commented 2 years ago

In most programing language Dictionary keys are immutable, So we can implement same into GD script by raising exception when Dictionary key is mutable(like Array). For using Array as key we can have method in Array which serializes Array into sting which can be used as key.

How does that sound @Zylann

Zylann commented 2 years ago

@RedHeadphone I commented on that here https://github.com/godotengine/godot/issues/24215#issuecomment-445412993

godotengine / godot