aboutsummaryrefslogtreecommitdiff
path: root/src/ast.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/ast.c')
-rw-r--r--src/ast.c483
1 files changed, 483 insertions, 0 deletions
diff --git a/src/ast.c b/src/ast.c
new file mode 100644
index 0000000..102dff5
--- /dev/null
+++ b/src/ast.c
@@ -0,0 +1,483 @@
+/* SPDX-License-Identifier: copyleft-next-0.3.1 */
+/* Copyright 2024 Kim Kuparinen < kimi.h.kuparinen@gmail.com > */
+
+/**
+ * @file ast.c
+ *
+ * Abstract syntax tree handling implementations.
+ */
+
+#include <stdio.h>
+#include <string.h>
+#include <stdarg.h>
+#include <stdlib.h>
+#include <assert.h>
+#include <math.h>
+
+#include <fwd/ast.h>
+#include <fwd/vec.h>
+#include <fwd/scope.h>
+
+static struct vec nodes = {0};
+static struct vec types = {0};
+
+static void destroy_ast_node(struct ast *n)
+{
+ if (!n)
+ return;
+
+ if (n->s)
+ free(n->s);
+
+ free(n);
+}
+
+static void destroy_type(struct type *n)
+{
+ if (!n)
+ return;
+
+ if (n->id)
+ free(n->id);
+
+ free(n);
+}
+
+static void destroy_ast_nodes()
+{
+ foreach_vec(ni, nodes) {
+ struct ast *n = vect_at(struct ast *, nodes, ni);
+ destroy_ast_node(n);
+ }
+
+ vec_destroy(&nodes);
+}
+
+static void destroy_types()
+{
+ foreach_vec(ti, types) {
+ struct type *t = vect_at(struct type *, types, ti);
+ destroy_type(t);
+ }
+
+ vec_destroy(&types);
+}
+
+void destroy_allocs()
+{
+ destroy_ast_nodes();
+ destroy_types();
+}
+
+static struct ast *create_empty_ast()
+{
+ if (vec_uninit(nodes)) {
+ nodes = vec_create(sizeof(struct ast *));
+ }
+
+ struct ast *n = calloc(1, sizeof(struct ast));
+ /* just to be safe */
+ n->k = AST_EMPTY;
+ vect_append(struct ast *, nodes, &n);
+ return n;
+}
+
+static struct type *create_empty_type()
+{
+ if (vec_uninit(types)) {
+ types = vec_create(sizeof(struct type *));
+ }
+
+ struct type *n = calloc(1, sizeof(struct type));
+ vect_append(struct ast *, types, &n);
+ return n;
+}
+
+struct ast *gen_ast(enum ast_kind kind,
+ struct ast *a0,
+ struct ast *a1,
+ struct ast *a2,
+ struct ast *a3,
+ struct type *t2,
+ char *s,
+ long long v,
+ double d,
+ struct src_loc loc)
+{
+ struct ast *n = create_empty_ast();
+ n->k = kind;
+ n->a0 = a0;
+ n->a1 = a1;
+ n->a2 = a2;
+ n->a3 = a3;
+ n->t2 = t2;
+ n->s = s;
+ n->v = v;
+ n->d = d;
+ n->loc = loc;
+ return n;
+}
+
+struct type *tgen_type(enum type_kind kind,
+ struct type *t0,
+ char *id,
+ struct src_loc loc)
+{
+ struct type *n = create_empty_type();
+ n->k = kind;
+ n->t0 = t0;
+ n->id = id;
+ n->loc = loc;
+ return n;
+}
+
+void ast_append(struct ast **list, struct ast *elem)
+{
+ struct ast *cur = *list;
+ if (!cur) {
+ *list = elem;
+ return;
+ }
+
+ while (cur->n)
+ cur = cur->n;
+
+ cur->n = elem;
+}
+
+struct ast *ast_prepend(struct ast *list, struct ast *elem)
+{
+ elem->n = list;
+ return elem;
+}
+
+static void dump(int depth, const char *fmt, ...)
+{
+ va_list args;
+ va_start(args, fmt);
+ printf("//");
+ for (int i = 0; i < depth; ++i)
+ printf(" ");
+
+ vprintf(fmt, args);
+
+ va_end(args);
+}
+
+void ast_dump(int depth, struct ast *n)
+{
+ if (!n) {
+ dump(depth, "{NULL}\n");
+ return;
+ }
+
+#define DUMP(x) case x: dump(depth, #x); break;
+ switch (n->k) {
+ DUMP(AST_CLOSURE);
+ DUMP(AST_LET);
+ DUMP(AST_INIT);
+ DUMP(AST_CALL);
+ DUMP(AST_PROC_DEF);
+ DUMP(AST_VAR_DEF);
+ DUMP(AST_DOT);
+ DUMP(AST_BLOCK);
+ DUMP(AST_ID);
+ DUMP(AST_EMPTY);
+ DUMP(AST_ADD);
+ DUMP(AST_SUB);
+ DUMP(AST_MUL);
+ DUMP(AST_DIV);
+ DUMP(AST_REM);
+ DUMP(AST_LAND);
+ DUMP(AST_LOR);
+ DUMP(AST_LSHIFT);
+ DUMP(AST_RSHIFT);
+ DUMP(AST_LT);
+ DUMP(AST_GT);
+ DUMP(AST_LE);
+ DUMP(AST_GE);
+ DUMP(AST_NE);
+ DUMP(AST_EQ);
+ DUMP(AST_NEG);
+ DUMP(AST_LNOT);
+ DUMP(AST_NOT);
+ DUMP(AST_CONST_INT);
+ DUMP(AST_CONST_CHAR);
+ DUMP(AST_CONST_BOOL);
+ DUMP(AST_CONST_FLOAT);
+ DUMP(AST_CONST_STR);
+ }
+#undef DUMP
+
+ depth++;
+
+ if (n->scope)
+ printf(" {%llu}", (unsigned long long)n->scope->number);
+
+ printf("\n");
+
+ if (n->s)
+ dump(depth, "%s\n", n->s);
+
+ if (is_const(n))
+ dump(depth, "%lli\n", n->v);
+
+ if (n->a0)
+ ast_dump_list(depth, n->a0);
+
+ if (n->a1)
+ ast_dump_list(depth, n->a1);
+
+ if (n->a2)
+ ast_dump_list(depth, n->a2);
+
+ if (n->a3)
+ ast_dump_list(depth, n->a3);
+}
+
+void ast_dump_list(int depth, struct ast *root)
+{
+ if (!root) {
+ dump(depth, "{NULL}\n");
+ return;
+ }
+
+ foreach_node(n, root) {
+ ast_dump(depth, n);
+ }
+}
+
+struct ast *clone_ast(struct ast *n)
+{
+ if (!n)
+ return NULL;
+
+ assert(n->k);
+ struct ast *new = create_empty_ast();
+ new->scope = n->scope;
+ new->loc = n->loc;
+ new->k = n->k;
+ new->v = n->v;
+ new->d = n->d;
+
+ if (n->s)
+ new->s = strdup(n->s);
+
+ if (n->a0)
+ new->a0 = clone_ast_list(n->a0);
+
+ if (n->a1)
+ new->a1 = clone_ast_list(n->a1);
+
+ if (n->a2)
+ new->a2 = clone_ast_list(n->a2);
+
+ if (n->a3)
+ new->a3 = clone_ast_list(n->a3);
+
+ return new;
+}
+
+struct ast *clone_ast_list(struct ast *root)
+{
+ struct ast *n = root, *new_root = NULL, *prev = NULL;
+ while (n) {
+ struct ast *new = clone_ast(n);
+
+ if (prev) prev->n = new;
+ else new_root = new;
+
+ prev = new;
+ n = n->n;
+ }
+
+ return new_root;
+}
+
+int ast_visit(ast_callback_t before, ast_callback_t after, struct ast *n,
+ void *d)
+{
+ int ret = 0;
+ if (!n)
+ return ret;
+
+ if (before && (ret = before(n, d)))
+ return ret;
+
+ if (n->a0 && (ret = ast_visit_list(before, after, n->a0, d)))
+ return ret;
+
+ if (n->a1 && (ret = ast_visit_list(before, after, n->a1, d)))
+ return ret;
+
+ if (n->a2 && (ret = ast_visit_list(before, after, n->a2, d)))
+ return ret;
+
+ if (n->a3 && (ret = ast_visit_list(before, after, n->a3, d)))
+ return ret;
+
+ if (after && (ret = after(n, d)))
+ return ret;
+
+ return ret;
+}
+
+int ast_visit_list(ast_callback_t before, ast_callback_t after, struct ast *l,
+ void *d)
+{
+ int ret = 0;
+ foreach_node(n, l) {
+ if ((ret = ast_visit(before, after, n, d)))
+ return ret;
+ }
+
+ return ret;
+}
+
+size_t ast_list_len(struct ast *node)
+{
+ size_t count = 0;
+ while (node) {
+ count++;
+ node = node->n;
+ }
+
+ return count;
+}
+
+struct ast *ast_last(struct ast *list)
+{
+ if (!list)
+ return NULL;
+
+ while (list->n)
+ list = list->n;
+
+ return list;
+}
+
+struct ast *ast_block_last(struct ast *block)
+{
+ struct ast *b = ast_last(block);
+ if (b && b->k == AST_BLOCK)
+ return ast_block_last(block_body(b));
+
+ return b;
+}
+
+int same_id(char *id1, char *id2)
+{
+ return strcmp(id1, id2) == 0;
+}
+
+int equiv_nodes(struct ast *n1, struct ast *n2)
+{
+ if (n1 && !n2)
+ return 0;
+
+ if (!n1 && n2)
+ return 0;
+
+ if (!n1 && !n2)
+ return 1;
+
+ if (n1->k != n2->k)
+ return 0;
+
+ if (n1->s && strcmp(n1->s, n2->s) != 0)
+ return 0;
+
+ if (n1->a0 && !equiv_node_lists(n1->a0, n2->a0))
+ return 0;
+
+ if (n1->a1 && !equiv_node_lists(n1->a1, n2->a1))
+ return 0;
+
+ if (n1->a2 && !equiv_node_lists(n1->a2, n2->a2))
+ return 0;
+
+ if (n1->a3 && !equiv_node_lists(n1->a3, n2->a3))
+ return 0;
+
+ return 1;
+}
+
+int equiv_node_lists(struct ast *c1, struct ast *c2)
+{
+ do {
+ if (!equiv_nodes(c1, c2))
+ return 0;
+
+ c1 = c1->n;
+ c2 = c2->n;
+
+ } while (c1 && c2);
+
+ return 1;
+}
+
+size_t align3k(size_t o)
+{
+ size_t rem = o % 3;
+ if (rem)
+ o += 3 - rem;
+
+ return o;
+}
+
+struct ast *reverse_ast_list(struct ast *root)
+{
+ struct ast *new_root = NULL;
+ while (root) {
+ struct ast *next = root->n;
+ root->n = new_root;
+ new_root = root;
+ root = next;
+ }
+
+ return new_root;
+}
+
+struct type *reverse_type_list(struct type *root)
+{
+ struct type *new_root = NULL;
+ while (root) {
+ struct type *next = root->n;
+ root->n = new_root;
+ new_root = root;
+ root = next;
+ }
+
+ return new_root;
+}
+
+void fix_closures(struct ast *root)
+{
+ while (root) {
+ if (root->k != AST_CALL) {
+ root = root->n;
+ continue;
+ }
+ struct ast *arg = ast_last(call_args(root));
+ if (!arg) {
+ root = root->n;
+ continue;
+ }
+
+ if (arg->k != AST_CLOSURE) {
+ root = root->n;
+ continue;
+ }
+
+ if (closure_body(arg) != NULL) {
+ root = root->n;
+ continue;
+ }
+
+ struct ast *next = root->n;
+ struct ast *block = gen_block(next, next->loc);
+ closure_body(arg) = block;
+ root->n = NULL;
+ root = next;
+ }
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-04-04 22:51:30 +0000