Should we allow recursive referencing in Dictionary/Array ?

[touilleMan]

While working on a new equal operator for Array and Dictionary (see #35816), I've encountered crash when dealing with recursive containers.

Example running with Godot 3.2:

var key_recursive_d_1 = {1: 1}
var key_recursive_d_2 = {1: 1}
key_recursive_d_1[key_recursive_d_2] = 1
key_recursive_d_2[key_recursive_d_1] = 1
# BUG !!!! This segfaults here !
print("key_recursive_d_1 == key_recursive_d_2 ==> ", key_recursive_d_1 == key_recursive_d_2)

Another with hash:

var d = {}
d[1] = d
# BUG !!!! This segfaults here !
print("d.hash() ==> ", d.hash())

Another with array:

var recursive_a_1 = [1]
recursive_a_1.append(recursive_a_1)
print("recursive: ", recursive_a_1)
# BUG !!!! This segfaults here !
print("recursive_a_1 == recursive_a_1 ==> ", recursive_a_1 == recursive_a_1)

This lead me to think recursive container are a curiosity that are not well handled but not much people care about them (I couldn't find any issue about that).

However correctly handling recursive container is tricky (see my changes to my PR to implement this: 5c214d18c0f78b90a4bbb8a65a81926acabb9681, and I'm not really sure this is 100% correct :/)

On top of that recursive container end up in memory leaks with Godot (I'm not aware of a cyclic reference detector in Godot)...

So my question is "do we really want to support this ?" Or wouldn't be just fine to run recursive reference detection when adding a container to another container, and printing an error if such thing is detected ?

[touilleMan]

Or wouldn't be just fine to run recursive reference detection when adding a container to another container, and printing an error if such thing is detected ?

Another even better solution would be to simply define a recursion limit. The good think about this approach is it should be dead simple to implement and won't increase the algorithm complexity (unlike the previous solution for instance)

[touilleMan]

I've implemented the recursion limit in my PR, see 0d8f573 ;-)

[akien-mga]

Can you check the status in the current master branch?

From a quick check the Dictionary example seems to properly catch and abort on infinite recursion (probably after #51068), but the Array case seems to still crash.

[akien-mga]

Can you check the status in the current master branch?

Poke ;)

[KoBeWi]

No longer crashes, the recursion is handled properly:

E 0:00:04:404   2D2D.tscn::GDScript_7yl3a:7 @ _ready(): Max recursion reached
  <C++ Source>  C:\godot_source\core/variant/dictionary.cpp:341 @ Dictionary::recursive_hash()
  <Stack Trace> 2D2D.tscn::GDScript_7yl3a:7 @ _ready()