path: root/boot/common.c

/*
 * a small library of types, functions and macros that
 * are used throughout the bootstrap compiler.
 * allocation done purely statically.
 *
 * Copyright (c) 2025-2026, Mel G. <mel@rnrd.eu>
 *
 * SPDX-License-Identifier: MPL-2.0
 */

#pragma once

#include <fcntl.h>
#include <math.h>
#include <stdarg.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <unistd.h>

#define uint8 uint8_t
#define uint16 uint16_t
#define uint32 uint32_t
#define uint64 uint64_t

#define int8 int8_t
#define int16 int16_t
#define int32 int32_t
#define int64 int64_t

#define float32 float
#define float64 double
#define real float64

#define uint uint64
#define integer int64
#define flags int32

#define ascii char
#define byte char

#define bool _Bool
#define true 1
#define false 0
#define nil NULL
#define unknown void

#define NORETURN _Noreturn

// macro used as target for embedding binary files during build into a byte array.
// usage: `const byte test_data[] = CATBOOT_EMBED(./files/test_data.txt);`
// the array will be filled with hexadecimal values of the file contents,
// with a nil byte appended at the end.
// the size of the array can be retrieved through `strlen(array)`, or `ARRAY_SIZE(array)-1`.
#define CATBOOT_EMBED(...) { 0 }

// ansi escape codes for terminal color and style
#define ANSI(code) "\33[" code "m"

#define ANSI_RESET ANSI("0")
#define ANSI_DEFAULT ANSI("39")

#define ANSI_RED ANSI("31")
#define ANSI_RED_BG ANSI("41")
#define ANSI_GREEN ANSI("32")
#define ANSI_GREEN_BG ANSI("42")
#define ANSI_YELLOW ANSI("33")
#define ANSI_YELLOW_BG ANSI("43")
#define ANSI_BLUE ANSI("34")
#define ANSI_BLUE_BG ANSI("44")
#define ANSI_MAGENTA ANSI("35")
#define ANSI_MAGENTA_BG ANSI("45")
#define ANSI_CYAN ANSI("36")
#define ANSI_CYAN_BG ANSI("46")
#define ANSI_WHITE ANSI("37")
#define ANSI_WHITE_BG ANSI("47")
#define ANSI_BLACK ANSI("30")
#define ANSI_BLACK_BG ANSI("40")

#define ANSI_BOLD ANSI("1")
#define ANSI_NO_BOLD ANSI("22")
#define ANSI_UNDERLINE ANSI("4")
#define ANSI_NO_UNDERLINE ANSI("24")

#define FAILURE_MESSAGE ANSI_BOLD ";( sorry, a failure has occurred..." ANSI_NO_BOLD

// call on irrecoverable failure.
// prints a very sad, apologetic message for
// the user and aborts program with failure status.
NORETURN
void
failure(const ascii* message, ...)
{
    fflush(stdout); // flush stdout to ensure any message is printed before the error.

    fprintf(stderr, ANSI_RED FAILURE_MESSAGE "\n-> ");

    va_list args;
    va_start(args, message);
    vfprintf(stderr, message, args);
    va_end(args);

    fprintf(stderr, "!\n" ANSI_RESET);
    exit(EXIT_FAILURE);
}

// internal check function, use the check() macro instead.
void
_check(bool condition, const ascii* condition_str, const ascii* message, ...)
{
    if (!condition) {
        va_list args;
        va_start(args, message);
        fflush(stdout);
        fprintf(stderr, ANSI_RED FAILURE_MESSAGE "\n");
        fprintf(stderr, "-> check failed: %s\n", condition_str);
        fprintf(stderr, "-> ");
        vfprintf(stderr, message, args);
        fprintf(stderr, "!\n" ANSI_RESET);
        va_end(args);
        exit(EXIT_FAILURE);
    }
}

// check a condition, triggering a failure if it's false.
// prints both the condition and the formatted message.
#define check(condition, message, ...) _check((condition), #condition, (message), ##__VA_ARGS__)

NORETURN
void
unreachable()
{
    failure("unreachable code reached");
}

// log out a message with a debug prefix.
// does not print additional \n at the end.
void
log_debug(const ascii* message, ...)
{
    fflush(stdout);
    fprintf(stderr, ANSI_BOLD ANSI_CYAN "debug. " ANSI_NO_BOLD);

    va_list args;
    va_start(args, message);
    vfprintf(stderr, message, args);
    va_end(args);

    fprintf(stderr, ANSI_RESET);
}

// log out a message with a warning prefix.
// does not print additional \n at the end.
void
log_warning(const ascii* message, ...)
{
    fflush(stdout);
    fprintf(stderr, ANSI_BOLD ANSI_YELLOW "warning? " ANSI_NO_BOLD);

    va_list args;
    va_start(args, message);
    vfprintf(stderr, message, args);
    va_end(args);

    fprintf(stderr, ANSI_RESET);
}

// log out a message with an error prefix.
// does not print additional \n at the end.
void
log_error(const ascii* message, ...)
{
    fflush(stdout);
    fprintf(stderr, ANSI_BOLD ANSI_RED "error! " ANSI_NO_BOLD);

    va_list args;
    va_start(args, message);
    vfprintf(stderr, message, args);
    va_end(args);

    fprintf(stderr, ANSI_RESET);
}

// for each entry in a linked list.
#define FOR_EACH(type, cursor, head) for (type cursor = head; cursor != nil; cursor = cursor->next)

#define ARRAY_SIZE(array) (sizeof(array) / sizeof((array)[0]))

// the common size of region memory blocks.
#define REGION_SIZE 1048576

// statically allocates a region of memory of a given size
// for a single type.
#define REGION_OF_SIZE(type, of, size) \
    type region_##of[size];            \
    uint region_##of##_cursor = 0;

// 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.
// for each iteration you get a pointer to the current element.
#define FOR_EACH_ARRAY(type, element_var, array_ptr)   \
    for (type* element_var = (type*)(array_ptr)->data; \
         element_var < (type*)(array_ptr)->data + array_length(array_ptr); ++element_var)

// the global string region.
REGION(ascii, string)

// a string.
// an immutable sequence of ascii characters.
struct String
{
    ascii* data;
    uint length;
};

// a view of a string.
// used for passing around strings without copying them,
// it is not assumed to have a permanent lifetime,
// nor is it guaranteed to be null-terminated.
struct String_View
{
    ascii* data;
    uint length;
};

// formats and prints a string with a given format to stdout.
// to use the given string in the format, use the `%S` specifier.
// the string is required to be the first argument in the format string.
// accepts both `struct String` and `struct String_View`.
#define STRING_FORMAT(s, format, ...) \
    _internal_string_format(stdout, s.length, format, s.data, ##__VA_ARGS__)

// formats and prints a string with a given format to `stream`.
// to use the given string in the format, use the `%S` specifier.
// the string is required to be the first argument in the format string.
// accepts both `struct String` and `struct String_View`.
#define STRING_FORMAT_TO(s, stream, format, ...) \
    _internal_string_format(stream, s.length, format, s.data, ##__VA_ARGS__)

// iterates over each character in a string.
// accepts both `struct String` and `struct String_View`.
#define STRING_ITERATE(index, c, str) \
    ascii c = str.data[0];            \
    for (uint index = 0; index < str.length; c = str.data[++index])

// allocates a new string in the global string region.
struct String
string_new(const ascii* data, uint length)
{
    // for compatibility, we include an additional null byte at the end.
    uint allocation_length = length + 1;
    check(region_string_cursor + allocation_length < REGION_SIZE, "out of string memory");

    ascii* at = region_string + region_string_cursor;
    region_string_cursor += allocation_length;

    for (uint i = 0; i < length; ++i) at[i] = data[i];
    at[length] = '\0';

    return (struct String){
        .data = at,
        .length = length,
    };
}

struct String
string_empty(void)
{
    return (struct String){
        .data = nil,
        .length = 0,
    };
}

bool
string_is_empty(struct String s)
{
    return s.data == nil || s.length == 0;
}

// allocates a new string in the global string region,
// taking the data from a null-terminated C string.
struct String
string_from_c_string(const char* c_string)
{
    uint length = strlen(c_string);
    return string_new(c_string, length);
}

// allocates a new string in the global string region,
// taking the data from a static null-terminated C string.
//
// NOTE: The string is not copied, so it MUST have a lifetime
// spanning the entire program.
struct String
string_from_static_c_string(const char* c_string)
{
    uint length = strlen(c_string);
    return (struct String){
        .data = (ascii*)c_string,
        .length = length,
    };
}

// returns the character at a given index.
// does bounds-checking.
ascii
string_at(struct String s, uint index)
{
    check(index < s.length, "index out of bounds");
    return s.data[index];
}

uint
string_length(struct String s)
{
    return s.length;
}

bool
string_equals(const struct String a, const struct String b)
{
    if (string_length(a) != string_length(b)) return false;
    if (string_length(a) == 0) return true;
    return memcmp(a.data, b.data, a.length) == 0;
}

bool
string_equals_c_str(const struct String a, const ascii* b)
{
    uint b_length = strlen(b);
    if (string_length(a) != b_length) return false;
    if (string_length(a) == 0) return true;
    return memcmp(a.data, b, a.length) == 0;
}

// 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)
{
    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_print(struct String s)
{
    printf("%.*s", (int32)s.length, s.data);
}

enum String_Concat_Arg
{
    ARG_END,
    ARG_STRING,
    ARG_ASCII,
};

#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, ...)
{
    va_list args;
    va_start(args, type1);
    uint total_length = 0;
    enum String_Concat_Arg type = type1;
    while (type != ARG_END) {
        switch (type) {
        case ARG_STRING: {
            struct String s = va_arg(args, struct String);
            if (!string_is_empty(s)) total_length += s.length;
            break;
        }
        case ARG_ASCII: {
            ascii* str = va_arg(args, ascii*);
            if (str) total_length += strlen(str);
            break;
        }
        default:
            break;
        }
        type = va_arg(args, enum String_Concat_Arg);
    }
    va_end(args);

    if (total_length == 0) return string_empty();

    check(total_length < MAX_STRING_CONCAT_LENGTH - 1, "string concatenation too long");
    ascii buffer[MAX_STRING_CONCAT_LENGTH];

    ascii* cursor = buffer;
    va_start(args, type1);
    type = type1;
    while (type != ARG_END) {
        switch (type) {
        case ARG_STRING: {
            struct String s = va_arg(args, struct String);
            if (!string_is_empty(s)) {
                memcpy(cursor, s.data, s.length);
                cursor += s.length;
            }
            break;
        }
        case ARG_ASCII: {
            ascii* str = va_arg(args, ascii*);
            if (str) {
                uint length = strlen(str);
                memcpy(cursor, str, length);
                cursor += length;
            }
            break;
        }
        default:
            break;
        }
        type = va_arg(args, enum String_Concat_Arg);
    }
    va_end(args);

    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)
{
    check(start <= end && end <= s.length, "substring out of bounds");
    return (struct String_View){
        .data = s.data + start,
        .length = end - start,
    };
}

// creates a new string view from an ascii buffer.
// the buffer is not copied, so it must have a lifetime
// spanning the at least the lifetime of the string view.
// null-termination is not required.
struct String_View
string_view_new(ascii* data, uint length)
{
    return (struct String_View){
        .data = data,
        .length = length,
    };
}

// creates a new string view from a string.
struct String_View
string_view_from_string(struct String s)
{
    return (struct String_View){
        .data = s.data,
        .length = s.length,
    };
}

// creates empty string view.
struct String_View
string_view_empty(void)
{
    return (struct String_View){
        .data = nil,
        .length = 0,
    };
}

// checks if a string view is empty.
bool
string_view_is_empty(struct String_View view)
{
    return view.data == nil || view.length == 0;
}

uint
string_view_length(struct String_View view)
{
    return view.length;
}

// returns the character at a given index in a string view.
ascii
string_view_at(struct String_View view, uint index)
{
    check(index < view.length, "index out of bounds");
    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)
{
    printf("%.*s", (int32)view.length, view.data);
}

#define MAX_FORMAT_STRING_SIZE 256

// creates a real c format string from our faux-format string.
// example:
//   "Hello %S! You are %d years old."
// becomes:
//   "Hello %.6s! You are %d years old."
// if we assume the string length is 6.
void
_internal_prepare_format_string(ascii* format_buffer, const ascii* format, uint static_length)
{
    ascii specifier[10];
    int specifier_length = snprintf(specifier, sizeof(specifier), "%%.%lus", static_length);
    check(specifier_length < sizeof(specifier), "string to format is too long");

    for (uint fi = 0, fbi = 0; fi < MAX_FORMAT_STRING_SIZE && fbi < MAX_FORMAT_STRING_SIZE;
         ++fi, ++fbi) {
        ascii c = format[fi];
        format_buffer[fbi] = c;

        if (c == '\0') break;

        // check if the next character is the format specifier 'S', that
        // we specified as our own custom format specifier.
        if (c == '%' && format[fi + 1] == 'S') {
            // copy the specifier into the format buffer.
            for (uint si = 0; si < specifier_length; ++si, ++fbi)
                format_buffer[fbi] = specifier[si];
            fbi--, fi++; // increment `fi` to skip 'S', decrement `fbi` to not leave a gap.
        }
    }
}

// formats a string using the given faux-format string, printing it to `stream`.
// the first VA arguments is expected to be the string data.
// do not use directly! use `STRING_FORMAT_TO`.
void
_internal_string_format(FILE* stream, uint string_length, const ascii* format, ...)
{
    ascii format_buffer[MAX_FORMAT_STRING_SIZE];
    _internal_prepare_format_string(format_buffer, format, string_length);

    va_list args;
    va_start(args, format);
    vfprintf(stream, format_buffer, args);
    va_end(args);
}

// a string buffer with a fixed capacity, the contents
// of which can be modified.
// essentially, a mutable string with a maximum size.
struct String_Buffer
{
    ascii* data;
    uint length;
    uint capacity;
};

// creates a new string buffer with the given capacity.
struct String_Buffer
string_buffer_new(uint capacity)
{
    check(capacity + 1 < REGION_SIZE - region_string_cursor,
          "out of string memory for string buffer");

    ascii* at = region_string + region_string_cursor;
    region_string_cursor += capacity + 1;

    at[0] = '\0';

    return (struct String_Buffer){
        .data = at,
        .length = 0,
        .capacity = capacity,
    };
}

// creates a new empty string buffer.
struct String_Buffer
string_buffer_empty(void)
{
    // we still technically allocate one byte of string memory for the
    // empty string buffer and its null-terminator, but that shouldn't be an issue.
    return string_buffer_new(0);
}

// returns the length of the string buffer.
uint
string_buffer_length(const struct String_Buffer* buffer)
{
    return buffer->length;
}

// returns the capacity of the string buffer.
uint
string_buffer_capacity(const struct String_Buffer* buffer)
{
    return buffer->capacity;
}

// checks if the string buffer is empty.
bool
string_buffer_is_empty(const struct String_Buffer* buffer)
{
    return buffer->length == 0;
}

// returns the character at a given index.
// does bounds-checking.
ascii
string_buffer_at(const struct String_Buffer* buffer, uint index)
{
    check(index < buffer->length, "index out of bounds");
    return buffer->data[index];
}

// clears the string buffer, setting its length to zero.
void
string_buffer_clear(struct String_Buffer* buffer)
{
    buffer->length = 0;
    buffer->data[0] = '\0';
}

// appends a character to the string buffer.
void
string_buffer_push(struct String_Buffer* buffer, ascii c)
{
    check(buffer->length < buffer->capacity, "string buffer is full: %u/%u", buffer->length,
          buffer->capacity);
    buffer->data[buffer->length] = c;
    ++buffer->length;
    buffer->data[buffer->length] = '\0';
}

// removes the last character from the string buffer.
// pass a non-nil pointer as `removed_char` to retrieve
// the removed character.
void
string_buffer_pop(struct String_Buffer* buffer, ascii* removed_char)
{
    check(buffer->length > 0, "cannot pop from an empty string buffer");

    --buffer->length;
    if (removed_char) *removed_char = buffer->data[buffer->length];
    buffer->data[buffer->length] = '\0';
}

// appends a string to the string buffer.
void
string_buffer_append(struct String_Buffer* buffer, struct String s)
{
    if (string_is_empty(s)) return;

    check(buffer->length + s.length <= buffer->capacity, "string buffer overflow: %u + %u > %u",
          buffer->length, s.length, buffer->capacity);

    for (uint i = 0; i < s.length; ++i) { buffer->data[buffer->length + i] = s.data[i]; }
    buffer->length += s.length;
    buffer->data[buffer->length] = '\0';
}

// pairs with `%S` in the printf-like formatters below.
#define STR(s) (int)(s).length, (s).data

void
_format_translate_format(ascii* dst, const ascii* src, uint dst_size)
{
    uint si = 0, di = 0;
    while (di + 4 < dst_size) {
        ascii c = src[si];
        if (c == '\0') break;
        if (c == '%' && src[si + 1] == 'S') {
            dst[di++] = '%';
            dst[di++] = '.';
            dst[di++] = '*';
            dst[di++] = 's';
            si += 2;
        } else {
            dst[di++] = c;
            si++;
        }
    }
    dst[di] = '\0';
}

#define MAX_FORMATTED_STRING_SIZE 1024

struct String
string_vformat(const ascii* format, va_list args)
{
    ascii translated[MAX_FORMAT_STRING_SIZE];
    _format_translate_format(translated, format, sizeof translated);

    ascii buffer[MAX_FORMATTED_STRING_SIZE];
    int written = vsnprintf(buffer, sizeof buffer, translated, args);
    check(written >= 0, "vsnprintf failed");
    return string_new(buffer, (uint)written);
}

struct String
string_format(const ascii* format, ...)
{
    va_list args;
    va_start(args, format);
    struct String result = string_vformat(format, args);
    va_end(args);
    return result;
}

// appends a C-style string to the string buffer.
void
string_buffer_append_c_str(struct String_Buffer* buffer, const ascii* c_str)
{
    uint c_str_len = strlen(c_str);
    if (c_str_len == 0) return;

    check(buffer->length + c_str_len <= buffer->capacity, "string buffer overflow: %u + %u > %u",
          buffer->length, c_str_len, buffer->capacity);

    for (uint i = 0; i < c_str_len; ++i) buffer->data[buffer->length + i] = c_str[i];

    buffer->length += c_str_len;
    buffer->data[buffer->length] = '\0';
}

// appends a formatted string to the buffer.
void
string_buffer_appendf(struct String_Buffer* buffer, const ascii* format, ...)
{
    va_list args;
    va_start(args, format);
    struct String formatted = string_vformat(format, args);
    va_end(args);
    string_buffer_append(buffer, formatted);
}

// converts the string buffer to an immutable string.
// allocates a new string in the string region.
struct String
string_buffer_to_string(const struct String_Buffer* buffer)
{
    return string_new(buffer->data, buffer->length);
}

// prints the contents of the string buffer to stdout.
void
string_buffer_print(const struct String_Buffer* buffer)
{
    printf("%.*s", (int32)buffer->length, buffer->data);
}

// a source file given to the compiler.
struct Source_File
{
    struct String source;
    // path to the source file, relative to the current working directory.
    struct String path;
};

// byte position within a file.
typedef uint64 Pos;

// an extent of text within a file,
// defined by its start and end byte positions.
struct Span
{
    Pos start;
    Pos end;
};

struct Span
span_new(Pos start, Pos end)
{
    return (struct Span){ .start = start, .end = end };
}

struct Span
span_empty(void)
{
    return (struct Span){ 0, 0 };
}

struct Span
span_width(Pos start, uint width)
{
    return (struct Span){ .start = start, .end = start + width };
}

// create a span which encompasses two spans.
struct Span
span_merge(struct Span a, struct Span b)
{
    return (struct Span){
        .start = a.start < b.start ? a.start : b.start,
        .end = a.end > b.end ? a.end : b.end,
    };
}

// expand a span by a number of bytes.
// negative number expands the span to the left,
// positive number expands the span to the right.
struct Span
span_expand(struct Span span, integer by)
{
    uint start_expand = by < 0 ? -by : 0;
    uint end_expand = by > 0 ? by : 0;
    return (struct Span){
        .start = span.start - start_expand,
        .end = span.end + end_expand,
    };
}

// check if two spans are equal.
bool
span_equals(struct Span a, struct Span b)
{
    return a.start == b.start && a.end == b.end;
}

// check if span equals = { 0, 0 }.
bool
span_is_empty(struct Span span)
{
    return span_equals(span, (struct Span){ 0, 0 });
}

uint
span_length(struct Span span)
{
    uint length = span.end - span.start;
    return length == 0 ? 1 : length;
}

// a cursor position placed within a text file.
struct Cursor
{
    uint line;
    uint column;
};

struct Cursor
cursor_new(uint line, uint column)
{
    return (struct Cursor){ .line = line, .column = column };
}

struct Cursor
cursor_empty(void)
{
    return cursor_new(0, 0);
}

enum Diagnostic_Severity
{
    DIAGNOSTIC_NOTE,
    DIAGNOSTIC_WARNING,
    DIAGNOSTIC_ERROR,
};

struct Diagnostic
{
    enum Diagnostic_Severity severity;
    struct Span span;
    // first line of the rendered diagnostic. may contain `\n` to introduce
    // extra body lines, each indented under the headline.
    struct String message;
    // optional. rendered as `hint: <hint>` under the body when non-empty.
    struct String hint;
    // NOTE(mel): probably overkill for bootstrapping, but i kind of want to figure
    // the error format out for future iterations, and want to see it in action,
    // to have more thoughts about improving it later on.
};

const ascii*
diagnostic_severity_label(enum Diagnostic_Severity severity)
{
    switch (severity) {
    case DIAGNOSTIC_NOTE:
        return "note.";
    case DIAGNOSTIC_WARNING:
        return "warning?";
    case DIAGNOSTIC_ERROR:
        return "error!";
    default:
        return "diagnostic";
    }
}

const ascii*
diagnostic_severity_color(enum Diagnostic_Severity severity)
{
    switch (severity) {
    case DIAGNOSTIC_NOTE:
        return ANSI_BLUE;
    case DIAGNOSTIC_WARNING:
        return ANSI_YELLOW;
    case DIAGNOSTIC_ERROR:
        return ANSI_RED;
    default:
        return ANSI_WHITE;
    }
}

// line and column are 1-based.
void
source_position_from_span(struct String source, struct Span span, uint* out_line, uint* out_column)
{
    uint line = 1, column = 1;
    uint upto = span.start;
    if (upto > string_length(source)) upto = string_length(source);
    for (uint i = 0; i < upto; ++i) {
        if (string_at(source, i) == '\n') {
            line++;
            column = 1;
        } else {
            column++;
        }
    }
    *out_line = line;
    *out_column = column;
}

struct Span
source_line_span(struct String source, struct Span span)
{
    Pos line_start = span.start, line_end = span.start;
    while (line_start > 0 && string_at(source, line_start - 1) != '\n') line_start--;
    while (line_end < string_length(source) && string_at(source, line_end) != '\n') line_end++;
    return span_new(line_start, line_end);
}

// render a diagnostic to a stream.
void
diagnostic_display(struct Source_File source, struct Diagnostic* d, FILE* out)
{
    uint line, column;
    source_position_from_span(source.source, d->span, &line, &column);

    STRING_FORMAT_TO(source.path, out, ANSI_WHITE "%s:%lu:%lu:\n", line, column);

    // first line of the message is the headline. anything after a `\n` is body.
    uint headline_end = 0;
    while (headline_end < d->message.length && d->message.data[headline_end] != '\n')
        headline_end++;

    fprintf(out, ANSI_BOLD "%s%s " ANSI_WHITE, diagnostic_severity_color(d->severity),
            diagnostic_severity_label(d->severity));
    fprintf(out, "%.*s", (int)headline_end, d->message.data);
    if (d->severity == DIAGNOSTIC_ERROR) fprintf(out, " :(");
    fprintf(out, "\n" ANSI_NO_BOLD);

    if (headline_end < d->message.length) {
        uint body_start = headline_end + 1;
        fprintf(out, "%.*s\n", (int)(d->message.length - body_start), d->message.data + body_start);
    }

    if (!string_is_empty(d->hint)) STRING_FORMAT_TO(d->hint, out, "  hint: %S\n");

    struct Span line_span = source_line_span(source.source, d->span);
    struct String_View source_line =
        string_substring(source.source, line_span.start, line_span.end);

    fprintf(out, ANSI_WHITE "%lu| ", line);
    STRING_FORMAT_TO(source_line, out, "%S\n");

    uint line_number_length = ceil(log10(line + 1));
    fprintf(out, "%s%*s", diagnostic_severity_color(d->severity),
            (int)(column + 1 + line_number_length), " ");
    uint width = span_length(d->span);
    if (width == 0) width = 1;
    for (uint w = 0; w < width; w++) fprintf(out, "^");
    fprintf(out, "\n" ANSI_RESET);
}

void
diagnostic_push_str(
    Array(struct Diagnostic) * into, bool* out_had_error, enum Diagnostic_Severity severity,
    struct Span span, struct String message)
{
    struct Diagnostic d = { .severity = severity, .span = span, .message = message };
    array_push(into, &d);
    if (out_had_error && severity == DIAGNOSTIC_ERROR) *out_had_error = true;
}

void
diagnostic_push(
    Array(struct Diagnostic) * into, bool* out_had_error, enum Diagnostic_Severity severity,
    struct Span span, const ascii* format, ...)
{
    va_list args;
    va_start(args, format);
    struct String message = string_vformat(format, args);
    va_end(args);
    diagnostic_push_str(into, out_had_error, severity, span, message);
}

#define diagnostic_emit(unit, severity, span, ...) \
    diagnostic_push(&(unit)->diagnostics, &(unit)->had_error, severity, span, __VA_ARGS__)

#define diagnostic_emit_str(unit, severity, span, message) \
    diagnostic_push_str(&(unit)->diagnostics, &(unit)->had_error, severity, span, message)

void
diagnostic_render(
    struct Source_File source, FILE* out, enum Diagnostic_Severity severity, struct Span span,
    const ascii* format, ...)
{
    va_list args;
    va_start(args, format);
    struct String message = string_vformat(format, args);
    va_end(args);

    struct Diagnostic d = { .severity = severity, .span = span, .message = message };
    diagnostic_display(source, &d, out);
}

// single iteration of the CRC32 checksum algorithm
// described in POSIX.
// see: https://pubs.opengroup.org/onlinepubs/9799919799/utilities/cksum.html
// used by `crc32_posix`.
uint32
crc32_posix_iteration(uint32 initial_hash, uint8 octet)
{
    const uint32 iso_polynomial = 0x4C11DB7;

    octet ^= initial_hash >> 24;
    uint32 hash = 0;
    uint32 poly = iso_polynomial;
    for (uint8 bit = 0; bit < 8; bit++) {
        if (octet & (1 << bit)) hash ^= poly;

        uint32 poly_msb = poly & (1 << 31);
        poly <<= 1;
        if (poly_msb) poly ^= iso_polynomial;
    }

    return hash ^ (initial_hash << 8);
}

// terse implementation of the POSIX CRC32 checksum algorithm
// meant for the `cksum` utility, which can be used through
// the GNU coreutils `cksum command`:
// `echo -ne "string to hash" | cksum`
// see: https://pubs.opengroup.org/onlinepubs/9799919799/utilities/cksum.html
uint32
crc32_posix(struct String str)
{
    uint32 hash = 0;
    STRING_ITERATE(i, c, str)
    {
        hash = crc32_posix_iteration(hash, c);
    }

    uint32 length = string_length(str);
    while (length) {
        hash = ~crc32_posix_iteration(hash, length);
        length >>= 8;
    }

    return hash;
}

// FNV-1a hashing algorithm, 64-bit variant.
// teeny-tiny, fast, pretty okay-ish distribution, and just about good
// enough for content-addressing and de-duplication!
// see: https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
uint64
fnv1a_64(struct String str)
{
    const uint64 fnv_offset_basis = 0xCBF29CE484222325ULL;
    const uint64 fnv_prime = 0x100000001B3ULL;

    uint64 hash = fnv_offset_basis;
    STRING_ITERATE(i, byte_of_data, str)
    {
        hash ^= (uint64)byte_of_data;
        hash *= fnv_prime;
    }
    return hash;
}