parser: add unary, and binary operationsHEADmaster

lex: add bang

passes: add initial debug pass

13 files changed, 533 insertions, 38 deletions

diff --git a/build.sh b/build.sh
index 5996c05..8dca9fc 100755
--- a/build.sh
+++ b/build.sh
@@ -6,6 +6,7 @@ SRC_DIRECTORIES=(
 	"./arch/"
 	"./lex/"
 	"./parser/"
+	"./passes/"
 	"./lib/"
 	"./platform/${PLATFORM}/"
 )
diff --git a/example.m b/example.m
index b54ad5a..79f996b 100644
--- a/example.m
+++ b/example.m
@@ -1,6 +1 @@
-fn g64 bentry() {
-	g64 test;
-	g32 test = (g32)0xB8000;
-	g64 test = 15;
-	return test;
-}
+5*5
diff --git a/include/lex.h b/include/lex.h
index bdfd32f..ab09baf 100644
--- a/include/lex.h
+++ b/include/lex.h
@@ -30,6 +30,7 @@
 #define TOKEN_MINUS             22
 #define TOKEN_STAR              23
 #define TOKEN_SLASH             24
+#define TOKEN_BANG              25
 
 const char* lex_get_token_name(int id);
 
@@ -40,8 +41,7 @@ const char* lex_get_token_name(int id);
 
 struct token {
 	int type;
-//	size_t line;
-//	size_t linepos;
+	size_t line;
 	size_t length;
 	char *lexeme;
 };
diff --git a/include/lib/arena.h b/include/lib/arena.h
new file mode 100644
index 0000000..9d3cb38
--- /dev/null
+++ b/include/lib/arena.h
@@ -0,0 +1,31 @@
+/**
+ * @file arena.h
+ * @author x221e
+ * @brief linear arena-allocation without relocation
+ * @description
+ * This will be a linear arena allocation,
+ * no free functionality exists right now.
+ *
+ * @todo create a larger arena structure that would hold regions
+ */
+
+#ifndef ARENA_H
+#define ARENA_H
+
+#include <stddef.h>
+
+// 2 MiB regions
+#define REGION_MAX_CAPACITY    1024*1024*2 
+
+struct region { // or arena?
+	size_t capacity;
+	size_t size;
+	void *end;
+	void *start;
+};
+
+int region_init(struct region *r);
+void *region_alloc(struct region *r, size_t b);
+int region_pop(struct region *r, size_t b);
+
+#endif
diff --git a/include/lib/vector.h b/include/lib/vector.h
index 33e5b97..e0cc523 100644
--- a/include/lib/vector.h
+++ b/include/lib/vector.h
@@ -16,6 +16,6 @@ struct vector {
 int vector_init(struct vector *v);
 int vector_resize(struct vector *v, size_t nc);
 int vector_emplace_back(struct vector *v, void *p);
-int vector_deinit(struct vector *v);
+int vector_free(struct vector *v);
 
 #endif
diff --git a/include/parser.h b/include/parser.h
new file mode 100644
index 0000000..a927475
--- /dev/null
+++ b/include/parser.h
@@ -0,0 +1,79 @@
+/**
+ * @file parser.h
+ * @author x221e
+ * @brief parser
+ * @description
+ * I am opting-in to AST producing compiler design. It is not strictly
+ * needed in this context, however, it will produce optimization benefits
+ * in the future.
+ *
+ * @warning DEFINETLY NEEDS ARENA ALLOC IMPL // prototyping one under lib/
+ */
+
+#ifndef PARSER_H
+#define PARSER_H
+
+#include <stddef.h>
+
+#include <lex.h>
+
+typedef struct vector vector;
+
+struct parser {
+	struct region *tokens;
+	struct vector *result; //TODO: replace with arena,, temporary
+	struct region *buffer;
+	size_t size;
+	size_t pos;
+
+	int error;
+};
+
+enum node_type { // Or should I use macros???
+	N_INVALID = -1,
+	N_EXPR = 0,
+	N_LITERAL = 1,
+	N_UNARY,
+	N_BINARY,
+};
+
+enum data_type {
+	DT_INVALID = -1,
+	DT_UNSIGNED64,
+	DT_UNSIGNED32,
+	DT_UNSIGNED16,
+	DT_UNSIGNED8,
+};
+
+struct node_primary {
+	enum node_type ntype;
+	enum data_type type;
+
+	int is_number;
+	union {
+		size_t number;
+		char* str;
+	} value;
+};
+
+struct node_unary {
+	enum node_type ntype;
+
+	struct token operator;
+	void *expr;
+};
+
+struct node_binary {
+	enum node_type ntype;
+	struct token operator;
+	void *left;
+	void *right;
+};
+
+struct node {
+	enum node_type ntype;
+};
+
+void parser_parse(struct parser *p);
+
+#endif
diff --git a/include/passdbg.h b/include/passdbg.h
new file mode 100644
index 0000000..15643d8
--- /dev/null
+++ b/include/passdbg.h
@@ -0,0 +1,9 @@
+#ifndef PASSDBG_H
+#define PASSDBG_H
+
+void passdbg_primary(void *n);
+void passdbg_unary(void *n);
+void passdbg_binary(void *n);
+void passdbg_walk(void *n);
+
+#endif
diff --git a/lex/lex.c b/lex/lex.c
index ea0978e..f787619 100644
--- a/lex/lex.c
+++ b/lex/lex.c
@@ -4,7 +4,6 @@
 #include <string.h>
 
 #include <platform/osal.h>
-
 #include <stdio.h>
 
 static struct token keywords[] = {
@@ -46,6 +45,7 @@ const char *lex_get_token_name(int id)
 	__GET_TKN_NAME(TOKEN_MINUS);
 	__GET_TKN_NAME(TOKEN_STAR);
 	__GET_TKN_NAME(TOKEN_SLASH);
+	__GET_TKN_NAME(TOKEN_BANG);
 	default:
 		print("lex_get_token_name: token not found: %d!", id);
 		exitc(1);
@@ -266,13 +266,12 @@ struct token lex_keyword(struct lex *l) //APPROPRIATE INC
 		}
 
 		if (strncmp(&l->buffer[start], keywords[i].lexeme, keywords[i].length) == 0) {
-			tt = keywords[i].type;	
+			tt = keywords[i].type;
 			break;
 		}
 	}
 
 	return (struct token) {.type = tt, .length=len, .lexeme = &l->buffer[start]};
-	 
 }
 
 struct token lex_next(struct lex *l)
@@ -329,11 +328,14 @@ struct token lex_next(struct lex *l)
 	case '/':
 		lex_advance(l, 1);
 		return TOKEN(TOKEN_SLASH, "/");
+	case '!':
+		lex_advance(l, 1);
+		return TOKEN(TOKEN_BANG, "!");
 	default:
 		char curr = lex_seek(l, 0);
-		if (lex_is_char(curr) || (curr == '_')) {
+		if (lex_is_char(curr) || (curr == '_'))
 			return lex_keyword(l);
-		}
+
 		return TOKEN(TOKEN_INVALID, "INVALID");
 	}
 }
diff --git a/lib/arena.c b/lib/arena.c
new file mode 100644
index 0000000..49ef7f1
--- /dev/null
+++ b/lib/arena.c
@@ -0,0 +1,54 @@
+#include <lib/arena.h>
+
+#include <platform/osal.h>
+
+#include <sys/mman.h>
+
+#include <string.h>
+#include <errno.h>
+#include <assert.h>
+
+int region_init(struct region *r)
+{
+	void * mem = mmap(NULL, REGION_MAX_CAPACITY, PROT_READ | PROT_WRITE,
+			  MAP_PRIVATE | MAP_ANONYMOUS, 0, 0); // Abstract this under platform
+
+	if (mem == NULL) {
+		print("errno: %s\n", strerror(errno));
+		return -1;
+	}
+
+	r->capacity = REGION_MAX_CAPACITY;
+	r->start = mem;
+	r->end = r->start;
+	r->size = 0;
+
+	return 0;		
+}
+
+void *region_alloc(struct region *r, size_t b)
+{
+	if (r->capacity <= r->size + b) {
+		print("compiler error: region memory exceeded trying to allocate %zu bytes!", b); // Make this debug error, only present with verbose flag.
+		return NULL;
+	}
+       
+	void* ptr = r->end;
+	r->end = (char*)r->end + b;
+	r->size += b;
+	return ptr;
+}
+
+// such a dumb workaround, fix this.
+int region_pop(struct region *r, size_t b)
+{
+	assert(r != NULL);
+
+	if (r->size > b) {
+		return -1;
+	}
+
+	r->end = (char*)r->end - b;
+	r->size -= b;
+	return 0;
+}
diff --git a/lib/vector.c b/lib/vector.c
index d338db2..91c349b 100644
--- a/lib/vector.c
+++ b/lib/vector.c
@@ -17,6 +17,12 @@ int vector_init(struct vector *v)
 	return 0;
 }
 
+int vector_free(struct vector *v)
+{
+	assert(v != NULL);
+	mem_free((void*)v->buffer);
+}
+
 int vector_reserve(struct vector *v, size_t nc)
 {
 	assert(v != NULL);
diff --git a/parser/parser.c b/parser/parser.c
new file mode 100644
index 0000000..42a2dcf
--- /dev/null
+++ b/parser/parser.c
@@ -0,0 +1,177 @@
+/**
+ * @file parser.c
+ * @brief 
+ */
+#include <parser.h>
+
+#include <assert.h>
+
+#include <platform/osal.h>
+#include <lib/arena.h>
+#include <lib/vector.h>
+#include <lex.h>
+
+#include <stdlib.h>
+
+void parser_print_error(struct parser *p, const char *e)
+{
+	print("error: %s\n", e);
+}
+
+struct token* parser_previous(struct parser *p)
+{
+	if (p->pos < 1) {
+		return &((struct token*)p->tokens->start)[0];
+	}
+	return &((struct token*)p->tokens->start)[p->pos - 1];
+}
+
+struct token* parser_advance(struct parser *p)
+{
+	if (p->pos >= p->size) {
+		return &((struct token*)p->tokens->start)[p->size];
+	}
+	p->pos++;
+	return &((struct token*)p->tokens->start)[p->pos];
+}
+
+struct token* parser_seek(struct parser *p, size_t o)
+{
+	if (p->pos + o >= p->size) {
+		return &((struct token*)p->tokens->start)[p->size];
+	}
+	return &((struct token*)p->tokens->start)[p->pos + o];
+}
+
+int parser_expect(struct parser *p, int t, char *e)
+{
+	assert(p != NULL);
+
+	if (parser_seek(p, 0)->type == t)
+		return 0;
+
+	p->error = 1;
+	parser_print_error(p, e);
+}
+
+int parser_match(struct parser *p, size_t n, ...)
+{
+	assert(p != NULL);
+	va_list args;
+	va_start(args, p);
+
+	int res = 0;
+	
+	struct token *t = parser_seek(p, 0);
+	for (int i = 0; i < n; i++) {
+		if (t->type == va_arg(args, int)) {
+			res = 1;
+			parser_advance(p);
+			goto cleanup;
+		}
+	}
+
+ cleanup:
+	va_end(args);
+	return res;
+}
+
+void * parser_parse_primary(struct parser *p)
+{
+	assert(p != NULL);
+
+	struct node_primary* n = (struct node_primary*)region_alloc(p->buffer, sizeof(struct node_primary));
+
+	n->ntype = N_LITERAL;
+	
+	struct token *tkn = parser_seek(p, 0);
+	char * tkn_str = tkn->lexeme;
+	
+	switch (tkn->type) {
+	case TOKEN_NUMBER:
+		n->is_number = 1;
+		n->value.number = atoi(tkn_str);
+		break;
+	case TOKEN_HEX:
+		n->is_number = 1;
+		print("TODO: to be implemented!!\n");
+		break;
+	case TOKEN_BINARY:
+		print("TODO: to be implemented!\n");
+		break;
+	}
+
+	parser_advance(p);
+	return n;
+}
+
+void *parser_parse_unary(struct parser *p)
+{
+	if (parser_match(p, 2, TOKEN_MINUS, TOKEN_BANG)) {
+		struct token *operator = parser_previous(p);
+		void *unary = parser_parse_unary(p);
+		
+		struct node_unary *mem = region_alloc(p->buffer, sizeof(struct node_unary));
+		*mem = (struct node_unary) {.ntype = N_UNARY, .operator=*operator, .expr=unary};
+		return mem;
+	}
+
+	return parser_parse_primary(p);
+}
+
+void *parser_parse_term(struct parser *p)
+{
+	assert(p != NULL);
+
+	void *expr = parser_parse_unary(p);
+
+	while (parser_match(p, 2, TOKEN_STAR, TOKEN_SLASH)) {
+		struct token *operator = parser_previous(p);
+		void *right = parser_parse_unary(p);
+		
+		void *tmp = expr;
+		expr = region_alloc(p->buffer, sizeof(struct node_binary));
+		*((struct node_binary*)expr) = (struct node_binary) {.ntype = N_BINARY, .operator=*operator, .left = tmp, .right = right};
+	}
+
+	return expr;
+}
+
+void *parser_parse_factor(struct parser *p)
+{
+	assert(p != NULL);
+
+	void *expr = parser_parse_term(p);
+
+	while (parser_match(p, 2, TOKEN_PLUS, TOKEN_MINUS)) {
+		struct token *operator = parser_previous(p);
+		void *right = parser_parse_term(p);
+		 
+		void *tmp = expr;
+		expr = region_alloc(p->buffer, sizeof(struct node_binary));
+		*((struct node_binary*)expr) = (struct node_binary) {.ntype = N_BINARY, .operator=*operator, .left = tmp, .right = right};
+	}
+
+	return expr;
+}
+
+void *parser_parse_expression(struct parser *p)
+{
+	assert(p != NULL);
+}
+
+void *parser_parse_statement(struct parser *p)
+{
+	assert(p != NULL);
+	parser_parse_primary(p);
+	parser_expect(p, TOKEN_SEMICOLON, "A statement must end with a semicolon!");
+}
+
+void parser_parse(struct parser *p)
+{
+	assert(p != NULL);
+
+	while (p->pos < p->size && (((struct token*)p->tokens->start) + p->pos) != NULL) {
+		vector_emplace_back(p->result, parser_parse_factor(p));
+	}
+}
diff --git a/passes/passdbg.c b/passes/passdbg.c
new file mode 100644
index 0000000..334e6ea
--- /dev/null
+++ b/passes/passdbg.c
@@ -0,0 +1,114 @@
+#include <passdbg.h>
+
+#include <lib/arena.h>
+
+#include <platform/osal.h>
+#include <parser.h>
+
+#include <assert.h>
+
+static int indent_lvl = 0;
+
+#define INDENT_PRINT(x)				 \
+	for (int i = 0; i < indent_lvl + x; i++) \
+		print(" ")
+
+void passdbg_primary(void *n)
+{
+	assert(n != NULL);
+	struct node_primary *primary = (struct node_primary *)n;
+
+	if (primary->ntype != N_LITERAL) {
+		print("passdbg_primary(): node not literal!");
+		exitc(1);
+	}
+
+	INDENT_PRINT(0);
+        print("Primary Node: (%s)\n", primary->is_number ? "Number" : "String");
+	INDENT_PRINT(2);
+	switch (primary->is_number) {
+	case 0:
+		print("Content: %s\n", primary->value.str);
+		break;
+	case 1:
+		print("Content: %d\n", primary->value.number);
+		break;
+	default:
+		print("error: unrecognized type for passdbg_primary()");
+		exitc(1);
+		break;
+	}
+}
+
+void passdbg_unary(void *n)
+{
+	assert(n != NULL);
+
+	struct node_unary *unary = (struct node_unary *)n;
+
+	if (unary->ntype == N_LITERAL) {
+		passdbg_primary(n);
+		return;
+	}
+
+	if (unary->ntype != N_UNARY) {
+		print("passdbg_unary(): Node not unary!");
+		exitc(1);
+	}
+
+	INDENT_PRINT(0);	
+	print("Unary Operator:\n");
+	indent_lvl += 2;
+	INDENT_PRINT(0);
+	print("Operator: %s\n", unary->operator.lexeme);
+	INDENT_PRINT(0);
+	print("Expr:\n");
+	indent_lvl += 2;
+	passdbg_walk(unary->expr);
+	indent_lvl -= 4;
+}
+
+void passdbg_binary(void *n)
+{
+	assert(n != NULL);
+
+	struct node_binary *binary = (struct node_binary*)n;
+
+	if (binary->ntype != N_BINARY) {
+		print("passdbg_binary(): error node not binary!");
+		exitc(1);
+	}
+
+	INDENT_PRINT(0);
+	print("Binary Operator:\n");
+	indent_lvl+=2;
+	INDENT_PRINT(0);
+	print("Operator: %s\n", binary->operator.lexeme);
+	INDENT_PRINT(0);
+	print("Left:\n");
+	indent_lvl+=2;
+	passdbg_walk(binary->left);
+	indent_lvl-=2;
+	INDENT_PRINT(0);
+	print("Right:\n");
+	indent_lvl+=2;
+	passdbg_walk(binary->right);
+	indent_lvl-=4;
+}
+
+#define __WALKER_CASE(type, func) case type: func; return
+
+void passdbg_walk(void *n)
+{
+	struct node* node = (struct node*)n;
+
+	switch (node->ntype) {
+		__WALKER_CASE(N_LITERAL, passdbg_primary(n));
+		__WALKER_CASE(N_UNARY, passdbg_unary(n));
+		__WALKER_CASE(N_BINARY, passdbg_binary(n));
+	default:
+		print("passdbg_walk(): invalid node type!\n");
+		exitc(1);
+	}
+}
+
diff --git a/platform/elf/main.c b/platform/elf/main.c
index 9c4bbd8..710cf04 100644
--- a/platform/elf/main.c
+++ b/platform/elf/main.c
@@ -1,7 +1,10 @@
 #include <stdio.h>
 
 #include <lex.h>
+#include <parser.h>
+#include <lib/arena.h>
 #include <lib/vector.h>
+#include <passdbg.h>
 
 #include <platform/osal.h>
 
@@ -18,9 +21,10 @@ int main(int argc, char **argv)
 
 	struct file fl = open_file(argv[1], FILE_READ);
 
-	struct vector token_storage = {0};
-	if (vector_init(&token_storage)) {
-		printf("error: vector_init()");
+	struct region tokens;
+	
+	if (region_init(&tokens) == -1) {
+		printf("Region init error!");
 		exit(1);
 	}
 
@@ -36,38 +40,61 @@ int main(int argc, char **argv)
 	size_t size = 0;
 
 	do {
-		tkn = mem_alloc(sizeof(struct token)); // Change mem alloc with arena alloc
+		struct token curr = lex_next(&lex);
+
+		if (curr.type == TOKEN_NEWLINE)
+			continue;
+
+		if (curr.type == TOKEN_EOP)
+			break;		
+		
+		tkn = region_alloc(&tokens, sizeof(struct token));
 
 		if (tkn == NULL) {
 			printf("error: token alloc");
 			exit(1);
 		}
+		
+		*tkn = curr;
+		
+		/* printf("Tokenized to mem %p! Current region size: %d, type: %d\n", */
+		/*        tkn, */
+		/*        (int)tokens.size, */
+		/*        ((struct token*)tokens.start)[size].type); */
 
-		*tkn = lex_next(&lex);
-
-		//		printf("Tokenized: %.*s, with length: %d.\n", (int)tkn->length, tkn->lexeme, (int)tkn->type);
-
-		if (vector_emplace_back(&token_storage, tkn) == -1) {
-			printf("error: vector_emplace_back()");
-			exit(1);
-		}
+		size++;
 
 	} while (tkn != NULL &&
 		tkn->type != TOKEN_INVALID && 
 		tkn->type != TOKEN_EOP);
 
-	for (int i = 0; i < token_storage.size; i++) {
-		if (token_storage.buffer[i] == NULL)
-			break;
-
-		printf("Tokenized '%.*s' with type: %s\n", //, on line: %d at position: %d\n", 
-		       (int)((struct token*) token_storage.buffer[i])->length,
-		       ((struct token*)token_storage.buffer[i])->lexeme,
-		       lex_get_token_name((int)((struct token*)token_storage.buffer[i])->type)
-//				((struct token*)token_storage.buffer[i])->line,
-//				((struct token*)token_storage.buffer[i])->pos
-				);
+	for (int i = 0; i < (tokens.size) / sizeof(struct token); i++) {
+		struct token* curr = ((struct token*)tokens.start) + i;
+		printf("Tokenized '%.*s' with type: %s\n",		       
+		       (int)curr->length,
+		       curr->lexeme,
+		       lex_get_token_name((int)curr->type));
 	}
 
-	return 0;
+	struct region parsed;
+	region_init(&parsed);
+
+	struct vector ast_tree;
+	vector_init(&ast_tree);
+	
+	struct parser p;
+	p.tokens = &tokens;
+	p.buffer = &parsed;
+	p.result = &ast_tree;
+	p.size = tokens.size / sizeof(struct token);
+	p.pos = 0;
+	p.error = 0;
+	
+	parser_parse(&p);
+	if (p.error)
+		return 1;
+
+	passdbg_walk(ast_tree.buffer[0]);
+
+	vector_free(&ast_tree);
 }