Add a working GC with mark-and-sweep

5 files changed, 193 insertions, 147 deletions

diff --git a/src/bootstrap/environment.c b/src/bootstrap/environment.c
index 78f31fb..57baea6 100644
--- a/src/bootstrap/environment.c
+++ b/src/bootstrap/environment.c
@@ -8,15 +8,18 @@ typedef struct Environment {
     EnvEntry *buf;
     size_t size;
     size_t cap;
+    bool marked;
 } Environment;
 
 static Environment *global_env;
 
 #define ENV_BUF_CAP 8
 
+Environment *alloc_env(void);
+
 Environment *
 env_create(Environment *parent) {
-    Environment *env = malloc(sizeof(Environment));
+    Environment *env = alloc_env();
     env->parent = parent;
     env->buf = NULL;
     env->size = 0;
@@ -66,7 +69,7 @@ env_update(Environment *env, Object *symbol, Object *value) {
         for (size_t i = 0; i < env->size; i++) {
             EnvEntry entry = env->buf[i];
             if (obj_eq(symbol, entry.symbol)) {
-                env->buf[i].value = obj_duplicate(value);
+                env->buf[i].value = value;
                 return obj_nil;
             }
         }
@@ -94,9 +97,9 @@ void
 env_add_or_update_current(Environment *env, Object *symbol, Object *value) {
     ssize_t index = env_index_current(env, symbol);
     if (index == -1) {
-        env_add_symbol(env, obj_duplicate(symbol), obj_duplicate(value));
+        env_add_symbol(env, symbol, value);
     } else {
-        env->buf[index].value = obj_duplicate(value);
+        env->buf[index].value = value;
     }
 }
 
@@ -115,7 +118,7 @@ env_extend(Environment *parent, Environment *extra) {
             tmp = tmp->parent;
         }
         if (!found) {
-            env_add_symbol(env, obj_duplicate(entry.symbol), obj_duplicate(entry.value));
+            env_add_symbol(env, entry.symbol, entry.value);
         }
     }
     return env;
diff --git a/src/bootstrap/gc.c b/src/bootstrap/gc.c
index 8ca99b7..6e15c63 100644
--- a/src/bootstrap/gc.c
+++ b/src/bootstrap/gc.c
@@ -5,8 +5,15 @@ typedef struct RootNodes {
     size_t cap;
 } RootNodes;
 
+typedef struct Environments {
+    Environment *buf;
+    size_t size;
+    size_t cap;
+} Environments;
+
 typedef struct GC {
     RootNodes roots;
+    Environments envs;
     Object *obj_list;
     // Free list keeps track of the offset numbers from the obj_list
     size_t *free_list;
@@ -16,11 +23,22 @@ typedef struct GC {
 } GC;
 
 // FIXME: small value for testing purposes
-#define GC_INITIAL_HEAP 16
-#define GC_ROOTS_CAP 8
+// #define GC_INITIAL_HEAP 32
+#define GC_INITIAL_HEAP 1024 * 1.5
+#define GC_ROOTS_CAP 1024 * 1024
+#define GC_ENVS_CAP 1024 * 1024
 
 static GC gc;
 
+Environment *
+alloc_env(void) {
+    if (gc.envs.size < gc.envs.cap) {
+        return &gc.envs.buf[gc.envs.size++];
+    }
+    printf("error: not enough room for more environments\n");
+    return NULL;
+}
+
 void
 push_root(Object *obj) {
     if (gc.roots.size == gc.roots.cap) {
@@ -38,13 +56,21 @@ pop_root(void) {
 void
 init_gc(void) {
     gc = (GC){
+        .free_list = malloc(GC_INITIAL_HEAP * sizeof(size_t)),
+        .obj_list = malloc(GC_INITIAL_HEAP * sizeof(Object)),
         .obj_cap = GC_INITIAL_HEAP,
         .available_slots = GC_INITIAL_HEAP,
+        .envs = (Environments){
+            .buf = malloc(GC_ENVS_CAP * sizeof(Environment)),
+            .size = 0,
+            .cap = GC_ENVS_CAP,
+        },
+        .roots = (RootNodes){
+            .buf = malloc(GC_ROOTS_CAP * sizeof(Object*)),
+            .size = 0,
+            .cap = GC_ROOTS_CAP,
+        },
     };
-    gc.free_list = malloc(GC_INITIAL_HEAP * sizeof(size_t));
-    gc.obj_list = malloc(GC_INITIAL_HEAP * sizeof(Object));
-    gc.roots.buf = malloc(GC_ROOTS_CAP * sizeof(Object*));
-    gc.roots.cap = GC_ROOTS_CAP;
 
     // The free list stores the offset from the initial position for all
     // available slots.
@@ -55,7 +81,22 @@ init_gc(void) {
 
 Object *
 get_obj(size_t offset) {
-    return gc.obj_list + offset;
+    return &gc.obj_list[offset];
+}
+
+void mark_obj(Object *obj);
+
+void
+mark_environment(Environment *env) {
+    if (env->marked) {
+        return;
+    }
+    env->marked = true;
+    for (size_t i = 0; i < env->size; i++) {
+        EnvEntry entry = env->buf[i];
+        mark_obj(entry.symbol);
+        mark_obj(entry.value);
+    }
 }
 
 void
@@ -68,17 +109,27 @@ mark_obj(Object *obj) {
         mark_obj(obj->car);
         mark_obj(obj->cdr);
     }
+    if (obj->type == OBJ_TYPE_LAMBDA) {
+        mark_obj(obj->params);
+        mark_obj(obj->body);
+        mark_environment(obj->env);
+    }
 }
 
 void
 mark_and_sweep(void) {
     // Mark.
+    for (size_t i = 0; i < gc.envs.size; i++) {
+        mark_environment(&gc.envs.buf[i]);
+    }
+
     for (size_t i = 0; i < gc.roots.size; i++) {
         if (gc.roots.buf[i]->marked) {
             continue;
         }
         mark_obj(gc.roots.buf[i]);
     }
+    // dump_gc()
 
     // Reset the free list.
     gc.fl_pos = 0;
@@ -86,40 +137,59 @@ mark_and_sweep(void) {
 
     // Sweep.
     for (size_t i = 0; i < gc.obj_cap; i++) {
-        if (!gc.obj_list[i].marked) {
+        Object *obj = &gc.obj_list[i];
+        if (!obj->marked) {
             // Free heap allocated memory for this object if needed.
-            Object obj = gc.obj_list[i];
-            if (obj.type == OBJ_TYPE_SYMBOL) {
-                free(obj.symbol);
-            } else if (obj.type == OBJ_TYPE_STRING) {
-                free(obj.string);
+            if (obj->type == OBJ_TYPE_SYMBOL) {
+                free(obj->symbol);
+            } else if (obj->type == OBJ_TYPE_STRING) {
+                free(obj->string);
             }
-
             gc.free_list[gc.available_slots++] = i;
         }
-        gc.obj_list[i].marked = false;
+        obj->marked = false;
+    }
+    for (size_t i = 0; i < gc.envs.size; i++) {
+        gc.envs.buf[i].marked = false;
     }
 }
 
+void
+dump_gc(void) {
+        printf("-------------- ROOTS -------------- \n");
+        for (size_t i = 0; i < gc.roots.size; i++) {
+            display(gc.roots.buf[i]);
+            printf("\n");
+        }
+        printf("------------- OBJECTS ------------- \n");
+        // for (size_t i = 0; i < gc.obj_cap; i++) {
+        for (size_t i = 0; i < 20; i++) {
+            printf("i: %ld -> ", i);
+            Object *obj = &gc.obj_list[i];
+            display(obj);
+            bool is_free = false;
+            for (size_t j = 0; j < gc.obj_cap; j++) {
+                if (gc.free_list[j] == i) {
+                    is_free = true;
+                    break;
+                }
+            }
+            if (is_free) {
+                printf(" [FREE]");
+            }
+            printf("\n");
+        }
+        printf("FREE OBJECTS: %ld\n", gc.available_slots);
+        printf("ENVIRONMENTS: %ld\n", gc.envs.size);
+}
+
 Object *
 alloc_object(ObjectType type) {
     if (gc.available_slots == 0) {
-        printf("triggering GC\n");
         mark_and_sweep();
         if (gc.available_slots == 0) {
-            printf("NOT MORE MEMORY AVAILABLE\n");
-            printf("-------------- ROOTS -------------- \n");
-            for (size_t i = 0; i < gc.roots.size; i++) {
-                display(gc.roots.buf[i]);
-                printf("\n");
-            }
-            printf("------------- OBJECTS ------------- \n");
-            for (size_t i = 0; i < gc.obj_cap; i++) {
-                printf("i: %ld -> ", i);
-                Object *obj = &gc.obj_list[i];
-                display(obj);
-                printf("\n");
-            }
+            printf("NOT MORE MEMORY AVAILABLE WHERE IS YOUR GOD NOW MWAHAHA\n");
+            dump_gc();
             exit(EXIT_FAILURE);
             // TODO: grow heap tables.
             // NOTE: When growing the tables, we WILL lose the pointer
diff --git a/src/bootstrap/main.c b/src/bootstrap/main.c
index ce1fdfe..66b1300 100755
--- a/src/bootstrap/main.c
+++ b/src/bootstrap/main.c
@@ -43,54 +43,56 @@ init(void) {
     push_root(obj_err);
     push_root(obj_quote);
 
-//     // Global environment.
-//     global_env = env_create(NULL);
-
-//     // Primitive symbols.
-//     MAKE_ENV_VAR(global_env, "else", obj_true);
-//     MAKE_ENV_VAR(global_env, "nil", obj_nil);
-
-//     // Primitive procedures.
-//     MAKE_ENV_PROC(global_env, "eval", proc_eval);
-//     MAKE_ENV_PROC(global_env, "quote", proc_quote);
-//     MAKE_ENV_PROC(global_env, "car", proc_car);
-//     MAKE_ENV_PROC(global_env, "cdr", proc_cdr);
-//     MAKE_ENV_PROC(global_env, "cons", proc_cons);
-//     MAKE_ENV_PROC(global_env, "list", proc_list);
-//     MAKE_ENV_PROC(global_env, "+", proc_sum);
-//     MAKE_ENV_PROC(global_env, "-", proc_sub);
-//     MAKE_ENV_PROC(global_env, "*", proc_mul);
-//     MAKE_ENV_PROC(global_env, "/", proc_div);
-//     MAKE_ENV_PROC(global_env, "%", proc_mod);
-//     MAKE_ENV_PROC(global_env, "print", proc_print);
-//     MAKE_ENV_PROC(global_env, "display", proc_display);
-//     MAKE_ENV_PROC(global_env, "newline", proc_newline);
-//     MAKE_ENV_PROC(global_env, "boolean?", proc_is_boolean);
-//     MAKE_ENV_PROC(global_env, "nil?", proc_is_nil);
-//     MAKE_ENV_PROC(global_env, "symbol?", proc_is_symbol);
-//     MAKE_ENV_PROC(global_env, "string?", proc_is_string);
-//     MAKE_ENV_PROC(global_env, "fixnum?", proc_is_fixnum);
-//     MAKE_ENV_PROC(global_env, "pair?", proc_is_pair);
-//     MAKE_ENV_PROC(global_env, "procedure?", proc_is_procedure);
-//     MAKE_ENV_PROC(global_env, "error?", proc_is_error);
-//     MAKE_ENV_PROC(global_env, "not", proc_not);
-//     MAKE_ENV_PROC(global_env, "and", proc_and);
-//     MAKE_ENV_PROC(global_env, "or", proc_or);
-//     MAKE_ENV_PROC(global_env, "if", proc_if);
-//     MAKE_ENV_PROC(global_env, "cond", proc_cond);
-//     MAKE_ENV_PROC(global_env, "<", proc_num_less_than);
-//     MAKE_ENV_PROC(global_env, "<=", proc_num_lesseq_than);
-//     MAKE_ENV_PROC(global_env, ">", proc_num_greater_than);
-//     MAKE_ENV_PROC(global_env, ">=", proc_num_greatereq_than);
-//     MAKE_ENV_PROC(global_env, "=", proc_num_equal);
-//     MAKE_ENV_PROC(global_env, "eq?", proc_equal);
-//     MAKE_ENV_PROC(global_env, "def", proc_define);
-//     MAKE_ENV_PROC(global_env, "set!", proc_set);
-//     MAKE_ENV_PROC(global_env, "lambda", proc_lambda);
-//     MAKE_ENV_PROC(global_env, "fun", proc_fun);
-
-//     // Runtime procedures.
-//     MAKE_ENV_PROC(global_env, "supress-errors", proc_supress_errors);
+    // Global environment.
+    global_env = env_create(NULL);
+    // TODO: make sure we create symbols and strings only once (interning
+    // strings?)
+
+    // Primitive symbols.
+    MAKE_ENV_VAR(global_env, "else", obj_true);
+    MAKE_ENV_VAR(global_env, "nil", obj_nil);
+
+    // Primitive procedures.
+    MAKE_ENV_PROC(global_env, "eval", proc_eval);
+    MAKE_ENV_PROC(global_env, "quote", proc_quote);
+    MAKE_ENV_PROC(global_env, "car", proc_car);
+    MAKE_ENV_PROC(global_env, "cdr", proc_cdr);
+    MAKE_ENV_PROC(global_env, "cons", proc_cons);
+    MAKE_ENV_PROC(global_env, "list", proc_list);
+    MAKE_ENV_PROC(global_env, "+", proc_sum);
+    MAKE_ENV_PROC(global_env, "-", proc_sub);
+    MAKE_ENV_PROC(global_env, "*", proc_mul);
+    MAKE_ENV_PROC(global_env, "/", proc_div);
+    MAKE_ENV_PROC(global_env, "%", proc_mod);
+    MAKE_ENV_PROC(global_env, "print", proc_print);
+    MAKE_ENV_PROC(global_env, "display", proc_display);
+    MAKE_ENV_PROC(global_env, "newline", proc_newline);
+    MAKE_ENV_PROC(global_env, "boolean?", proc_is_boolean);
+    MAKE_ENV_PROC(global_env, "nil?", proc_is_nil);
+    MAKE_ENV_PROC(global_env, "symbol?", proc_is_symbol);
+    MAKE_ENV_PROC(global_env, "string?", proc_is_string);
+    MAKE_ENV_PROC(global_env, "fixnum?", proc_is_fixnum);
+    MAKE_ENV_PROC(global_env, "pair?", proc_is_pair);
+    MAKE_ENV_PROC(global_env, "procedure?", proc_is_procedure);
+    MAKE_ENV_PROC(global_env, "error?", proc_is_error);
+    MAKE_ENV_PROC(global_env, "not", proc_not);
+    MAKE_ENV_PROC(global_env, "and", proc_and);
+    MAKE_ENV_PROC(global_env, "or", proc_or);
+    MAKE_ENV_PROC(global_env, "if", proc_if);
+    MAKE_ENV_PROC(global_env, "cond", proc_cond);
+    MAKE_ENV_PROC(global_env, "<", proc_num_less_than);
+    MAKE_ENV_PROC(global_env, "<=", proc_num_lesseq_than);
+    MAKE_ENV_PROC(global_env, ">", proc_num_greater_than);
+    MAKE_ENV_PROC(global_env, ">=", proc_num_greatereq_than);
+    MAKE_ENV_PROC(global_env, "=", proc_num_equal);
+    MAKE_ENV_PROC(global_env, "eq?", proc_equal);
+    MAKE_ENV_PROC(global_env, "def", proc_define);
+    MAKE_ENV_PROC(global_env, "set!", proc_set);
+    MAKE_ENV_PROC(global_env, "lambda", proc_lambda);
+    MAKE_ENV_PROC(global_env, "fun", proc_fun);
+
+    // Runtime procedures.
+    MAKE_ENV_PROC(global_env, "supress-errors", proc_supress_errors);
 }
 
 void
@@ -113,24 +115,6 @@ process_source(const StringView *source) {
         Object *root = parse_tree(&visitor);
         gc.roots.size = root_stack_size;
         push_root(root);
-        // printf("AFTER: %ld\n", gc.roots.size);
-        // return the stack before parsing to previous state except we now have
-        // the root object as well.
-        // printf("-----------\n");
-        // printf("ROOTS: \n");
-        // for (size_t i = 0; i < gc.roots.size; i++) {
-        //     display(gc.roots.buf[i]);
-        //     printf("\n");
-        // }
-        // printf("...........\n");
-        for (size_t i = 0; i < gc.obj_cap; i++) {
-            Object *obj = &gc.obj_list[i];
-            printf("marked? : %d  ", obj->marked);
-            printf("type: %d ", obj->type);
-            display(obj);
-            printf("\n");
-        }
-        // printf("===========\n");
         if (root == obj_err || errors_n != 0) {
             break;
         }
@@ -141,7 +125,6 @@ process_source(const StringView *source) {
             printf("\n");
         }
         pop_root();
-        // mark_and_sweep();
     }
 
     if (tokens.buf != NULL) {
diff --git a/src/bootstrap/objects.c b/src/bootstrap/objects.c
index 2bd5b1a..09076db 100644
--- a/src/bootstrap/objects.c
+++ b/src/bootstrap/objects.c
@@ -116,41 +116,6 @@ append_string(Object *obj, const StringView sv) {
     obj->string_n += sv.n;
 }
 
-Object *
-obj_duplicate(Object *obj) {
-    Object *copy = obj_err;
-    switch (obj->type) {
-        case OBJ_TYPE_BOOL:
-        case OBJ_TYPE_NIL:
-        case OBJ_TYPE_PROCEDURE:
-        case OBJ_TYPE_LAMBDA: // TODO: should we duplicate everything inside?
-        case OBJ_TYPE_ERR: {
-            copy = obj;
-        } break;
-        case OBJ_TYPE_FIXNUM: {
-            copy = make_fixnum(obj->fixnum);
-        } break;
-        case OBJ_TYPE_SYMBOL: {
-            copy = make_symbol((StringView){obj->symbol, obj->symbol_n});
-        } break;
-        case OBJ_TYPE_STRING: {
-            copy = make_string();
-            append_string(copy, (StringView){obj->string, obj->string_n});
-        } break;
-        case OBJ_TYPE_PAIR: {
-            Object *root = make_pair(obj_duplicate(obj->car), obj_nil);
-            copy = root;
-            obj = obj->cdr;
-            while (obj != obj_nil) {
-                root->cdr = make_pair(obj_duplicate(obj->car), obj_nil);
-                root = root->cdr;
-                obj = obj->cdr;
-            }
-        } break;
-    }
-    return copy;
-}
-
 void display(Object *root);
 
 void
diff --git a/src/bootstrap/primitives.c b/src/bootstrap/primitives.c
index 35208b0..abb87e7 100644
--- a/src/bootstrap/primitives.c
+++ b/src/bootstrap/primitives.c
@@ -2,7 +2,6 @@
 
 Object *
 eval(Environment* env, Object *root) {
-    return obj_nil; // DEBUG: gc
     switch (root->type) {
         case OBJ_TYPE_ERR:
         case OBJ_TYPE_PROCEDURE:
@@ -95,7 +94,8 @@ eval_lambda:
                     };
                     root = root->cdr;
                 }
-                return eval(env, root->car);
+                root = eval(env, root->car);
+                return root;
             }
         } break;
     }
@@ -630,9 +630,20 @@ proc_cons(Environment *env, Object *obj) {
         });
         return obj_err;
     }
-    Object *a = eval(env, obj->car);
-    Object *b = eval(env, obj->cdr->car);
-    return make_pair(a, b);
+    Object *head = make_pair(obj_nil, obj_nil);
+    push_root(head);
+    head->car = eval(env, obj->car);
+    if (head->car == obj_err) {
+        pop_root();
+        return obj_err;
+    }
+    head->cdr = eval(env, obj->cdr->car);
+    if (head->cdr == obj_err) {
+        pop_root();
+        return obj_err;
+    }
+    pop_root();
+    return head;
 }
 
 Object *
@@ -640,14 +651,28 @@ proc_list(Environment *env, Object *obj) {
     if (obj == obj_nil) {
         return obj_nil;
     }
-    Object *head = make_pair(eval(env, obj->car), obj_nil);
+
+    Object *head = make_pair(obj_nil, obj_nil);
+    push_root(head);
+    Object *tmp = eval(env, obj->car);
+    if (tmp == obj_err) {
+        pop_root();
+        return obj_err;
+    }
+    head->car = tmp;
     Object *curr = head;
     obj = obj->cdr;
     while (obj != obj_nil) {
-        curr->cdr = make_pair(eval(env, obj->car), obj_nil);
+        tmp = eval(env, obj->car);
+        if (tmp == obj_err) {
+            pop_root();
+            return obj_err;
+        }
+        curr->cdr = make_pair(tmp, obj_nil);
         curr = curr->cdr;
         obj = obj->cdr;
     }
+    pop_root();
     return head;
 }
 
@@ -753,8 +778,8 @@ proc_lambda(Environment *env, Object *obj) {
     }
     Object *body = obj->cdr;
     Object *fun = alloc_object(OBJ_TYPE_LAMBDA);
-    fun->params = obj_duplicate(params);
-    fun->body = obj_duplicate(body);
+    fun->params = params;
+    fun->body = body;
     fun->env = env;
     return fun;
 }
@@ -788,8 +813,8 @@ proc_fun(Environment *env, Object *obj) {
     }
     Object *body = obj->cdr->cdr;
     Object *fun = alloc_object(OBJ_TYPE_LAMBDA);
-    fun->params = obj_duplicate(params);
-    fun->body = obj_duplicate(body);
+    fun->params = params;
+    fun->body = body;
     fun->env = env;
     env_add_or_update_current(env, name, fun);
     return obj_nil;