Add generic dynamic array and change tokens to use it

6 files changed, 77 insertions, 41 deletions

diff --git a/src/bootstrap/darray.h b/src/bootstrap/darray.h
new file mode 100644
index 0000000..bb49cdd
--- /dev/null
+++ b/src/bootstrap/darray.h
@@ -0,0 +1,55 @@
+#ifndef BDL_DARRAY_H
+#define BDL_DARRAY_H
+
+#include <string.h>
+
+typedef struct ArrayHeader {
+    size_t size;
+    size_t cap;
+} ArrayHeader;
+
+// Header/Size/capacity accessors.
+#define array_head(ARR) ((ArrayHeader *)((char *)(ARR) - sizeof(ArrayHeader)))
+#define array_size(ARR) ((ARR) ? array_head(ARR)->size : 0)
+#define array_cap(ARR)  ((ARR) ? array_head(ARR)->cap : 0)
+
+// Initialize a dynamic array ARR with N elements. The initialization doesn't
+// zero out the data, so thread carefully..
+#define array_init(ARR,N) ((ARR) = _array_reserve(N, sizeof(*(ARR))))
+
+// Push a given element T to the dynamic array ARR.
+#define array_push(ARR, T) \
+    ((ARR) = _array_maybe_grow(ARR, sizeof(T)),  \
+     (ARR)[array_head(ARR)->size++] = (T))
+
+// Return the last element of the array. Can be used to build stacks.
+#define array_pop(ARR) (ARR)[--array_head(ARR)->size]
+
+// Free the memory from the original allocated position.
+#define array_free(ARR)   ((ARR) ? free(array_head(ARR)), (ARR) = NULL : 0)
+
+static inline void *
+_array_reserve(size_t num_elem, size_t type_size) {
+    char *p = malloc(num_elem * type_size + sizeof(ArrayHeader));
+    p += sizeof(ArrayHeader);
+    array_head(p)->size = 0;
+    array_head(p)->cap = num_elem;
+    return p;
+}
+
+static inline void *
+_array_maybe_grow(void *arr, size_t type_size) {
+    ArrayHeader *head = array_head(arr);
+    if (head->cap == head->size) {
+        if (head->cap == 0) {
+            head->cap++;
+        } else {
+            head->cap *= 2;
+        }
+        head = realloc(head, head->cap * type_size + sizeof(ArrayHeader));
+    }
+    arr = (char *)head + sizeof(ArrayHeader);
+    return arr;
+}
+
+#endif // BDL_DARRAY_H
diff --git a/src/bootstrap/lexer.c b/src/bootstrap/lexer.c
index 05324eb..38ca37c 100644
--- a/src/bootstrap/lexer.c
+++ b/src/bootstrap/lexer.c
@@ -44,19 +44,6 @@ print_token(Token tok) {
     printf("\n");
 }
 
-void
-push_token(Tokens *tokens, Token tok) {
-    if (tokens->buf == NULL) {
-        tokens->size = 0;
-        tokens->cap = TOK_BUF_CAP;
-        tokens->buf = malloc(tokens->cap * sizeof(Token));
-    } else if (tokens->size == tokens->cap) {
-        tokens->cap *= 2;
-        tokens->buf = realloc(tokens->buf, tokens->cap * sizeof(Token));
-    }
-    tokens->buf[tokens->size++] = tok;
-}
-
 char
 scan_next(Scanner *scanner) {
     char c = sv_next(&scanner->current);
@@ -147,9 +134,10 @@ find_primitive_type(const StringView value) {
     return TOKEN_SYMBOL;
 }
 
-Tokens
+Token *
 tokenize(const StringView *sv) {
-    Tokens tokens = (Tokens){0};
+    Token *tokens = NULL;
+    array_init(tokens, 1);
     Scanner scanner = (Scanner){
         .current = *sv,
         .line_number = 1,
@@ -197,7 +185,7 @@ tokenize(const StringView *sv) {
                     .line = line,
                     .column = col,
                 };
-                push_token(&tokens, token);
+                array_push(tokens, token);
             } break;
             case '\'': {
                 Token token =  (Token){
@@ -205,7 +193,7 @@ tokenize(const StringView *sv) {
                     .line = line,
                     .column = col,
                 };
-                push_token(&tokens, token);
+                array_push(tokens, token);
             } break;
             case '(': {
                 if (scan_peek(&scanner) == ')') {
@@ -215,14 +203,14 @@ tokenize(const StringView *sv) {
                         .line = line,
                         .column = col,
                     };
-                    push_token(&tokens, token);
+                    array_push(tokens, token);
                 } else {
                     Token token =  (Token){
                         .type = TOKEN_LPAREN,
                         .line = line,
                         .column = col,
                     };
-                    push_token(&tokens, token);
+                    array_push(tokens, token);
                 }
             } break;
             case ')': {
@@ -231,7 +219,7 @@ tokenize(const StringView *sv) {
                     .line = line,
                     .column = col,
                 };
-                push_token(&tokens, token);
+                array_push(tokens, token);
             } break;
             default: {
                 size_t n = 1;
@@ -252,7 +240,7 @@ tokenize(const StringView *sv) {
                     .column = col,
                 };
                 token.type = find_primitive_type(token.value);
-                push_token(&tokens, token);
+                array_push(tokens, token);
             } break;
         }
     }
@@ -263,7 +251,7 @@ tokenize(const StringView *sv) {
         .line = scanner.line_number,
         .column = 1,
     };
-    push_token(&tokens, token);
+    array_push(tokens, token);
 
     return tokens;
 }
diff --git a/src/bootstrap/lexer.h b/src/bootstrap/lexer.h
index 129fd9a..2b2789f 100644
--- a/src/bootstrap/lexer.h
+++ b/src/bootstrap/lexer.h
@@ -22,12 +22,6 @@ typedef struct Token {
     size_t column;
 } Token;
 
-typedef struct Tokens {
-    Token *buf;
-    size_t size;
-    size_t cap;
-} Tokens;
-
 typedef struct Scanner {
     StringView current;
     size_t line_number;
@@ -38,9 +32,6 @@ typedef struct Scanner {
 // Print a token to standard output for debugging purposes.
 void print_token(Token tok);
 
-// Push a token to the token list.
-void push_token(Tokens *tokens, Token tok);
-
 // Same functionality as the ScanView pairs, but keeping track of line and
 // column numbers.
 char scan_next(Scanner *scanner);
@@ -59,7 +50,7 @@ bool is_delimiter(char c);
 TokenType find_primitive_type(const StringView value);
 
 // Generate a list of tokens from the given string.
-Tokens tokenize(const StringView *sv);
+Token * tokenize(const StringView *sv);
 
 #define TOK_BUF_CAP 256
 
diff --git a/src/bootstrap/main.c b/src/bootstrap/main.c
index cfad9f1..22332af 100755
--- a/src/bootstrap/main.c
+++ b/src/bootstrap/main.c
@@ -6,6 +6,8 @@
 #include <stdlib.h>
 #include <string.h>
 
+#include "darray.h"
+
 #include "singletons.c"
 
 #include "environment.c"
@@ -92,10 +94,10 @@ init(void) {
 
 void
 process_source(const StringView *source) {
-    Tokens tokens = tokenize(source);
+    Token *tokens = tokenize(source);
     if (errors_n != 0) {
-        if (tokens.buf != NULL) {
-            free(tokens.buf);
+        if (tokens != NULL) {
+            array_free(tokens);
         }
         return;
     }
@@ -122,8 +124,8 @@ process_source(const StringView *source) {
         pop_root();
     }
 
-    if (tokens.buf != NULL) {
-        free(tokens.buf);
+    if (tokens != NULL) {
+        array_free(tokens);
     }
 }
 
diff --git a/src/bootstrap/parser.c b/src/bootstrap/parser.c
index 5b0033a..a2f0f71 100644
--- a/src/bootstrap/parser.c
+++ b/src/bootstrap/parser.c
@@ -2,17 +2,17 @@
 
 Token
 peek_token(const Visitor *visitor) {
-    return visitor->tokens.buf[visitor->current];
+    return visitor->tokens[visitor->current];
 }
 
 Token
 next_token(Visitor *visitor) {
-    return visitor->tokens.buf[visitor->current++];
+    return visitor->tokens[visitor->current++];
 }
 
 bool
 has_next_token(const Visitor *visitor) {
-    return visitor->current < visitor->tokens.size;
+    return visitor->current < array_size(visitor->tokens);
 }
 
 Object *
diff --git a/src/bootstrap/parser.h b/src/bootstrap/parser.h
index 3bd17ef..3834c75 100644
--- a/src/bootstrap/parser.h
+++ b/src/bootstrap/parser.h
@@ -2,7 +2,7 @@
 #define BDL_PARSER_H
 
 typedef struct Visitor {
-    Tokens tokens;
+    Token *tokens;
     size_t current;
 } Visitor;