Chapter 26.1, 26.2, 26.3, and 26.4

11 files changed, 160 insertions, 0 deletions

diff --git a/clox/src/common.h b/clox/src/common.h
index 5cd0cf4..6dd187a 100644
--- a/clox/src/common.h
+++ b/clox/src/common.h
@@ -8,6 +8,9 @@
 #define DEBUG_PRINT_CODE
 #define DEBUG_TRACE_EXECUTION
 
+#define DEBUG_STRESS_GC
+#define DEBUG_LOG_GC
+
 #define UINT8_COUNT (UINT8_MAX + 1)
 
 #endif
diff --git a/clox/src/compiler.c b/clox/src/compiler.c
index 75ed697..f31d015 100644
--- a/clox/src/compiler.c
+++ b/clox/src/compiler.c
@@ -4,6 +4,7 @@
 
 #include "common.h"
 #include "compiler.h"
+#include "memory.h"
 #include "scanner.h"
 
 #ifdef DEBUG_PRINT_CODE
@@ -827,3 +828,11 @@ ObjFunction *compile(const char *source) {
   ObjFunction *function = endCompiler();
   return parser.hadError ? NULL : function;
 }
+
+void markCompilerRoots() {
+  Compiler *compiler = current;
+  while (compiler != NULL) {
+    markObject((Obj *)compiler->function);
+    compiler = compiler->enclosing;
+  }
+}
diff --git a/clox/src/compiler.h b/clox/src/compiler.h
index 7de1c20..37e159d 100644
--- a/clox/src/compiler.h
+++ b/clox/src/compiler.h
@@ -5,5 +5,6 @@
 #include "vm.h"
 
 ObjFunction *compile(const char *source);
+void markCompilerRoots();
 
 #endif
diff --git a/clox/src/memory.c b/clox/src/memory.c
index 1db1c61..7d403d1 100644
--- a/clox/src/memory.c
+++ b/clox/src/memory.c
@@ -1,9 +1,21 @@
 #include <stdlib.h>
 
+#include "compiler.h"
 #include "memory.h"
 #include "vm.h"
 
+#ifdef DEBUG_LOG_GC
+#include "debug.h"
+#include <stdio.h>
+#endif
+
 void *reallocate(void *pointer, size_t oldSize, size_t newSize) {
+  if (newSize > oldSize) {
+#ifdef DEBUG_STRESS_GC
+    collectGarbage();
+#endif
+  }
+
   if (newSize == 0) {
     free(pointer);
     return NULL;
@@ -15,7 +27,76 @@ void *reallocate(void *pointer, size_t oldSize, size_t newSize) {
   return result;
 }
 
+void markObject(Obj *object) {
+  if (object == NULL)
+    return;
+  if (object->isMarked)
+    return;
+
+#ifdef DEBUG_LOG_GC
+  printf("%p mark ", (void *)object);
+  printValue(OBJ_VAL(object));
+  printf("\n");
+#endif
+  object->isMarked = true;
+
+  if (vm.grayCapacity < vm.grayCount + 1) {
+    vm.grayCapacity = GROW_CAPACITY(vm.grayCapacity);
+    vm.grayStack =
+        (Obj **)realloc(vm.grayStack, sizeof(Obj *) * vm.grayCapacity);
+    if (vm.grayStack == NULL)
+      exit(1);
+  }
+
+  vm.grayStack[vm.grayCount++] = object;
+}
+
+void markValue(Value value) {
+  if (IS_OBJ(value))
+    markObject(AS_OBJ(value));
+}
+
+static void markArray(ValueArray *array) {
+  for (int i = 0; i < array->count; i++) {
+    markValue(array->values[i]);
+  }
+}
+
+static void blackenObject(Obj *object) {
+#ifdef DEBUG_LOG_GC
+  printf("%p blacken ", (void *)object);
+  printValue(OBJ_VAL(object));
+  printf("\n");
+#endif
+  switch (object->type) {
+  case OBJ_CLOSURE: {
+    ObjClosure *closure = (ObjClosure *)object;
+    markObject((Obj *)closure->function);
+    for (int i = 0; i < closure->upvalueCount; i++) {
+      markObject((Obj *)closure->upvalues[i]);
+    }
+    break;
+  }
+  case OBJ_FUNCTION: {
+    ObjFunction *function = (ObjFunction *)object;
+    markObject((Obj *)function->name);
+    markArray(&function->chunk.constants);
+    break;
+  }
+  case OBJ_UPVALUE:
+    markValue(((ObjUpvalue *)object)->closed);
+    break;
+  case OBJ_NATIVE:
+  case OBJ_STRING:
+    break;
+  }
+}
+
 static void freeObject(Obj *object) {
+#ifdef DEBUG_LOG_GC
+  printf("%p free type %d\n", (void *)object, object->type);
+#endif // DEBUG_LOG_GC
+
   switch (object->type) {
   case OBJ_CLOSURE: {
     ObjClosure *closure = (ObjClosure *)object;
@@ -44,6 +125,44 @@ static void freeObject(Obj *object) {
   }
 }
 
+static void markRoots() {
+  for (Value *slot = vm.stack; slot < vm.stackTop; slot++) {
+    markValue(*slot);
+  }
+
+  for (int i = 0; i < vm.frameCount; i++) {
+    markObject((Obj *)vm.frames[i].closure);
+  }
+
+  for (ObjUpvalue *upvalue = vm.openUpvalues; upvalue != NULL;
+       upvalue = upvalue->next) {
+    markObject((Obj *)upvalue);
+  }
+
+  markTable(&vm.globals);
+  markCompilerRoots();
+}
+
+static void traceReferences() {
+  while (vm.grayCount > 0) {
+    Obj *object = vm.grayStack[--vm.grayCount];
+    blackenObject(object);
+  }
+}
+
+void collectGarbage() {
+#ifdef DEBUG_LOG_GC
+  printf("-- gc begin\n");
+#endif
+
+  markRoots();
+  traceReferences();
+
+#ifdef DEBUG_LOG_GC
+  printf("-- gd end\n");
+#endif
+}
+
 void freeObjects() {
   Obj *object = vm.objects;
   while (object != NULL) {
@@ -51,4 +170,6 @@ void freeObjects() {
     freeObject(object);
     object = next;
   }
+
+  free(vm.grayStack);
 }
diff --git a/clox/src/memory.h b/clox/src/memory.h
index f7946f6..b1a8327 100644
--- a/clox/src/memory.h
+++ b/clox/src/memory.h
@@ -19,6 +19,9 @@
   reallocate(pointer, sizeof(type) * (oldCount), 0)
 
 void *reallocate(void *pointer, size_t oldSize, size_t newSize);
+void markObject(Obj *object);
+void markValue(Value value);
+void collectGarbage();
 void freeObjects();
 
 #endif
diff --git a/clox/src/object.c b/clox/src/object.c
index 31550ae..5f2bdde 100644
--- a/clox/src/object.c
+++ b/clox/src/object.c
@@ -13,9 +13,15 @@
 static Obj *allocateObject(size_t size, ObjType type) {
   Obj *object = (Obj *)reallocate(NULL, 0, size);
   object->type = type;
+  object->isMarked = false;
 
   object->next = vm.objects;
   vm.objects = object;
+
+#ifdef DEBUG_LOG_GC
+  printf("%p allocate %zu for %d", (void *)object, size, type);
+#endif
+
   return object;
 }
 
diff --git a/clox/src/object.h b/clox/src/object.h
index e6b842d..36ec034 100644
--- a/clox/src/object.h
+++ b/clox/src/object.h
@@ -28,6 +28,7 @@ typedef enum {
 
 struct Obj {
   ObjType type;
+  bool isMarked;
   struct Obj *next;
 };
 
diff --git a/clox/src/table.c b/clox/src/table.c
index 5b6f3f9..ae34ab0 100644
--- a/clox/src/table.c
+++ b/clox/src/table.c
@@ -140,3 +140,11 @@ ObjString *tableFindString(Table *table, const char *chars, int length,
     index = (index + 1) % table->capacity;
   }
 }
+
+void markTable(Table *table) {
+  for (int i = 0; i < table->capacity; i++) {
+    Entry *entry = &table->entries[i];
+    markObject((Obj *)entry->key);
+    markValue(entry->value);
+  }
+}
diff --git a/clox/src/table.h b/clox/src/table.h
index b4c3271..b2bf7a3 100644
--- a/clox/src/table.h
+++ b/clox/src/table.h
@@ -23,5 +23,6 @@ bool tableDelete(Table *table, ObjString *key);
 void tableAddAll(Table *from, Table *to);
 ObjString *tableFindString(Table *talbe, const char *chars, int length,
                            uint32_t hash);
+void markTable(Table *table);
 
 #endif
diff --git a/clox/src/vm.c b/clox/src/vm.c
index b11a52a..6dfd600 100644
--- a/clox/src/vm.c
+++ b/clox/src/vm.c
@@ -56,6 +56,10 @@ void initVM() {
   resetStack();
   vm.objects = NULL;
 
+  vm.grayCount = 0;
+  vm.grayCapacity = 0;
+  vm.grayStack = NULL;
+
   initTable(&vm.globals);
   initTable(&vm.strings);
 
diff --git a/clox/src/vm.h b/clox/src/vm.h
index 08706a3..61fe45a 100644
--- a/clox/src/vm.h
+++ b/clox/src/vm.h
@@ -25,6 +25,9 @@ typedef struct {
   Table strings;
   ObjUpvalue *openUpvalues;
   Obj *objects;
+  int grayCount;
+  int grayCapacity;
+  Obj **grayStack;
 } VM;
 
 typedef enum {