begin working on graph IR

4 files changed, 195 insertions, 85 deletions

diff --git a/dynarr.h b/dynarr.h
new file mode 100644
index 0000000..fb577ef
--- /dev/null
+++ b/dynarr.h
@@ -0,0 +1,71 @@
+#ifndef DYNARR_H
+#define DYNARR_H
+
+#include "arena.h"
+
+#define DYNARR(t) struct { t *data; ptrdiff_t len, cap; }
+
+#define ZDA_FIT(da, c, zn) ((typeof((da)->data))\
+	zda_fit((void **)&(da)->data, sizeof((da)->data[0]),\
+			_Alignof(typeof((da)->data[0])), \
+			c, &(da)->cap, zn))
+
+#define ZDA_FIT_ALIGN(da, c, a, zn) ((typeof((da)->data))\
+	zda_fit((void **)&(da)->data, sizeof((da)->data[0]), a,\
+			c, &(da)->cap, zn))
+
+#define ZDA_GROW(da, n, zn) ZDA_FIT(da, (da)->len + n, zn)
+
+#define ZDA_PUSH(da, v, zn)\
+	(ZDA_GROW(da, 1, zn)[(da)->len++] = (v))
+
+#define ZDA_INIT_CAP 32
+
+#define DA_FIT(da, c) ((typeof((da)->data))\
+	da_fit((void **)&(da)->data, sizeof((da)->data[0]), c, &(da)->cap))
+
+#define DA_FIT_ALIGN(da, c, a) ((typeof((da)->data))\
+	da_fit((void **)&(da)->data, sizeof((da)->data[0]), a, c, &(da)->cap)
+
+#define DA_GROW(da, n) DA_FIT(da, (da)->len + n)
+#define DA_PUSH(da, ...) (DA_GROW(da, 1)[(da)->len++] = (__VA_ARGS__))
+#define DA_INIT_CAP 32
+
+void *da_fit(void **data, ptrdiff_t size, ptrdiff_t fit, ptrdiff_t *cap);
+void *zda_fit(void **data, ptrdiff_t size, ptrdiff_t align, ptrdiff_t fit, ptrdiff_t *cap, Arena *a);
+
+#ifdef DYNARR_IMPL
+
+#include <stdio.h>
+#include <stdlib.h>
+
+void *da_fit(void **data, ptrdiff_t size, ptrdiff_t fit, ptrdiff_t *cap) {
+	ptrdiff_t c = *cap;
+	if (c >= fit) return *data;
+	if (!c) c = DA_INIT_CAP;
+	while (c < fit) c <<= 1;
+	size_t sz = c * size;
+	void *p = *data ? realloc(*data, sz) : malloc(sz);
+	if (!p) {
+		fprintf(stderr, "dynamic array resize failure\n");
+		abort();
+	}
+	*cap = c;
+	*data = p;
+	return p;
+}
+
+void *zda_fit(void **data, ptrdiff_t size, ptrdiff_t align, ptrdiff_t fit, ptrdiff_t *cap, Arena *a) {
+	ptrdiff_t C = *cap;
+	ptrdiff_t c = C;
+	if (c >= fit) return *data;
+	if (!c) c = ZDA_INIT_CAP;
+	while (c < fit) c <<= 1;
+	void *p = arena_realloc(a, *data, C * size, c * size, align);
+	*cap = c;
+	*data = p;
+	return p;
+}
+
+#endif
+#endif
diff --git a/impl.c b/impl.c
index 96d8836..03014bb 100644
--- a/impl.c
+++ b/impl.c
@@ -1,6 +1,9 @@
 #define STR_IMPL
 #define STRIO_IMPL
 #define ARENA_IMPL
+#define DYNARR_IMPL
+
 #include "str.h"
 #include "strio.h"
 #include "arena.h"
+#include "dynarr.h"
diff --git a/lex.h b/lex.h
index 460636a..daf71cc 100644
--- a/lex.h
+++ b/lex.h
@@ -4,27 +4,27 @@
 #include "str.h"
 
 #define LEX_TOK_LIST\
-	X(TOK_EOF, "end-of-file")\
-	X(TOK_IDENT, "identifier")\
-	X(TOK_PROC, "proc")\
-	X(TOK_LET, "let")\
-	X(TOK_VAR, "var")\
-	X(TOK_CONST, "const")\
-	X(TOK_RETURN, "return")\
-	X(TOK_LBRACE, "{")\
-	X(TOK_RBRACE, "}")\
-	X(TOK_LPAREN, "(")\
-	X(TOK_RPAREN, ")")\
-	X(TOK_PLUS, "+")\
-	X(TOK_MINUS, "-")\
-	X(TOK_ASTERISK, "*")\
-	X(TOK_SLASH, "/")\
-	X(TOK_EQUALS, "=")\
-	X(TOK_COLON, ":")\
-	X(TOK_COMMA, ",")\
-	X(TOK_LIT_STR, "string literal")\
-	X(TOK_LIT_CHAR, "character literal")\
-	X(TOK_LIT_NUM, "numeric literal")
+	X(EOF, "end-of-file")\
+	X(IDENT, "identifier")\
+	X(PROC, "proc")\
+	X(LET, "let")\
+	X(VAR, "var")\
+	X(CONST, "const")\
+	X(RETURN, "return")\
+	X(LBRACE, "{")\
+	X(RBRACE, "}")\
+	X(LPAREN, "(")\
+	X(RPAREN, ")")\
+	X(PLUS, "+")\
+	X(MINUS, "-")\
+	X(ASTERISK, "*")\
+	X(SLASH, "/")\
+	X(EQUALS, "=")\
+	X(COLON, ":")\
+	X(COMMA, ",")\
+	X(LIT_STR, "string literal")\
+	X(LIT_CHAR, "character literal")\
+	X(LIT_NUM, "numeric literal")
 
 #define LEX_TOK_CHAR_LIST\
 	X(TOK_LBRACE, '{')\
@@ -40,7 +40,7 @@
 	X(TOK_COMMA, ',')
 
 typedef enum {
-#define X(n, s) n,
+#define X(n, s) TOK_##n,
 	LEX_TOK_LIST
 #undef X
 	TOK_MAX,
@@ -53,7 +53,12 @@ static const char *lex_tok_str[TOK_MAX] = {
 };
 
 #define TMASK(t) (1L << t)
-typedef unsigned long TokMask;
+
+typedef enum {
+#define X(n, s) TM_##n = TMASK(TOK_##n),
+	LEX_TOK_LIST
+#undef X
+} TokMask;
 
 typedef struct {
 	Token tok;
diff --git a/main.c b/main.c
index e8df555..b1e5150 100644
--- a/main.c
+++ b/main.c
@@ -5,6 +5,8 @@
 #include <string.h>
 
 #include "lex.h"
+#include "arena.h"
+#include "dynarr.h"
 
 /* node graph */
 
@@ -20,97 +22,125 @@ typedef enum {
 } NodeType;
 
 typedef struct Node {
+	int id;
 	NodeType type;
-	struct Node **inputs, **outputs;
+	DYNARR(struct Node *) in, out;
+	union {
+		int64_t i;
+	} v;
 } Node;
 
 typedef struct {
+	Arena arena;
+	int last_id;
 	Node *start, *stop;
-} ProcGraph;
+} Proc;
+
+typedef struct {
+	DYNARR(Proc) procs;
+} Unit;
+
+void unit_init(Unit *u) {
+	(void)u;
+}
+
+void unit_fini(Unit *u) {
+	free(u->procs.data);
+}
+
+Node *node_new(Proc *p, NodeType t) {
+	Node *n = new(&p->arena, Node);
+	n->type = t;
+	n->id = p->last_id++;
+	return n;
+}
+
+void node_add(Proc *p, Node *src, Node *dest) {
+	ZDA_PUSH(&src->out, dest, &p->arena);
+	ZDA_PUSH(&dest->in, src, &p->arena);
+}
 
 /* parsing */
 
-void parse_expr(Lexer *l);
+Node *parse_expr(Lexer *l, Proc *p);
 
-void parse_stmt_let(Lexer *l) {
-	lex_expect(l, TMASK(TOK_IDENT));
-	Str name = l->ident;
-	lex_expect(l, TMASK(TOK_EQUALS) | TMASK(TOK_COLON));
+void parse_return(Lexer *l, Proc *p) {
 	lex_next(l);
-	parse_expr(l);
-	printf("name_bind %.*s\n", (int)name.n, name.s);
+	Node *n = parse_expr(l, p);
+	node_add(p, n, p->stop);
 }
 
-void parse_stmt(Lexer *l) {
+void parse_stmt(Lexer *l, Proc *p) {
 	/* TODO */
 	(void)l;
 	switch (l->tok) {
-	case TOK_LET:
-		parse_stmt_let(l);
-		break;
 	case TOK_RETURN:
-		lex_next(l);
-		parse_expr(l);
-		puts("return");
+		parse_return(l, p);
 		break;
 	default:
-		lex_expected(l, TMASK(TOK_RBRACE));
+		lex_expected(l, TM_RBRACE);
 	}
 }
 
-void parse_proc(Lexer *l) {
-	lex_expect(l, TMASK(TOK_IDENT));
-	lex_expect(l, TMASK(TOK_LBRACE));
+void parse_proc(Lexer *l, Unit *u) {
+	DA_FIT(&u->procs, u->procs.len + 1);
+	Proc *proc = &u->procs.data[u->procs.len++];
+	memset(proc, 0, sizeof(Proc));
+	proc->start = node_new(proc, N_START);
+	proc->stop = node_new(proc, N_STOP);
+	lex_expect(l, TM_IDENT);
+	lex_expect(l, TM_LBRACE);
 	lex_next(l);
 	while (l->tok != TOK_RBRACE) {
-		lex_expected_not(l, TMASK(TOK_EOF));
-		parse_stmt(l);
+		lex_expected_not(l, TM_EOF);
+		parse_stmt(l, proc);
 	}
-	lex_expected(l, TMASK(TOK_RBRACE));
+	lex_expected(l, TM_RBRACE);
 	lex_next(l);
 }
 
-void parse_term(Lexer *l) {
+Node *parse_term(Lexer *l, Proc *p) {
+	Node *node = NULL;
 	int negate_after = l->tok == TOK_MINUS;
-	if (TMASK(l->tok) & (TMASK(TOK_MINUS) | TMASK(TOK_PLUS))) {
+	if (TMASK(l->tok) & (TM_MINUS | TM_PLUS)) {
 		lex_next(l);
 	}
 	if (l->tok == TOK_LPAREN) {
 		lex_next(l);
-		parse_expr(l);
-		lex_expected(l, TMASK(TOK_RPAREN));
+		node = parse_expr(l, p);
+		lex_expected(l, TM_RPAREN);
 		lex_next(l);
 	} else {
-		lex_expected(l, TMASK(TOK_LIT_NUM) | TMASK(TOK_LIT_STR) | TMASK(TOK_LIT_CHAR) | TMASK(TOK_IDENT));
-		switch (l->tok) {
-		case TOK_IDENT:
-			printf("var %.*s\n", (int)l->ident.n, l->ident.s);
-			break;
-		case TOK_LIT_STR:
-			printf("lit_str %.*s\n", (int)l->ident.n, l->ident.s);
-			break;
-		case TOK_LIT_CHAR:
-			printf("lit_char %.*s\n", (int)l->ident.n, l->ident.s);
-			break;
-		case TOK_LIT_NUM:
-			printf("lit_num %.*s\n", (int)l->ident.n, l->ident.s);
-			break;
-		default:
-			break;
+		lex_expected(l, TM_LIT_NUM);
+		int64_t val = 0;
+		for (int i = 0; i < l->ident.n; i++) {
+			if (!(l->ident.s[i] >= '0' && l->ident.s[i] <= '9')) {
+				lex_error(l, LE_ERROR, S("Not a digit"));
+				break;
+			}
+			val = (val * 10) + (l->ident.s[i] - '0');
 		}
+		node = node_new(p, N_LIT_INT);
+		node_add(p, p->start, node);
+		node->v.i = val;
 		lex_next(l);
 	}
-	if (negate_after) puts("negate");
+	if (negate_after) {
+		Node *neg = node_new(p, N_OP_NEG);
+		node_add(p, node, neg);
+		return neg;
+	}
+	return node;
 }
 
-void parse_expr(Lexer *l) {
-	parse_term(l);
+Node *parse_expr(Lexer *l, Proc *p) {
+	Node *lhs = parse_term(l, p);
 	if (l->tok == TOK_LPAREN) {
 		lex_next(l);
 		puts("args_start");
 		for (;;) {
-			parse_expr(l);
-			lex_expected(l, TMASK(TOK_COMMA) | TMASK(TOK_RPAREN));
+			parse_expr(l, p);
+			lex_expected(l, TM_COMMA | TM_RPAREN);
 			if (l->tok == TOK_RPAREN) break;
 			lex_next(l);
 		}
@@ -118,35 +148,36 @@ void parse_expr(Lexer *l) {
 		puts("args_end");
 		puts("func_call");
 	}
-	if (TMASK(l->tok) & (TMASK(TOK_PLUS) | TMASK(TOK_MINUS) | TMASK(TOK_ASTERISK) | TMASK(TOK_SLASH))) {
-		Token t = l->tok;
+	if (TMASK(l->tok) & (TM_PLUS | TM_MINUS | TM_ASTERISK | TM_SLASH)) {
+		lex_expected(l, TM_PLUS);
 		lex_next(l);
-		parse_expr(l);
-		switch (t) {
-		case TOK_PLUS: puts("add"); break;
-		case TOK_MINUS: puts("subtract"); break;
-		case TOK_ASTERISK: puts("multiply"); break;
-		case TOK_SLASH: puts("divide"); break;
-		default: break;
-		}
+		Node *rhs = parse_expr(l, p);
+		Node *add = node_new(p, N_OP_ADD);
+		node_add(p, lhs, add);
+		node_add(p, rhs, add);
+		return add;
 	}
+	return lhs;
 }
 
-void parse_toplevel(Lexer *l) {
+void parse_toplevel(Lexer *l, Unit *u) {
 	switch (l->tok) {
 	case TOK_PROC:
-		parse_proc(l);
+		parse_proc(l, u);
 		break;
 	default:
-		lex_expected(l, TMASK(TOK_PROC));
+		lex_expected(l, TM_PROC);
 		break;
 	}
 }
 
 void parse_unit(Lexer *l) {
+	Unit u = { 0 };
+	unit_init(&u);
 	while (l->tok != TOK_EOF) {
-		parse_toplevel(l);
+		parse_toplevel(l, &u);
 	}
+	unit_fini(&u);
 }
 
 int main(int argc, const char **argv) {