Handling Cycles

We built a simple reference counting garbage collector. It can handle:

Simple types, like INT and FLOAT.
Dynamically allocated types, like STRING.
Static Container types, like VECTOR3.
Dynamic Container types, like ARRAY.

However, there's one little problem with our implementation. Take a look at this code:

snek_object_t *first = new_snek_array(1);
snek_object_t *second = new_snek_array(1);
// refcounts: first = 1, second = 1
snek_array_set(first, 0, second);
// refcounts: first = 1, second = 2
refcount_dec(first);
// refcounts: first = 0, second = 1
refcount_dec(second);
// refcounts: first = 0, second = 0
// all free!

We create a first array, and shove the second array inside of it. Everything here works as expected. The trouble arises when we introduce a cycle: for example, first contains second but second also contains first...

Assignment

Run the code in its current state. Notice that the assertions fail. Even though we decremented both the first and second arrays' refcounts, neither were freed (refcount = 0).

Fix the assertions to pass by updating them to match the sad reality of our current implementation.

Observe

The reason both refcounts are stuck at one after being decremented, is because when first has its refcount decremented it already had 2. So it only drops to 1, which does not trigger a "free" of the second array:

void refcount_dec(snek_object_t *obj) {
  if (obj == NULL) {
    return;
  }
  obj->refcount--;
  if (obj->refcount == 0) {
    // this doesn't happen when refcount is 1
    return refcount_free(obj);
  }
  return;
}

And because second still has 2 refcounts, it also only drops to 1, which fails to trigger a "free" of the first array.

In other words, we have a cycle, and our simple reference counting garbage collector can't handle it.