How can I uniquely identify an Array?

:information_source: Attention Topic was automatically imported from the old Question2Answer platform.
:bust_in_silhouette: Asked By archeron

I have an Array that may eventually contain a reference to itself. The simplest case would be something like this:

var cyclic = [1, 2, 3]
cyclic.append(cyclic)

Now I’d like to recursively process such structures without ending in an infinite loop, e.g. something like that:

func do_something(structure, already_visited):
    if typeof(structure) == TYPE_INT:
        print("do something with it")
    elif typeof(structure) == TYPE_ARRAY:
        if already_visited.has(structure):
            return
        already_visited[structure] = true
        for item in structure:
            do_something(item, already_visited)

do_something(cyclic, {})

Unfortunately this doesn’t work because

already_visited[structure] = true

seems to send GDScript into an infinite loop (it is probably trying to build a hash value for the Array and ends up in the cycle…). So I can’t put a reference to the cyclic array itself into already_visited - but what else can I put in there that will uniquely identify the Array? Is there something like Python’s id() function that would yield, for example, the memory address of the Array?

Have you tried using the Array hash() function to identify the array?

Ertain | 2021-03-08 06:12

Unfortunately, this ends in an infinite loop - GDScript never comes back from:

var a = [1, 2, 3]
a.append(a)
var h = hash(a)   # hangs
print("This never gets executed")

Makes sense, too: GDScript seems to implement hash() without safety checks for cyclic structures, which I can understand - it would be a waste of time for 99.9% of the time. This is most likely the underlying reason of why adding a cyclic structure as a key in a dictionary hangs - there’s an implicit call to hash involved.

archeron | 2021-03-08 19:32

You could add a flag to the actual array.
Maybe at element 0

elif typeof(structure) == TYPE_ARRAY:
        if structure[0] == TYPE_ARRAY: 
            return   # element has already been visited
        # the first element type is irrelevant and I use bool here 
        # second element contains the actual first element of structure
        structure[0] = [true, structure[0]]   

LeslieS | 2023-02-12 17:13

:bust_in_silhouette: Reply From: dabuwhy

you can use map
then get map.keys() as a set