From a31eff3926b4355ab9a4d7a76b0007fae0dd68b2 Mon Sep 17 00:00:00 2001
From: Bad Diode <bd@badd10de.dev>
Date: Sat, 30 Oct 2021 15:36:04 +0200
Subject: Add dead code elimination to AST tree

---
 src/parser.c | 76 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++---
 src/parser.h |  2 ++
 2 files changed, 75 insertions(+), 3 deletions(-)

diff --git a/src/parser.c b/src/parser.c
index 3e6abc2..d1a5e7a 100644
--- a/src/parser.c
+++ b/src/parser.c
@@ -459,6 +459,50 @@ check_object_scope(Environment *env, Object *obj, Errors *errors) {
     }
 }
 
+void
+remove_unused_expr(Object *obj) {
+    if (obj == NULL) {
+        return;
+    }
+    switch (obj->type) {
+        case OBJ_TYPE_DEF:
+        case OBJ_TYPE_SET: {
+            remove_unused_expr(obj->var_expr);
+        } break;
+        case OBJ_TYPE_IF: {
+            remove_unused_expr(obj->condition);
+            remove_unused_expr(obj->expr_true);
+            remove_unused_expr(obj->expr_false);
+        } break;
+        case OBJ_TYPE_PAIR: {
+            remove_unused_expr(obj->head);
+            remove_unused_expr(obj->tail);
+        } break;
+        case OBJ_TYPE_LAMBDA: {
+            Object **new_body = NULL;
+            array_init(new_body, 0);
+            for (size_t i = 0; i < array_size(obj->body); i++) {
+                Object *expr = obj->body[i];
+                if (i != array_size(obj->body) - 1) {
+                    if (IS_FIXNUM(expr) ||
+                        IS_STRING(expr) ||
+                        IS_SYMBOL(expr) ||
+                        IS_LAMBDA(expr) ||
+                        IS_BOOL(expr)   ||
+                        IS_NIL(expr)) {
+                        continue;
+                    }
+                }
+                remove_unused_expr(expr);
+                array_push(new_body, expr);
+            }
+            array_free(obj->body);
+            obj->body = new_body;
+        } break;
+        default: break;
+    }
+}
+
 Root *
 parse(Token *tokens, Errors *errors) {
     array_init(roots, 0);
@@ -472,9 +516,8 @@ parse(Token *tokens, Errors *errors) {
     // Build initial ASTs. This also ensures the core grammar is correct.
     while (has_next_token(&parser)) {
         Object *root = parse_tree(&parser, errors);
-        OBJ_PRINT(root);
         if (errors->n != 0) {
-            break;
+            return NULL;
         }
         array_push(roots, root);
     }
@@ -498,9 +541,36 @@ parse(Token *tokens, Errors *errors) {
     for (size_t i = 0; i < array_size(roots); i++) {
         Object *root = roots[i];
         check_object_scope(global_env, root, errors);
+        if (errors->n != 0) {
+            return NULL;
+        }
+    }
+
+    // Remove unnecessary statements.
+    Root *final_roots = NULL;
+    array_init(final_roots, 0);
+    for (size_t i = 0; i < array_size(roots); i++) {
+        Object *root = roots[i];
+        if (i != array_size(roots) - 1) {
+            if (IS_FIXNUM(root) ||
+                IS_STRING(root) ||
+                IS_SYMBOL(root) ||
+                IS_LAMBDA(root) ||
+                IS_BOOL(root)   ||
+                IS_NIL(root)) {
+                continue;
+            }
+        }
+        array_push(final_roots, root);
+
+        remove_unused_expr(root);
+        if (errors->n != 0) {
+            return NULL;
+        }
     }
+    array_free(roots);
+    roots = final_roots;
 
-    // TODO: Remove unnecessary statements.
     return roots;
 }
 
diff --git a/src/parser.h b/src/parser.h
index dff40d8..01f53b0 100755
--- a/src/parser.h
+++ b/src/parser.h
@@ -108,6 +108,8 @@ void free_objects(void);
 #define IS_NIL(VAL)    ((VAL)->type == OBJ_TYPE_NIL)
 #define IS_TRUE(VAL)   ((VAL)->type != OBJ_TYPE_FALSE)
 #define IS_FALSE(VAL)  ((VAL)->type == OBJ_TYPE_FALSE)
+#define IS_BOOL(VAL)   \
+    (((VAL)->type == OBJ_TYPE_FALSE) || ((VAL)->type == OBJ_TYPE_TRUE))
 #define IS_FIXNUM(VAL) ((VAL)->type == OBJ_TYPE_FIXNUM)
 #define IS_STRING(VAL) ((VAL)->type == OBJ_TYPE_STRING)
 #define IS_SYMBOL(VAL) ((VAL)->type == OBJ_TYPE_SYMBOL)
-- 
cgit v1.2.1