Garbage collect arrays

22 files changed, 142 insertions, 50 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;
 }
diff --git a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDeclareNativeFunctionTests]/[method:canDeclareNativeFunction(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDeclareNativeFunctionTests]/[method:canDeclareNativeFunction(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
index ff631677..517d78e9 100644
--- a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDeclareNativeFunctionTests]/[method:canDeclareNativeFunction(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
+++ b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDeclareNativeFunctionTests]/[method:canDeclareNativeFunction(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
@@ -20,7 +20,7 @@ Locals:
 Instructions:
 
 (
-    (call (local "closurePointer__f__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (function-ptr (struct ()) (struct ()))))))) (int32-const 1)))
+    (call (local "closurePointer__f__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (function-ptr (struct ()) (struct ()))))))) (int32-const 3)))
     (
         memory-store
         pointer=(local "closurePointer__f__0")
diff --git a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineEffectTests]/[method:canGenerateCodeForDefineEffect(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineEffectTests]/[method:canGenerateCodeForDefineEffect(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
index 5d8a70a1..f1fa118c 100644
--- a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineEffectTests]/[method:canGenerateCodeForDefineEffect(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
+++ b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineEffectTests]/[method:canGenerateCodeForDefineEffect(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
@@ -27,7 +27,7 @@ Compilation unit elements:
     return-type=int
     body=(
         (call (local "gcRootStackIndex__0") "shed__runtime__gc_get_root_stack_index" ())
-        (call (local "effectHandlerMethod__0") "shed__runtime__effects_find_handler_method" ((int-const 1) (int-const 0)))
+        (call (local "effectHandlerMethod__0") "shed__runtime__effects_find_handler_method" ((int-const 3) (int-const 0)))
         (int-to-data-ptr (local "closurePointer__1") (local "effectHandlerMethod__0"))
         (
             memory-load
@@ -48,7 +48,7 @@ Compilation unit elements:
     return-type=int
     body=(
         (call (local "gcRootStackIndex__0") "shed__runtime__gc_get_root_stack_index" ())
-        (call (local "effectHandlerMethod__0") "shed__runtime__effects_find_handler_method" ((int-const 1) (int-const 1)))
+        (call (local "effectHandlerMethod__0") "shed__runtime__effects_find_handler_method" ((int-const 3) (int-const 1)))
         (int-to-data-ptr (local "closurePointer__1") (local "effectHandlerMethod__0"))
         (
             memory-load
@@ -73,7 +73,7 @@ Locals:
 Instructions:
 
 (
-    (call (local "userDefinedEffectPointer__State__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (int int)))))) (int32-const 2)))
+    (call (local "userDefinedEffectPointer__State__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (int int)))))) (int32-const 4)))
     (
         memory-store
         pointer=(local "userDefinedEffectPointer__State__0")
@@ -88,7 +88,7 @@ Instructions:
         offset=(1 1)
         value=(int-const 0)
     )
-    (call (local "closurePointer__read__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (function-ptr (struct ()) (struct ()))))))) (int32-const 3)))
+    (call (local "closurePointer__read__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (function-ptr (struct ()) (struct ()))))))) (int32-const 5)))
     (
         memory-store
         pointer=(local "closurePointer__read__0")
@@ -104,7 +104,7 @@ Instructions:
         offset=(1 0)
         value=(local "userDefinedMethod__read__0")
     )
-    (call (local "closurePointer__write__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (function-ptr (struct ()) (struct ()))))))) (int32-const 3)))
+    (call (local "closurePointer__write__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (function-ptr (struct ()) (struct ()))))))) (int32-const 5)))
     (
         memory-store
         pointer=(local "closurePointer__write__0")
diff --git a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineFunctionTests]/[method:canCaptureFreeVariablesThatAreSetAfterDefinition(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineFunctionTests]/[method:canCaptureFreeVariablesThatAreSetAfterDefinition(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
index d1cba7b9..3d416b9f 100644
--- a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineFunctionTests]/[method:canCaptureFreeVariablesThatAreSetAfterDefinition(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
+++ b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineFunctionTests]/[method:canCaptureFreeVariablesThatAreSetAfterDefinition(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
@@ -61,7 +61,7 @@ Locals:
 Instructions:
 
 (
-    (call (local "closurePointer__f__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (function-ptr (struct ()) (struct (int int)))))))) (int32-const 1)))
+    (call (local "closurePointer__f__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (function-ptr (struct ()) (struct (int int)))))))) (int32-const 3)))
     (
         memory-store
         pointer=(local "closurePointer__f__0")
diff --git a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineFunctionTests]/[method:canDefineMinimalFunction(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineFunctionTests]/[method:canDefineMinimalFunction(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
index 0ac1f3f9..62db57f4 100644
--- a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineFunctionTests]/[method:canDefineMinimalFunction(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
+++ b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineFunctionTests]/[method:canDefineMinimalFunction(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
@@ -46,7 +46,7 @@ Locals:
 Instructions:
 
 (
-    (call (local "closurePointer__f__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (function-ptr (struct ()) (struct ()))))))) (int32-const 1)))
+    (call (local "closurePointer__f__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (function-ptr (struct ()) (struct ()))))))) (int32-const 3)))
     (
         memory-store
         pointer=(local "closurePointer__f__0")
diff --git a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineFunctionTests]/[method:effectHandlerMethodSwapsEffectHandlerInBody(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineFunctionTests]/[method:effectHandlerMethodSwapsEffectHandlerInBody(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
index 5c5edca1..fb905480 100644
--- a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineFunctionTests]/[method:effectHandlerMethodSwapsEffectHandlerInBody(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
+++ b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineFunctionTests]/[method:effectHandlerMethodSwapsEffectHandlerInBody(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
@@ -69,7 +69,7 @@ Locals:
 Instructions:
 
 (
-    (call (local "closurePointer__f__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (function-ptr (struct (data-ptr)) (struct ()))))))) (int32-const 1)))
+    (call (local "closurePointer__f__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (function-ptr (struct (data-ptr)) (struct ()))))))) (int32-const 3)))
     (
         memory-store
         pointer=(local "closurePointer__f__0")
diff --git a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineFunctionTests]/[method:immutableFreeVariablesAreStoredInAndLoadedFromEnvironment(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineFunctionTests]/[method:immutableFreeVariablesAreStoredInAndLoadedFromEnvironment(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
index 5c22c1e9..e970ace9 100644
--- a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineFunctionTests]/[method:immutableFreeVariablesAreStoredInAndLoadedFromEnvironment(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
+++ b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineFunctionTests]/[method:immutableFreeVariablesAreStoredInAndLoadedFromEnvironment(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
@@ -61,7 +61,7 @@ Locals:
 Instructions:
 
 (
-    (call (local "closurePointer__f__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (function-ptr (struct ()) (struct (int int)))))))) (int32-const 1)))
+    (call (local "closurePointer__f__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (function-ptr (struct ()) (struct (int int)))))))) (int32-const 3)))
     (
         memory-store
         pointer=(local "closurePointer__f__0")
diff --git a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineFunctionTests]/[method:pointersToFreeMutableVariablesAreStoredInAndLoadedFromEnvironment(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineFunctionTests]/[method:pointersToFreeMutableVariablesAreStoredInAndLoadedFromEnvironment(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
index a97ac2d8..f8b24821 100644
--- a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineFunctionTests]/[method:pointersToFreeMutableVariablesAreStoredInAndLoadedFromEnvironment(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
+++ b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineFunctionTests]/[method:pointersToFreeMutableVariablesAreStoredInAndLoadedFromEnvironment(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
@@ -61,7 +61,7 @@ Locals:
 Instructions:
 
 (
-    (call (local "closurePointer__f__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (function-ptr (struct ()) (struct (data-ptr data-ptr)))))))) (int32-const 1)))
+    (call (local "closurePointer__f__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (function-ptr (struct ()) (struct (data-ptr data-ptr)))))))) (int32-const 3)))
     (
         memory-store
         pointer=(local "closurePointer__f__0")
diff --git a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineFunctionTests]/[method:positionalAndNamedParamsAreDefined(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineFunctionTests]/[method:positionalAndNamedParamsAreDefined(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
index ff563430..d3329bef 100644
--- a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineFunctionTests]/[method:positionalAndNamedParamsAreDefined(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
+++ b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineFunctionTests]/[method:positionalAndNamedParamsAreDefined(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
@@ -69,7 +69,7 @@ Locals:
 Instructions:
 
 (
-    (call (local "closurePointer__f__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (function-ptr (struct ()) (struct (int int)))))))) (int32-const 1)))
+    (call (local "closurePointer__f__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (function-ptr (struct ()) (struct (int int)))))))) (int32-const 3)))
     (
         memory-store
         pointer=(local "closurePointer__f__0")
diff --git a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineStructTests]/[method:canGenerateCodeForDefineStructNonPositional(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineStructTests]/[method:canGenerateCodeForDefineStructNonPositional(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
index 60808ec5..407e5776 100644
--- a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineStructTests]/[method:canGenerateCodeForDefineStructNonPositional(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
+++ b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineStructTests]/[method:canGenerateCodeForDefineStructNonPositional(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
@@ -20,7 +20,7 @@ Compilation unit elements:
     return-type=int
     body=(
         (call (local "gcRootStackIndex__0") "shed__runtime__gc_get_root_stack_index" ())
-        (call (local "structValuePointer__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (int int)))))) (int32-const 1)))
+        (call (local "structValuePointer__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (int int)))))) (int32-const 3)))
         (
             memory-store
             pointer=(local "structValuePointer__0")
@@ -40,7 +40,7 @@ Compilation unit elements:
             pointer=(local "structValuePointer__0")
             layout=(struct ((struct (data-ptr int32 int32)) (struct (int int))))
             offset=(0 2)
-            value=(int-const 1)
+            value=(int-const 3)
         )
         (
             memory-store
@@ -68,7 +68,7 @@ Locals:
 Instructions:
 
 (
-    (call (local "closurePointer__User__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (function-ptr (struct ()) (struct ()))))))) (int32-const 2)))
+    (call (local "closurePointer__User__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (function-ptr (struct ()) (struct ()))))))) (int32-const 4)))
     (
         memory-store
         pointer=(local "closurePointer__User__0")
diff --git a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineStructTests]/[method:canGenerateCodeForDefineStructPositional(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineStructTests]/[method:canGenerateCodeForDefineStructPositional(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
index 58661943..055a0733 100644
--- a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineStructTests]/[method:canGenerateCodeForDefineStructPositional(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
+++ b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioDefineStructTests]/[method:canGenerateCodeForDefineStructPositional(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
@@ -20,7 +20,7 @@ Compilation unit elements:
     return-type=int
     body=(
         (call (local "gcRootStackIndex__0") "shed__runtime__gc_get_root_stack_index" ())
-        (call (local "structValuePointer__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (int int)))))) (int32-const 1)))
+        (call (local "structValuePointer__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (int int)))))) (int32-const 3)))
         (
             memory-store
             pointer=(local "structValuePointer__0")
@@ -40,7 +40,7 @@ Compilation unit elements:
             pointer=(local "structValuePointer__0")
             layout=(struct ((struct (data-ptr int32 int32)) (struct (int int))))
             offset=(0 2)
-            value=(int-const 1)
+            value=(int-const 3)
         )
         (
             memory-store
@@ -68,7 +68,7 @@ Locals:
 Instructions:
 
 (
-    (call (local "closurePointer__User__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (function-ptr (struct ()) (struct ()))))))) (int32-const 2)))
+    (call (local "closurePointer__User__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (function-ptr (struct ()) (struct ()))))))) (int32-const 4)))
     (
         memory-store
         pointer=(local "closurePointer__User__0")
diff --git a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioNamespaceTests]/[method:canDefineNamespace(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioNamespaceTests]/[method:canDefineNamespace(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
index b6c7c25e..2f6aa036 100644
--- a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioNamespaceTests]/[method:canDefineNamespace(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
+++ b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioNamespaceTests]/[method:canDefineNamespace(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
@@ -46,7 +46,7 @@
         locals=((val "namespaceValue__0" data-ptr) (val "closure__f__0" int) (val "closurePointer__f__0" data-ptr))
         return-type=void
         body=(
-            (call (local "namespaceValue__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (int int)))))) (int32-const 1)))
+            (call (local "namespaceValue__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (int int)))))) (int32-const 3)))
             (
                 memory-store
                 pointer=(local "namespaceValue__0")
@@ -68,7 +68,7 @@
                 offset=()
                 value=(local "namespaceValue__0")
             )
-            (call (local "closurePointer__f__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (function-ptr (struct ()) (struct ()))))))) (int32-const 2)))
+            (call (local "closurePointer__f__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (function-ptr (struct ()) (struct ()))))))) (int32-const 4)))
             (
                 memory-store
                 pointer=(local "closurePointer__f__0")
diff --git a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioSwitchTests]/[method:canGenerateCodeForSwitchWithSingleResult(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioSwitchTests]/[method:canGenerateCodeForSwitchWithSingleResult(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
index 1095843e..bb3f18e3 100644
--- a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioSwitchTests]/[method:canGenerateCodeForSwitchWithSingleResult(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
+++ b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioSwitchTests]/[method:canGenerateCodeForSwitchWithSingleResult(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
@@ -42,7 +42,7 @@ Instructions:
         (
             (
                 case
-                1
+                3
                 (
                     block
                     (
@@ -55,7 +55,7 @@ Instructions:
             )
             (
                 case
-                2
+                4
                 (
                     block
                     (
diff --git a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioTryTests]/[method:canGenerateCodeForTry(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioTryTests]/[method:canGenerateCodeForTry(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
index c42d7218..c581add5 100644
--- a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioTryTests]/[method:canGenerateCodeForTry(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
+++ b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioTryTests]/[method:canGenerateCodeForTry(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
@@ -34,7 +34,7 @@ Locals:
 Instructions:
 
 (
-    (call (local "effectHandler__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (data-ptr (struct (int int int)))))))) (int32-const 1)))
+    (call (local "effectHandler__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (data-ptr (struct (int int int)))))))) (int32-const 3)))
     (
         memory-store
         pointer=(local "effectHandler__0")
diff --git a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioTryTests]/[method:effectHandlerIsPoppedBeforeReturn(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioTryTests]/[method:effectHandlerIsPoppedBeforeReturn(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
index ff7ae670..20d6c786 100644
--- a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioTryTests]/[method:effectHandlerIsPoppedBeforeReturn(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
+++ b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioTryTests]/[method:effectHandlerIsPoppedBeforeReturn(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
@@ -46,7 +46,7 @@ Locals:
 Instructions:
 
 (
-    (call (local "effectHandler__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (data-ptr (struct (int)))))))) (int32-const 1)))
+    (call (local "effectHandler__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (data-ptr (struct (int)))))))) (int32-const 3)))
     (
         memory-store
         pointer=(local "effectHandler__0")
diff --git a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioTupleCreateTests]/[method:canGenerateCodeForTupleCreate(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioTupleCreateTests]/[method:canGenerateCodeForTupleCreate(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
index c70ed9b6..4c146e20 100644
--- a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioTupleCreateTests]/[method:canGenerateCodeForTupleCreate(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
+++ b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.shidtopatio.ShidToPatioTupleCreateTests]/[method:canGenerateCodeForTupleCreate(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
@@ -20,7 +20,7 @@ Instructions:
     (local-store (local "tupleElement__2__0") (local "d"))
     (local-store (local "tupleElement__1__0") (local "c"))
     (local-store (local "tupleElement__0__0") (local "b"))
-    (call (local "tuplePointer__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (int int int)))))) (int32-const 1)))
+    (call (local "tuplePointer__0") "shed__runtime__gc_alloc" ((int-const (byte-size-of (struct ((struct (data-ptr int32 int32)) (struct (int int int)))))) (int32-const 3)))
     (
         memory-store
         pointer=(local "tuplePointer__0")
diff --git a/src/main/java/org/shedlang/compiler/shidtopatio/ArrayBuilderRuntimeType.java b/src/main/java/org/shedlang/compiler/shidtopatio/ArrayBuilderRuntimeType.java
new file mode 100644
index 00000000..5cb8000a
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/shidtopatio/ArrayBuilderRuntimeType.java
@@ -0,0 +1,35 @@
+package org.shedlang.compiler.shidtopatio;
+
+import org.shedlang.compiler.patio.types.PatioDataLayout;
+import org.shedlang.compiler.patio.types.PatioDataLayouts;
+
+import java.util.List;
+
+public class ArrayBuilderRuntimeType implements RuntimeType {
+    public static final ArrayBuilderRuntimeType INSTANCE = new ArrayBuilderRuntimeType();
+
+    private ArrayBuilderRuntimeType() {
+    }
+
+    @Override
+    public PatioDataLayout layout() {
+        return ShidToPatioGc.gcObjectDataLayout(
+            PatioDataLayouts.struct(List.of(
+                PatioDataLayouts.INT,
+                PatioDataLayouts.INT,
+                PatioDataLayouts.INT,
+                PatioDataLayouts.BOOL
+            ))
+        );
+    }
+
+    @Override
+    public List<Integer> gcChildrenOffset() {
+        return ShidToPatioGc.gcObjectOffset(List.of());
+    }
+
+    @Override
+    public int gcChildrenCount() {
+        return 1;
+    }
+}
diff --git a/src/main/java/org/shedlang/compiler/shidtopatio/ArrayRuntimeType.java b/src/main/java/org/shedlang/compiler/shidtopatio/ArrayRuntimeType.java
new file mode 100644
index 00000000..bc977526
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/shidtopatio/ArrayRuntimeType.java
@@ -0,0 +1,30 @@
+package org.shedlang.compiler.shidtopatio;
+
+import org.shedlang.compiler.patio.types.PatioDataLayout;
+import org.shedlang.compiler.patio.types.PatioDataLayouts;
+
+import java.util.List;
+
+public class ArrayRuntimeType implements RuntimeType {
+    public static final ArrayRuntimeType INSTANCE = new ArrayRuntimeType();
+
+    private ArrayRuntimeType() {
+    }
+
+    @Override
+    public PatioDataLayout layout() {
+        // TODO: separate out runtime type from the info needed by RTTI
+        return PatioDataLayouts.struct(List.of());
+    }
+
+    @Override
+    public List<Integer> gcChildrenOffset() {
+        return List.of();
+    }
+
+    @Override
+    public int gcChildrenCount() {
+        // This is a lie! We special case arrays in the runtime.
+        return 0;
+    }
+}
diff --git a/src/main/java/org/shedlang/compiler/shidtopatio/ShidToPatioContext.java b/src/main/java/org/shedlang/compiler/shidtopatio/ShidToPatioContext.java
index 546a6ccd..87e5ff61 100644
--- a/src/main/java/org/shedlang/compiler/shidtopatio/ShidToPatioContext.java
+++ b/src/main/java/org/shedlang/compiler/shidtopatio/ShidToPatioContext.java
@@ -48,6 +48,13 @@ public record ShidToPatioContext(
             // Ensure that scalars have tag of 0: this is relied on in the
             // runtime (for instance, when allocating ints and strings).
             context = context.addRuntimeTypeTag(ScalarRuntimeType.INSTANCE);
+
+            // Ensure that arrays have tag of 1.
+            context = context.addRuntimeTypeTag(ArrayRuntimeType.INSTANCE);
+
+            // Ensure that array builders have tag of 2.
+            context = context.addRuntimeTypeTag(ArrayBuilderRuntimeType.INSTANCE);
+
             context = generateStructTags(context);
             context = generateEffectTags(context);
 
diff --git a/src/test/java/org/shedlang/compiler/shidtopatio/ShidToPatioDefineStructTests.java b/src/test/java/org/shedlang/compiler/shidtopatio/ShidToPatioDefineStructTests.java
index cb9268fb..f206fb09 100644
--- a/src/test/java/org/shedlang/compiler/shidtopatio/ShidToPatioDefineStructTests.java
+++ b/src/test/java/org/shedlang/compiler/shidtopatio/ShidToPatioDefineStructTests.java
@@ -88,7 +88,7 @@ public class ShidToPatioDefineStructTests {
         context = ShidToPatio.generateInstruction(instruction1, context);
         context = ShidToPatio.generateInstruction(instruction2, context);
 
-        assertThat(context.structTag(structType1), equalTo(1));
-        assertThat(context.structTag(structType2), equalTo(2));
+        assertThat(context.structTag(structType1), equalTo(3));
+        assertThat(context.structTag(structType2), equalTo(4));
     }
 }