Godot: Dictionary keys are stored by reference

Created on 7 Dec 2018 · 10Comments · Source: godotengine/godot

Godot version:
3.0.6 stable

OS/device including version:
Ubuntu Bionic 64bit

Issue description:

var xx = {}

var k1 = [[1,2], [3,4]]
var k2 = [[1,2], [3,4]]
var v1 = [1,2,3]
xx[k1] = v1
print(xx.has(k2))

k1[0][0] = 999
print(xx.has(k2))

print(xx.has(k1))
print(xx.keys())

The result:

True
False
False
[[[999, 2], [3, 4]]]

There are two issues here:

Changing k1 changes the key in the dictionary which implies that the key stored in the dictionary is actually a reference to k1. This might be the design and not a bug, but if it is the design, I am not sure how does it work with the hash of the key which is used to quickly find the value in the internal data structure. Additionally this is counter intuitive and not documented.
After changing k1 there is no more way to retrieve the value. Both k1 and k2 considered not in the dictionary. This is most probably a bug.

bug discussion core

Source

alkhimey

All 10 comments

Labelling as "bug" for now, I'm not sure if it's actually a bug or by design, but this needs to be reviewed (and if the latter, documented indeed).

akien-mga on 7 Dec 2018

take a look at ordered_hash_map.h line ~249 line.

    V &operator[](const K &p_key) {
        Element e = find(p_key);
        if (!e) {
            // consistent with Map behaviour
            e = insert(p_key, V());
        }
        return e.value();
    }

for dictionary, the K template == Variant..
so there needs to be some template specializiation for where K == Variant
in which the k value is copied.

pgruenbacher on 7 Dec 2018

👍1

@alkhimey if you were to update k1 so it matches the original value, you would see that you'd be able to retrieve the v1 value? I think it hashes the k value upon insertion, but then keeps a reference to the key value purely for returning the keys list... so theoretically values should still be accessible.

pgruenbacher on 7 Dec 2018

The keys you are using are arrays. Arrays are mutable types that are always passed by reference. That includes when they are used as dictionary values, or dictionary keys. So yeah, it's just by design.

I never really understood the point of using arrays directly as keys and hashing them by content. I don't know any language doing it, even Python does not allow it and instead asks for a tuple, which is immutable, unlike arrays, probably due to the issue mentionned here.

If we want to keep this, perhaps the only way is to copy the array on insertion if used as a dictionary key.

Zylann on 8 Dec 2018

@pgruenbacher The relevant code I believe is here

/* I want to have only one function.. */
    _FORCE_INLINE_ const Element *get_element(const TKey &p_key) const {

        uint32_t hash = Hasher::hash(p_key);
        uint32_t index = hash & ((1 << hash_table_power) - 1);

        Element *e = hash_table[index];

        while (e) {

            /* checking hash first avoids comparing key, which may take longer */
            if (e->hash == hash && Comparator::compare(e->pair.key, p_key)) {

                /* the pair exists in this hashtable, so just update data */
                return e;
            }

            e = e->next;
        }

        return NULL;
}

My conclusion is that after changing r1:
r1 does not have the correct hash anymore.
r2 has the correct hash but it's contents are different from r1 ( Comparator::compare returns false )

I think making a copy of the keys (and values?) is a good solution.

If it is not important enough to change or breaks the overall design, a simple warning in the documentation can be of a great help for other developers.

alkhimey on 8 Dec 2018

👍1

I think it might be nice to have a warning emitted whenever the key is Variant and is_shared returns true for it.
Alternatively, Dictionary should call Variant.duplicate(deep=true) when inserting the keys.