6 files changed, 305 insertions, 68 deletions

diff --git a/boot/common.c b/boot/common.c
index b8587bc..e453065 100644
--- a/boot/common.c
+++ b/boot/common.c
@@ -8,9 +8,6 @@
  * SPDX-License-Identifier: MPL-2.0
  */
 
-// TODO: merge our common library with `boot/runtime/core.c`
-// to avoid implementing a semi-standard library twice!
-
 #pragma once
 
 #include <math.h>
@@ -147,6 +144,146 @@ unreachable()
 // statically allocates a region of memory for a type.
 #define REGION(type, of) REGION_OF_SIZE(type, of, REGION_SIZE)
 
+// the global array data region.
+REGION(byte, array_data)
+
+// a simple fixed-size array type that uses static allocation.
+struct _Array
+{
+    uint element_size;
+    void* data;
+    uint length;
+    uint capacity;
+};
+
+#define Array(type) struct _Array
+
+// allocate memory from the static array region.
+void*
+array_allocate_static(size_t size)
+{
+    check(region_array_data_cursor + size <= ARRAY_SIZE(region_array_data), "out of array memory");
+    void* ptr = region_array_data + region_array_data_cursor;
+    region_array_data_cursor += size;
+    return ptr;
+}
+
+// creates a new, empty array with fixed capacity using static allocation.
+struct _Array
+_array_new(uint element_size, uint capacity)
+{
+    void* data = array_allocate_static(capacity * element_size);
+    struct _Array array = {
+        .element_size = element_size,
+        .data = data,
+        .length = 0,
+        .capacity = capacity,
+    };
+    return array;
+}
+
+#define array_new(type, capacity) _array_new(sizeof(type), capacity)
+
+// returns the number of elements in the array.
+uint
+array_length(const struct _Array* array)
+{
+    return array->length;
+}
+
+// returns the total capacity of the array.
+uint
+array_capacity(const struct _Array* array)
+{
+    return array->capacity;
+}
+
+// checks if the array is empty.
+bool
+array_is_empty(const struct _Array* array)
+{
+    return array->length == 0;
+}
+
+// internal use, prefer the array_push macro.
+void
+_array_push(struct _Array* array, const void* element)
+{
+    check(array->length < array->capacity, "array is full: %u/%u", array->length, array->capacity);
+    memcpy((ascii*)array->data + (array->length * array->element_size), element, array->element_size);
+    ++array->length;
+}
+
+#define array_push(array, element) _array_push(array, (const void*)(element))
+
+// internal use, prefer the array_at macro.
+void*
+_array_at(const struct _Array* array, uint index)
+{
+    check(index < array->length, "array index out of bounds: %u (length: %u)", index, array->length);
+    return (ascii*)array->data + (index * array->element_size);
+}
+
+#define array_at(type, array, index) ((type*)_array_at(array, index))
+
+// internal use, prefer the array_get macro.
+void
+_array_get(const struct _Array* array, uint index, void* out_element)
+{
+    check(index < array->length, "array index out of bounds: %u (length: %u)", index, array->length);
+    memcpy(out_element, (ascii*)array->data + (index * array->element_size), array->element_size);
+}
+
+#define array_get(array, index, out_element) _array_get(array, index, (void*)(out_element))
+
+// a slice is a view into a block of memory.
+struct _Slice
+{
+    uint element_size;
+    void* data;
+    uint length;
+};
+
+#define Slice(type) struct _Slice
+
+// creates a new slice from data.
+struct _Slice
+_slice_new(void* data, uint length, uint element_size)
+{
+    struct _Slice slice = {
+        .data = data,
+        .length = length,
+        .element_size = element_size
+    };
+    return slice;
+}
+
+#define slice_new(data, length) _slice_new((void*)(data), (length), sizeof(*(data)))
+
+// returns the length of a slice.
+uint
+slice_length(const struct _Slice* slice)
+{
+    return slice->length;
+}
+
+// internal use, prefer the slice_at macro.
+void*
+_slice_at(const struct _Slice* slice, uint index)
+{
+    check(index < slice->length, "slice index out of bounds: %u (length: %u)", index, slice->length);
+    return (ascii*)slice->data + (index * slice->element_size);
+}
+
+#define slice_at(type, slice, index) ((type*)_slice_at(slice, index))
+
+// a macro for iterating over each element in an array.
+#define FOR_EACH_ARRAY(type, element_var, array_ptr, action) \
+    for (uint i = 0; i < array_length(array_ptr); ++i) { \
+        type element_var = *array_at(type, array_ptr, i); \
+        action; \
+    }
+
 // the global string region.
 REGION(ascii, string)
 
@@ -277,19 +414,137 @@ string_equals_c_str(const struct String a, const ascii* b)
     if (string_length(a) == 0) return true;
     return memcmp(a.data, b, a.length) == 0;
 }
-void
-string_print(struct String s)
+
+// returns a null-terminated C string representation.
+// the string is already null-terminated in our implementation,
+// thus no copy is required.
+const ascii*
+string_c_str(struct String s)
 {
-    printf("%.*s", (int32)s.length, s.data);
+    return s.data;
+}
+
+// creates a new string with a character appended to
+// the end of the given string.
+struct String
+string_push(struct String s, ascii c)
+{
+    check(region_string_cursor + s.length + 2 < REGION_SIZE, "out of string memory for push");
+
+    ascii* at = region_string + region_string_cursor;
+    region_string_cursor += s.length + 2;
+
+    for (uint i = 0; i < s.length; ++i) at[i] = s.data[i];
+    at[s.length] = c;
+    at[s.length + 1] = '\0';
+
+    return (struct String){
+        .data = at,
+        .length = s.length + 1,
+    };
+}
+
+// creates a new string with the last character of
+// the given string removed.
+// pass a non-nil pointer as `removed_char` to retrieve
+// the removed character.
+struct String
+string_pop(struct String s, ascii* removed_char)
+{
+    check(s.length > 0, "cannot pop from an empty string");
+
+    if (removed_char) *removed_char = s.data[s.length - 1];
+
+    return (struct String){
+        .data = s.data,
+        .length = s.length - 1,
+    };
 }
 
+// creates a new string consisting of string `a` followed by string `b`.
+struct String
+string_append(struct String a, struct String b)
+{
+    if (string_is_empty(b)) return a;
+
+    uint new_length = a.length + b.length;
+    check(region_string_cursor + new_length + 1 < REGION_SIZE, "out of string memory for append");
+
+    ascii* at = region_string + region_string_cursor;
+    region_string_cursor += new_length + 1;
+
+    for (uint i = 0; i < a.length; ++i) at[i] = a.data[i];
+    for (uint i = 0; i < b.length; ++i) at[a.length + i] = b.data[i];
+    at[new_length] = '\0';
+
+    return (struct String){
+        .data = at,
+        .length = new_length,
+    };
+}
+
+// creates a new string consisting of string `a` followed
+// by the contents of the c-style string buffer `b`.
+struct String
+string_append_c_str(struct String a, const ascii* b)
+{
+    uint c_str_len = strlen(b);
+    if (c_str_len == 0) return a;
+
+    uint new_length = a.length + c_str_len;
+    check(region_string_cursor + new_length + 1 < REGION_SIZE, "out of string memory for append_c_str");
+
+    ascii* at = region_string + region_string_cursor;
+    region_string_cursor += new_length + 1;
+
+    for (uint i = 0; i < a.length; ++i) at[i] = a.data[i];
+    for (uint i = 0; i < c_str_len; ++i) at[a.length + i] = b[i];
+    at[new_length] = '\0';
+
+    return (struct String){
+        .data = at,
+        .length = new_length,
+    };
+}
+
+// creates a copy of a string.
+struct String
+string_clone(struct String s)
+{
+    return string_new(s.data, s.length);
+}
+
+// creates a new string consisting of a slice of the original string.
+// the slice range is defined by `[start, end)`.
+// if `start == end`, returns an empty string.
+struct String
+string_slice(struct String s, uint start, uint end)
+{
+    check(start <= end && end <= s.length, "invalid slice range [%u, %u) for string of length %u", start, end, s.length);
+
+    if (start == end) return string_empty();
+
+    uint slice_len = end - start;
+    return string_new(s.data + start, slice_len);
+}
+
+// creates a new string with the contents of string `s`,
+// with the character at index `index` modified to `c`.
+struct String
+string_set(struct String s, uint index, ascii c)
+{
+    check(index < s.length, "index out of bounds: %u (length: %u)", index, s.length);
+
+    struct String new_s = string_clone(s);
+    new_s.data[index] = c;  // safe because we just allocated this
+    return new_s;
+}
+
+// prints the contents of string `s` to stdout.
 void
-string_format(struct String s, const ascii* format, ...)
+string_print(struct String s)
 {
-    va_list args;
-    va_start(args, format);
-    vprintf(format, args);
-    va_end(args);
+    printf("%.*s", (int32)s.length, s.data);
 }
 
 enum String_Concat_Arg
@@ -301,6 +556,10 @@ enum String_Concat_Arg
 
 #define MAX_STRING_CONCAT_LENGTH 2048
 
+// concatenates multiple strings and ascii buffers into a single string.
+// each new argument is prepended by a `String_Concat_Arg` value,
+// either `ARG_STRING` or `ARG_ASCII`, followed by the argument itself.
+// the final argument must be `ARG_END`.
 struct String
 string_concatenate(enum String_Concat_Arg type1, ...)
 {
@@ -364,6 +623,8 @@ string_concatenate(enum String_Concat_Arg type1, ...)
     return string_new(buffer, total_length);
 }
 
+// creates a new string view from a substring of the given string `s`.
+// the view range is defined by `[start, end)`.
 struct String_View
 string_substring(struct String s, uint start, uint end)
 {
@@ -428,6 +689,25 @@ string_view_at(struct String_View view, uint index)
     return view.data[index];
 }
 
+// creates a new string view from a c-style string buffer.
+struct String_View
+string_view_from_c_str(const ascii* c_str)
+{
+    return (struct String_View){
+        .data = (ascii*)c_str,
+        .length = strlen(c_str),
+    };
+}
+
+// compares two string views for equality.
+bool
+string_view_equals(struct String_View a, struct String_View b)
+{
+    if (a.length != b.length) return false;
+    if (a.length == 0) return true;
+    return memcmp(a.data, b.data, a.length) == 0;
+}
+
 // prints a string view to stdout.
 void
 string_view_print(struct String_View view)
@@ -483,47 +763,6 @@ _internal_string_format(FILE* stream, uint string_length, const ascii* format, .
     va_end(args);
 }
 
-#define STRING_ARRAY_MAX 8
-
-// a string array, used for storing multiple strings.
-// if we ever need more strings, just bump `STRING_ARRAY_MAX` up.
-struct String_Array
-{
-    struct String strings[STRING_ARRAY_MAX];
-    uint count;
-};
-
-// initializes a string array with no strings.
-struct String_Array
-string_array_new(void)
-{
-    return (struct String_Array){
-        .strings = { 0 },
-        .count = 0,
-    };
-}
-
-// adds a string to the string array.
-bool
-string_array_add(struct String_Array* array, struct String string)
-{
-    if (array->count >= STRING_ARRAY_MAX) return false;
-
-    array->strings[array->count++] = string;
-    return true;
-}
-
-struct String
-string_array_at(const struct String_Array* array, uint index)
-{
-    check(index < array->count, "index out of bounds");
-    return array->strings[index];
-}
-
-#define STRING_ARRAY_FOR_EACH(cursor, str, array) \
-    struct String str = array.strings[0];         \
-    for (uint cursor = 0; cursor < array.count; str = array.strings[++cursor])
-
 // a source file given to the compiler.
 struct Source_File
 {
diff --git a/boot/parse.c b/boot/parse.c
index 481fa90..ea6b06b 100644
--- a/boot/parse.c
+++ b/boot/parse.c
@@ -499,7 +499,7 @@ parser_function_header_node(struct Parser* p, struct Parser_Error* error)
 struct Argument_Group_Node
 parser_argument_group_node(struct Parser* p, struct Parser_Error* error)
 {
-    struct String_Array argument_names = string_array_new();
+    Array(struct String) argument_names = array_new(struct String, 32);
     struct Expression *arguments_head = nil, *arguments_current = nil;
     for (;;) {
         // check if we have a named argument.
@@ -521,7 +521,7 @@ parser_argument_group_node(struct Parser* p, struct Parser_Error* error)
 
         // if we have a named argument, we need to add it to the names array,
         // otherwise we just add an empty string.
-        string_array_add(&argument_names, name);
+        array_push(&argument_names, &name);
 
         if (parser_probe(p, TOKEN_COMMA)) {
             parser_next(p);
@@ -538,7 +538,7 @@ parser_argument_group_node(struct Parser* p, struct Parser_Error* error)
 struct Bare_Declaration_Node
 parser_bare_declaration_node(struct Parser* p, struct Parser_Error* error)
 {
-    struct String_Array names = string_array_new();
+    Array(struct String) names = array_new(struct String, 16);
 
     struct Span span = { 0 };
     struct Cursor location = parser_peek(p).location;
@@ -547,7 +547,7 @@ parser_bare_declaration_node(struct Parser* p, struct Parser_Error* error)
             CHECK_RETURN(parser_need(p, TOKEN_NAME, error), struct Bare_Declaration_Node);
 
         span = span_is_empty(span) ? name_token.span : span_merge(span, name_token.span);
-        string_array_add(&names, name_token.value.name);
+        array_push(&names, &name_token.value.name);
 
         struct Token next = parser_peek(p);
         if (token_can_begin_type(&next)) break;
diff --git a/boot/runtime/core.c b/boot/runtime/core.c
index a409604..c911666 100644
--- a/boot/runtime/core.c
+++ b/boot/runtime/core.c
@@ -9,10 +9,6 @@
  * spdx-license-identifier: mpl-2.0
  */
 
-// TODO: as mentioned in `boot/common.c`, the catskill transpiled
-// source code "core" library should be merged with the catboot
-// "common" library.
-
 #pragma once
 
 // common headers for both your average catskill program.
diff --git a/boot/transpile.c b/boot/transpile.c
index 7ab13e9..01531d9 100644
--- a/boot/transpile.c
+++ b/boot/transpile.c
@@ -152,8 +152,8 @@ transpiler_visit_statement_declaration(struct Visit* visit, struct Statement* st
         struct Function_Header_Node* header = &fun->header;
 
         VISIT(visit_type_node, header->return_type);
-        fprintf(transpiler->output, " %.*s", (int)declaration->inner.names.strings[0].length,
-                declaration->inner.names.strings[0].data);
+        struct String name = *array_at(struct String, &declaration->inner.names, 0);
+        fprintf(transpiler->output, " %.*s", (int)name.length, name.data);
         VISIT(visit_function_header_node, header);
         fprintf(transpiler->output, " ");
         VISIT(visit_block_node, &fun->body);
@@ -162,8 +162,8 @@ transpiler_visit_statement_declaration(struct Visit* visit, struct Statement* st
             fprintf(transpiler->output, "const ");
         }
         VISIT(visit_type_node, declaration->inner.type);
-        fprintf(transpiler->output, " %.*s", (int)declaration->inner.names.strings[0].length,
-                declaration->inner.names.strings[0].data);
+        struct String name = *array_at(struct String, &declaration->inner.names, 0);
+        fprintf(transpiler->output, " %.*s", (int)name.length, name.data);
         if (initializer) {
             fprintf(transpiler->output, " = ");
             VISIT(visit_expression, initializer);
diff --git a/boot/tree.c b/boot/tree.c
index 228bbd4..751cf02 100644
--- a/boot/tree.c
+++ b/boot/tree.c
@@ -433,7 +433,7 @@ struct Argument_Group_Node
     struct Expression* arguments;
     // names of the arguments, if given.
     // an unnamed argument is represented as an empty string.
-    struct String_Array argument_names;
+    Array(struct String) argument_names;
 };
 
 // a declaration of a variable, constant, or other binding, without a mutability
@@ -442,7 +442,7 @@ struct Argument_Group_Node
 // a bare declaration in a for-loop, for example, is always mutable.
 struct Bare_Declaration_Node
 {
-    struct String_Array names;
+    Array(struct String) names;
     struct Expression* initializer;
     struct Type_Node* type;
 
diff --git a/boot/visit.c b/boot/visit.c
index fa49a7d..f9ad51c 100644
--- a/boot/visit.c
+++ b/boot/visit.c
@@ -1027,7 +1027,9 @@ printer_visit_bare_declaration_node(struct Visit* visit, struct Bare_Declaration
     TREE_PRINTER_PREAMBLE
 
     PRINT("(declaration ");
-    STRING_ARRAY_FOR_EACH (i, name, node->names) { PRINT("%s ", name.data); }
+    FOR_EACH_ARRAY(struct String, name, &node->names, {
+        PRINT("%s ", name.data);
+    })
 
     if (node->type && node->type->type != TYPE_NODE_NONE) {
         VISIT(visit_type_node, node->type);
@@ -1107,7 +1109,7 @@ printer_visit_argument_group_node(struct Visit* visit, struct Argument_Group_Nod
 
     uint i = 0;
     FOR_EACH (struct Expression*, argument, node->arguments) {
-        struct String name = string_array_at(&node->argument_names, i++);
+        struct String name = *array_at(struct String, &node->argument_names, i++);
         if (name.data && name.data[0] != '\0') {
             PRINT(" (named arg '%s' ", name.data);
         } else {