refcount.c

// TODOs offstream:
// - differences between typedeft shenanigans

// Jokes:
// - mark-and-sweep you off your feet

// For eductional purposes, should we implement
// both a mark-and-sweep, as well as a ref-count?

#include "garbage.h"

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>

// When we work with objects, we're really
// working with pointers to objects.
//
// This keeps everything the same size and
// has some nice properties later that we will see :)
typedef struct object_t *object;

typedef enum ObjectKind {
  INTEGER,
  FLOAT,
  STRING,
  VEC_3,
  TUPLE,
} object_kind_t;

typedef struct {
  size_t size;
  char *characters;
} obj_string;

typedef struct {
  object *x;
  object *y;
  object *z;
} obj_vector_3;

typedef struct {
  size_t size;
  object **elements;
} obj_tuple;

typedef union ObjectData {
  int v_int;
  float v_float;
  obj_vector_3 v_vec_3;
  obj_string v_string;
  obj_tuple v_tuple;
} object_data_t;

typedef struct object_t {
  int ref_count;
  object_kind_t obj_kind;
  object_data_t obj_data;
} object_t;

void gc_object_dec(object *ref);

void gc_object_free(object *ref) {
  object obj = *ref;

  assert(obj->ref_count == 0);

  // decrement all the things this is holding
  switch (obj->obj_kind) {
  case INTEGER:
    // Integers are allocated within the object, so nothing to free
    break;
  case FLOAT:
    // Floats are allocated within the object, so nothing to free
    break;
  case STRING: {
    // Free the allocated characters for the string.
    obj_string *str = &obj->obj_data.v_string;
    free(str->characters);
    break;
  }
  case VEC_3: {
    // We don't have to *free* the objects,
    // we simply decrement their reference counts.
    //
    // If they go to 0, decrement will handle freeing them.
    obj_vector_3 *vec = &obj->obj_data.v_vec_3;
    gc_object_dec(vec->x);
    gc_object_dec(vec->y);
    gc_object_dec(vec->z);
    break;
  }
  case TUPLE: {
    obj_tuple *tuple = &obj->obj_data.v_tuple;

    // decrement all the references in our tuple
    for (size_t i = 0; i < tuple->size; i++) {
      object *elt = tuple->elements[i];
      gc_object_dec(elt);
    }

    // (tricky to remember) Free the element list
    free(tuple->elements);

    break;
  }
  default:
    assert(false);
  }

  // Free the memory that we allocated for an object.
  free(obj);

  // Mark our object as NULL.
  // This makes sure that we can never reference it again
  // (and that we can assert that it has been freed easily)
  *ref = NULL;

  return;
}

void gc_object_inc(object *ref) {
  if (ref == NULL || *ref == NULL) {
    return;
  }

  object obj = *ref;

  // Should only increment live objects
  assert(obj->ref_count >= 1);

  obj->ref_count++;
  return;
}

void gc_object_dec(object *ref) {
  if (ref == NULL || *ref == NULL) {
    return;
  }

  object obj = *ref;
  obj->ref_count--;

  // Should never get a negative ref count
  assert(obj->ref_count >= 0);

  if (obj->ref_count == 0) {
    return gc_object_free(ref);
  }

  return;
}

object make_int(int i) {
  object obj = malloc(sizeof(object_t));
  assert(obj != NULL);

  obj->ref_count = 1;
  obj->obj_kind = INTEGER;
  obj->obj_data = (object_data_t){.v_int = i};

  return obj;
}

object make_tuple_2(object *a, object *b) {
  obj_tuple tuple = {0};

  gc_object_inc(a);
  gc_object_inc(b);

  tuple.size = 2;
  tuple.elements = malloc(sizeof(object_t) * 2);
  tuple.elements[0] = a;
  tuple.elements[1] = b;

  object obj = malloc(sizeof(object_t));
  obj->ref_count = 1;
  obj->obj_kind = TUPLE;
  obj->obj_data = (object_data_t){.v_tuple = tuple};

  return obj;
}

void test_free_int_first() {
  object i1 = make_int(1);
  object i2 = make_int(2);

  object obj = make_tuple_2(&i1, &i2);

  gc_object_inc(&obj);
  gc_object_dec(&obj);

  // Free i1 before freeing list
  gc_object_dec(&i1);
  assert(i1 != NULL);

  // Now there are no references to i1, so it should be freed.
  gc_object_dec(&obj);
  assert(obj == NULL);

  // i1 also magically gets updated!
  assert(i1 == NULL);

  // Clean up last memory
  gc_object_dec(&i2);
  assert(i2 == NULL);
}

void test_free_tuple_first() {
  object i1 = make_int(1);
  object i2 = make_int(2);

  object obj = make_tuple_2(&i1, &i2);

  gc_object_inc(&obj);
  gc_object_dec(&obj);

  gc_object_dec(&obj);
  assert(obj == NULL);

  // Free i1 after freeing list
  assert(i1 != NULL);
  gc_object_dec(&i1);
  assert(i1 == NULL);

  // Clean up last memory
  gc_object_dec(&i2);
  assert(i2 == NULL);
}

void test() {
  test_free_int_first();
  test_free_tuple_first();
}

// Plan:
// 1. Write a refcount gc
// 2. Talk about where refcount fails
// 3. Write a mark-and-sweep gc
// 4. Compare & Contrast
// (in the course): Introduce ownership as a concept