Sketch: 'destroyable' class types (and weak pointers for them)

[HoneyPony]

In gamedev, and especially in Godot-like scenarios, it is often very useful to have a kind of object that can be explicitly destroyed. In Godot, these are the Nodes which make up most of the game. You often want to be able to free individual nodes to remove them from the scene tree and clean up their resources. It would be very awkward to have to carefully drop each reference to a node in order to destroy it.

I've always known I wanted some kind of types that are along these lines, and here is an initial sketch of what they might look like.

@destroyable
class Example {
    var example: int = 30;
}

// Global and member variables to @destroyable classes must be weak pointers.
// This is because the object can be destroyed at any time, at which point weak
// pointers will update themselves to be nil.
var global: weak Example = nil;

class Other {
    var member: weak Example = nil;
}

// Functions and local variables can take real pointers to @destroyable classes, 
// as these variables are necessarily transient.
fun takes_example(e: Example) {
    // ...
}

fun destroying_isnt_immediate(e: Example) {
    print(e.example);
    e.destroy(); // Assume that this is the destroy method

    // The Example itself is still alive until the next GC cycle. What has changed due to the
    // destroy() call is that we can no longer obtain references to it from the weak references.
    // Because there are no global or member variables that are non-weak references, it is unlikely
    // that you will have written your code in a way that keeps the object alive forever past this
    // point.
    print(e.example);

    // This assignment of a weak reference to an already-destroyed object is equivalent to assigning
    // it to nil. This is a little counterintuitive, but the argument is that you shouldn't write code like
    // this in general.
    global = e;

    // You can also check whether a reference we are looking at has been destroyed. Again, most
    // of the time you would prefer to write your code in a way such that this doesn't matter, but it
    // is safe to do this.
    print(e.is_destroyed()); //! true
}

The implementation of these weak references is based entirely on a generational counter. The two relevant types look like this:

struct weak_ref {
    void *ptr;
    uint64_t generation;
};

struct destroyable_class {
    ps_object object;
    uint64_t generation;
    // fields...
};

Unwrapping a weak reference looks like this:

void *result = NULL;
void *ptr = weak_ref.ptr; // also do an atomic load if relevant
if(ptr) {
    if(ptr->generation == weak_ref.generation) {
        result = ptr;
    }
}

// So, if this was an or_panic, we would now panic if result was NULL.
// If this was an `else`, we would perform the else branch if result was NULL.

Destroying a weak class looks like this:

obj->generation |= 1;

In particular, odd generations are destroyed; even generations are allocated. Assigning an object to a weak pointer looks like this:

uint64_t gen = obj->generation; // Do an atomic load if relevant
if(gen  & 1) {
    // Assignment to a destroyed object is invalid.
    weak_ref.ptr = NULL;
    weak_ref.generation = 0;
}
else {
    weak_ref.ptr = obj;
    weak_ref.generation = gen;
}

The is_destroyed helper function for @destroyable classes looks like this:

ps_bool result = !!(obj->generation & 1);

Finally, the way the garbage collector visits weak pointers is likely with a new poni_gc_mark_weak() function, something like:

void poni_gc_mark_weak(struct gc *gc, void **ptr, uint64_t *generation) {
    void *as_ptr = ptr;
    uint64_t gen = *generation;

    // Nothing to mark for NULL pointer.
    if(!as_ptr) { return; }

    uint64_t obj_gen = (struct ps_destroyable*)(as_ptr)->generation;
    if(obj_gen != gen) {
        // If the pointer/object mismatch in generation, then overwrite the weak pointer itself.
       *ptr = NULL;
       *generation = 0;
       // Don't keep the object alive.
       return;
    }

    // Otherwise, mark the object normally.
    if(*(uint64_t*)(as_ptr) & 1) { return; /* already marked */ }
    gc_add_to_queue(gc, as_ptr);
    *(uint64_t*)(as_ptr) |= 1; // mark
}

Note that depending on the way the garbage collector is implemented, there is actually no need at all for an additional generation field. In particular, if these allocated objects are not themselves re-used, we could make the generation field simply be another bit in the object header. However, if we do that, ALL of the marking operations on that header will have to be atomic or operations. (In particular, with only a single bit that ever gets written to, it doesn't matter if the operation is atomic or not, so long as it appears to the GC in a consistent way. Specifically, two threads that both read the unmarked value and both write it do not fight with each other, as they are both ultimately trying to write the same value).

The other question is whether we would want to have weak pointers for regular types. These would be a little weird, as what they'd essentially do is mark an object as being alive (maybe through a third mark bit?), but not as being really alive (i.e. not the usual mark bit). Then, in the next GC cycle, those objects would be actually deleted and the weak pointers reset.

One cool thing we can do if we have these @destroyable classes is better Godot integration. Godot has types that are manually freeable, and although we won't be able to ever have truly type-safe "non-null" references to these (because any such reference could be invalidated by a free() call that occurred after the reference was created), we can have "pretty good" non-null references if we use the @destroyable classes. That is, we can still get the semantic of only storing weak pointers in globals or member variables, which goes a long way to making sure you use these types safely.

[HoneyPony]

One other feature to consider for @destroyable objects is a way to make them "immortal", maybe something like @destroyable(immortal = true).

The idea would be that such objects would be kept alive, regardless of the number of strong references to them, until destroy() was called on them. That is, such objects would be leaked if all the references to them dropped without somebody calling destroy() at some point.

In my current experimental game code, I have written a "Pool" type for managing dynamic objects, that keeps a reference to each currently alive object in an array, because code needs to hang on to a reference to them somewhere in order to keep them alive. In this proposed system, however, this would not be necessary, and the pool type itself would be less necessary.

I suppose the problem is you still need a reference to these objects in order to do anything useful with them. So my pool system would still kind of have to exist.

Something that would be helpful, then, is some convenient way to access every object of a certain @destroyable class. Maybe something like @destroyable(iterable = true)?

[HoneyPony]

One other thing to consider is that, given that it is not really possible to mix @destroyable and not in one inheritance hierarchy, a cleaner way to implement this might be to introduce a special base class Destroyable, and simply have things inherit from that.

// Builtin:
class Destroyable {
    fun destroy();
    fun is_destroyed() -> bool;
    
    // Special property: Global and member variables cannot be T or T? where
    // T: Destroyable; they may only be weak pointers to T.
}

class Example : Destroyable {
}

Of course, this requires the implementation of inheritance.