Garbage collect arrays

3 files changed, 43 insertions, 23 deletions

diff --git a/runtime/src/shed/arrays.h b/runtime/src/shed/arrays.h
new file mode 100644
index 00000000..494aaa9d
--- /dev/null
+++ b/runtime/src/shed/arrays.h
@@ -0,0 +1,12 @@
+#ifndef SHED_ARRAYS_H
+#define SHED_ARRAYS_H
+
+#include "./gc.h"
+
+struct ShedArray {
+    struct ShedGcObjectHeader object_header;
+    PatioInt size;
+    ShedObject elements[];
+};
+
+#endif
diff --git a/runtime/src/shed/gc/mark-and-sweep/gc.c b/runtime/src/shed/gc/mark-and-sweep/gc.c
index b9b6d7d8..f83ccb2a 100644
--- a/runtime/src/shed/gc/mark-and-sweep/gc.c
+++ b/runtime/src/shed/gc/mark-and-sweep/gc.c
@@ -1,6 +1,7 @@
 #include <stdbool.h>
 
 #include "../../../patio/patio.h"
+#include "../../arrays.h"
 #include "../../gc.h"
 #include "../../primitives.h"
 #include "../../std/malloc.h"
@@ -28,13 +29,25 @@ void mark(struct ShedGcObjectHeader* object) {
 
     object->mark = current_mark_value;
 
-    struct RuntimeType* runtime_type = &shed__rtti[object->runtime_type_tag];
+    struct ShedGcObjectHeader** children;
+    size_t children_count;
+    if (object->runtime_type_tag == 1) {
+        // Special handling for arrays, since they have a variable number of
+        // children.
+        struct ShedArray* shed_array = (struct ShedArray*) object;
 
-    struct ShedGcObjectHeader** children = (struct ShedGcObjectHeader**) (
-        ((void*) object) + runtime_type->children_offset
-    );
+        children = (struct ShedGcObjectHeader**) shed_array->elements;
+        children_count = shed_array->size;
+    } else {
+        struct RuntimeType* runtime_type = &shed__rtti[object->runtime_type_tag];
+
+        children = (struct ShedGcObjectHeader**) (
+            ((void*) object) + runtime_type->children_offset
+        );
+        children_count = runtime_type->children_count;
+    }
 
-    for (size_t child_index = 0; child_index < runtime_type->children_count; child_index++) {
+    for (size_t child_index = 0; child_index < children_count; child_index++) {
         mark(children[child_index]);
     }
 }
diff --git a/runtime/src/shed/namespaces/Std/Lists.c b/runtime/src/shed/namespaces/Std/Lists.c
index a7a0ac25..a803d010 100644
--- a/runtime/src/shed/namespaces/Std/Lists.c
+++ b/runtime/src/shed/namespaces/Std/Lists.c
@@ -1,27 +1,27 @@
+#include "shed/arrays.h"
 #include "shed/gc.h"
 #include "shed/ints.h"
 #include "./Lists.h"
 
 struct ShedArrayBuilder {
     struct ShedGcObjectHeader object_header;
+    // TODO: in principle, this should really be a PatioInt since the GC should
+    // assumes everything is stored in a Patio int. In practice, pointers in
+    // C are the same size as PatioInt, and indeed the GC assumes this is the
+    // case (at the time of writing at least), so this should also work.
+    struct ShedArray* array;
     PatioInt capacity;
     PatioInt size;
     bool is_owner;
-    struct ShedArray* array;
 };
 
-struct ShedArray {
-    struct ShedGcObjectHeader object_header;
-    PatioInt size;
-    ShedObject elements[];
-};
+// TODO: move other array code into `shed/arrays`?
 
 static struct ShedArray* array_copy(struct ShedArray* source, PatioInt size, PatioInt capacity) {
     struct ShedArray* array = shed__runtime__gc_alloc(
         sizeof(struct ShedArray) + sizeof(ShedObject) * capacity,
-        0
+        1
     );
-    array->object_header.mark = 0b110;
     array->size = size;
 
     for (PatioInt element_index = 0; element_index < size; element_index++) {
@@ -32,23 +32,19 @@ static struct ShedArray* array_copy(struct ShedArray* source, PatioInt size, Pat
 }
 
 ShedObject shed__runtime__namespace__Std__Lists__arrayBuilder(ShedClosurePointer closurePointer, ShedObject capacityObject) {
-    // TODO: runtime type tag / GC support (don't set mark to 0b110, set appropriate runtime type)
-
     PatioInt capacity = shed__runtime__int_value(capacityObject);
 
     struct ShedArray* array = shed__runtime__gc_alloc(
         sizeof(struct ShedArray) + sizeof(ShedObject) * capacity,
-        0
+        1
     );
-    array->object_header.mark = 0b110;
     array->size = 0;
 
-    struct ShedArrayBuilder* array_builder = shed__runtime__gc_alloc(sizeof(struct ShedArrayBuilder), 0);
-    array_builder->object_header.mark = 0b110;
+    struct ShedArrayBuilder* array_builder = shed__runtime__gc_alloc(sizeof(struct ShedArrayBuilder), 2);
+    array_builder->array = array;
     array_builder->capacity = capacity;
     array_builder->size = 0;
     array_builder->is_owner = true;
-    array_builder->array = array;
 
     return (ShedObject) array_builder;
 }
@@ -91,12 +87,11 @@ ShedObject shed__runtime__namespace__Std__Lists__method__ArrayBuilder__unsafeAdd
 
     array->elements[array_builder->size] = arg1;
 
-    struct ShedArrayBuilder* new_array_builder = shed__runtime__gc_alloc(sizeof(struct ShedArrayBuilder), 0);
-    new_array_builder->object_header.mark = 0b110;
+    struct ShedArrayBuilder* new_array_builder = shed__runtime__gc_alloc(sizeof(struct ShedArrayBuilder), 2);
+    new_array_builder->array = array;
     new_array_builder->capacity = array_builder->capacity;
     new_array_builder->size = array_builder->size + 1;
     new_array_builder->is_owner = true;
-    new_array_builder->array = array;
 
     return (ShedObject) new_array_builder;
 }