Add stack protection for recursive funcs

4 files changed, 127 insertions, 42 deletions

diff --git a/src/bootstrap/environment.c b/src/bootstrap/environment.c
index 57baea6..570c5d4 100644
--- a/src/bootstrap/environment.c
+++ b/src/bootstrap/environment.c
@@ -105,7 +105,7 @@ env_add_or_update_current(Environment *env, Object *symbol, Object *value) {
 
 Environment *
 env_extend(Environment *parent, Environment *extra) {
-    Environment *env = env_create(parent);
+    Environment *env = parent;
     for (size_t i = 0; i < extra->size; i++) {
         EnvEntry entry = extra->buf[i];
         Environment *tmp = env;
diff --git a/src/bootstrap/gc.c b/src/bootstrap/gc.c
index b63ee2b..381ab6b 100644
--- a/src/bootstrap/gc.c
+++ b/src/bootstrap/gc.c
@@ -5,38 +5,63 @@ typedef struct RootNodes {
     size_t cap;
 } RootNodes;
 
+// Stack of active environments.
+typedef struct ActiveEnvs {
+    Environment **buf;
+    size_t size;
+    size_t cap;
+} ActiveEnvs;
+
 typedef struct Environments {
     Environment *buf;
     size_t size;
     size_t cap;
 } Environments;
 
+typedef struct FreeList {
+    size_t *buf;
+    size_t size;
+    size_t cap;
+    size_t position;
+} FreeList;
+
 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;
+    Object *objects;
     size_t obj_cap;
-    size_t fl_pos;
-    size_t available_slots;
+    FreeList free_objects;
+    FreeList free_envs;
+    ActiveEnvs active_envs;
 } GC;
 
 // FIXME: small value for testing purposes
-// #define GC_INITIAL_HEAP 32
-#define GC_INITIAL_HEAP 1024 * 1.5
+// #define GC_OBJS_CAP 1024 * 1024 * 10
+// #define GC_ROOTS_CAP 1024
+// #define GC_ENVS_CAP 1024 * 1024 * 2
+#define GC_OBJS_CAP  1024 * 1024
 #define GC_ROOTS_CAP 1024 * 1024
-#define GC_ENVS_CAP 1024 * 1024
+#define GC_ENVS_CAP  1024 * 1024
 
 static GC gc;
 
+void mark_and_sweep(void);
+void dump_gc(void);
+
 Environment *
 alloc_env(void) {
-    if (gc.envs.size < gc.envs.cap) {
-        return &gc.envs.buf[gc.envs.size++];
+    if (gc.free_envs.size == 0) {
+        mark_and_sweep();
+        if (gc.free_envs.size == 0) {
+            fprintf(stderr, "NO MORE ENV MEMORY AVAILABLE WHERE IS YOUR GOD NOW MWAHAHA\n");
+            dump_gc();
+            exit(EXIT_FAILURE);
+            // TODO: grow heap tables.
+        }
     }
-    fprintf(stderr, "error: not enough room for more environments\n");
-    return NULL;
+    size_t slot = gc.free_envs.buf[gc.free_envs.position++];
+    gc.free_envs.size--;
+    return &gc.envs.buf[slot];
 }
 
 void
@@ -54,12 +79,24 @@ pop_root(void) {
 }
 
 void
+push_active_env(Environment *env) {
+    if (gc.active_envs.size == gc.active_envs.cap) {
+        gc.active_envs.cap *= 2;
+        gc.active_envs.buf = realloc(gc.active_envs.buf, gc.active_envs.cap * sizeof(Environment *));
+    }
+    gc.active_envs.buf[gc.active_envs.size++] = env;
+}
+
+Environment *
+pop_active_env(void) {
+    return gc.active_envs.buf[gc.active_envs.size--];
+}
+
+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,
+        .objects = malloc(GC_OBJS_CAP * sizeof(Object)),
+        .obj_cap = GC_OBJS_CAP,
         .envs = (Environments){
             .buf = malloc(GC_ENVS_CAP * sizeof(Environment)),
             .size = 0,
@@ -70,25 +107,43 @@ init_gc(void) {
             .size = 0,
             .cap = GC_ROOTS_CAP,
         },
+        .free_objects = (FreeList){
+            .buf = malloc(GC_OBJS_CAP * sizeof(size_t)),
+            .size = GC_OBJS_CAP,
+            .cap = GC_OBJS_CAP,
+        },
+        .free_envs = (FreeList){
+            .buf = malloc(GC_ENVS_CAP * sizeof(size_t)),
+            .size = GC_ENVS_CAP,
+            .cap = GC_ENVS_CAP,
+        },
+        .active_envs = (ActiveEnvs){
+            .buf = malloc(GC_ROOTS_CAP * sizeof(Environment*)),
+            .size = 0,
+            .cap = GC_ROOTS_CAP,
+        },
     };
 
     // The free list stores the offset from the initial position for all
     // available slots.
-    for (size_t i = 0; i < gc.obj_cap; i++) {
-        gc.free_list[i] = i;
+    for (size_t i = 0; i < GC_OBJS_CAP; i++) {
+        gc.free_objects.buf[i] = i;
+    }
+    for (size_t i = 0; i < GC_ENVS_CAP; i++) {
+        gc.free_envs.buf[i] = i;
     }
 }
 
 Object *
 get_obj(size_t offset) {
-    return &gc.obj_list[offset];
+    return &gc.objects[offset];
 }
 
 void mark_obj(Object *obj);
 
 void
 mark_environment(Environment *env) {
-    if (env->marked) {
+    if (env == NULL || env->marked) {
         return;
     }
     env->marked = true;
@@ -119,8 +174,8 @@ mark_obj(Object *obj) {
 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.active_envs.size; i++) {
+        mark_environment(gc.active_envs.buf[i]);
     }
 
     for (size_t i = 0; i < gc.roots.size; i++) {
@@ -129,28 +184,43 @@ mark_and_sweep(void) {
         }
         mark_obj(gc.roots.buf[i]);
     }
-    // dump_gc()
 
     // Reset the free list.
-    gc.fl_pos = 0;
-    gc.available_slots = 0;
+    gc.free_objects.position = 0;
+    gc.free_objects.size = 0;
+    gc.free_envs.position = 0;
+    gc.free_envs.size = 0;
 
     // Sweep.
     for (size_t i = 0; i < gc.obj_cap; i++) {
-        Object *obj = &gc.obj_list[i];
+        Object *obj = &gc.objects[i];
         if (!obj->marked) {
             // Free heap allocated memory for this object if needed.
             if (obj->type == OBJ_TYPE_SYMBOL) {
                 free(obj->symbol);
+                obj->symbol = NULL;
+                obj->symbol_n = 0;
             } else if (obj->type == OBJ_TYPE_STRING) {
                 free(obj->string);
+                obj->string = NULL;
+                obj->string_n = 0;
             }
-            gc.free_list[gc.available_slots++] = i;
+            gc.free_objects.buf[gc.free_objects.size++] = i;
         }
         obj->marked = false;
     }
-    for (size_t i = 0; i < gc.envs.size; i++) {
-        gc.envs.buf[i].marked = false;
+    for (size_t i = 0; i < gc.envs.cap; i++) {
+        Environment *env = &gc.envs.buf[i];
+        if (!env->marked) {
+            if (env->buf != NULL) {
+                free(env->buf);
+                env->buf = NULL;
+                env->size = 0;
+                env->cap = 0;
+            }
+            gc.free_envs.buf[gc.free_envs.size++] = i;
+        }
+        env->marked = false;
     }
 }
 
@@ -165,11 +235,11 @@ dump_gc(void) {
         // 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];
+            Object *obj = &gc.objects[i];
             display(obj);
             bool is_free = false;
             for (size_t j = 0; j < gc.obj_cap; j++) {
-                if (gc.free_list[j] == i) {
+                if (gc.free_objects.buf[j] == i) {
                     is_free = true;
                     break;
                 }
@@ -179,16 +249,16 @@ dump_gc(void) {
             }
             printf("\n");
         }
-        printf("FREE OBJECTS: %ld\n", gc.available_slots);
+        printf("FREE OBJECTS: %ld\n", gc.free_objects.size);
         printf("ENVIRONMENTS: %ld\n", gc.envs.size);
 }
 
 Object *
 alloc_object(ObjectType type) {
-    if (gc.available_slots == 0) {
+    if (gc.free_objects.size == 0) {
         mark_and_sweep();
-        if (gc.available_slots == 0) {
-            fprintf(stderr, "NOT MORE MEMORY AVAILABLE WHERE IS YOUR GOD NOW MWAHAHA\n");
+        if (gc.free_objects.size == 0) {
+            fprintf(stderr, "NO MORE OBJ MEMORY AVAILABLE WHERE IS YOUR GOD NOW MWAHAHA\n");
             dump_gc();
             exit(EXIT_FAILURE);
             // TODO: grow heap tables.
@@ -204,8 +274,8 @@ alloc_object(ObjectType type) {
             // later.
         }
     }
-    size_t slot = gc.free_list[gc.fl_pos++];
-    gc.available_slots--;
+    size_t slot = gc.free_objects.buf[gc.free_objects.position++];
+    gc.free_objects.size--;
     Object *obj = get_obj(slot);
     obj->type = type;
     return obj;
diff --git a/src/bootstrap/main.c b/src/bootstrap/main.c
index 66b1300..7251e60 100755
--- a/src/bootstrap/main.c
+++ b/src/bootstrap/main.c
@@ -47,6 +47,7 @@ init(void) {
     global_env = env_create(NULL);
     // TODO: make sure we create symbols and strings only once (interning
     // strings?)
+    push_active_env(global_env);
 
     // Primitive symbols.
     MAKE_ENV_VAR(global_env, "else", obj_true);
diff --git a/src/bootstrap/primitives.c b/src/bootstrap/primitives.c
index a814e40..0403e3a 100644
--- a/src/bootstrap/primitives.c
+++ b/src/bootstrap/primitives.c
@@ -5,6 +5,7 @@ Object * proc_if(Environment *env, Object *obj);
 Object *
 eval(Environment *env, Object *root) {
     Object* lambda;
+    Object* ret = NULL;
     bool recursion_active = false;
 eval_start:
     switch (root->type) {
@@ -15,7 +16,8 @@ eval_start:
         case OBJ_TYPE_BOOL:
         case OBJ_TYPE_NIL:
         case OBJ_TYPE_STRING: {
-            return root;
+            ret = root;
+            goto eval_success;
         } break;
         case OBJ_TYPE_SYMBOL: {
             Object *val = env_lookup(env, root);
@@ -26,7 +28,8 @@ eval_start:
                 });
                 return obj_err;
             }
-            return val;
+            ret = val;
+            goto eval_success;
         } break;
         case OBJ_TYPE_PAIR: {
             if (root->car->type == OBJ_TYPE_SYMBOL) {
@@ -64,7 +67,8 @@ eval_start:
                         }
                         goto eval_start;
                     }
-                    return val->proc(env, root->cdr);
+                    ret = val->proc(env, root->cdr);
+                    goto eval_success;
                 }
                 if (val->type == OBJ_TYPE_LAMBDA) {
                     lambda = val;
@@ -86,8 +90,12 @@ eval_lambda:
                 args = root->cdr;
                 Object *params = lambda->params;
                 if (!recursion_active) {
-                    env = env_extend(lambda->env, env);
                     recursion_active = true;
+                    // Protect current stack.
+                    Environment *tmp = env_create(lambda->env);
+                    push_active_env(tmp);
+                    // Extend environment.
+                    env = env_extend(tmp, env);
                 }
                 while (params != obj_nil) {
                     if (args == obj_nil) {
@@ -138,6 +146,12 @@ eval_lambda:
         .value = ERR_UNKNOWN_OBJ_TYPE,
     });
     return obj_err;
+eval_success:
+    if (recursion_active) {
+        // Remove stack protector.
+        pop_active_env();
+    }
+    return ret;
 }
 
 Object *