// This file defines type info and methods for the Text datatype, which uses
// libunistr for Unicode support and implements a datastructure based on a
// hybrid of Raku/MoarVM's space-efficient grapheme cluster representation of
// strings, combined with a mostly-balanced tree datastructure based on Cords
// (Boehm et al), which have good runtime performance for text constructed by a
// series of many concatenations. In practice, this means Tomo's Text has an
// extremely compact memory footprint (typically as compact as UTF8 or
// up to 2x better for some languages), with extremely fast operations
// including concatenation, random indexing, and taking substrings.

// For more information on MoarVM's grapheme cluster strings, see:
//     https://docs.raku.org/language/unicode
//     https://github.com/MoarVM/MoarVM/blob/main/docs/strings.asciidoc
// For more information on Cords, see the paper "Ropes: an Alternative to
// Strings" (Boehm, Atkinson, Plass 1995):
//     https://www.cs.tufts.edu/comp/150FP/archive/hans-boehm/ropes.pdf

// Tomo's Text datatype represents Unicode text that is fully normalized using
// normalization form C (NFC). This means that all text created from source code
// or read in at runtime will respect normalization during comparison and other
// operations, and the original (potentially non-canonical) representation of
// text is not preserved. This also means that byte sequences that do not
// represent valid unicode text cannot be interpreted as the Text datatype. For
// example, a file with malformed UTF8 sequences cannot be read as Text.

// A note on grapheme clusters: In Unicode, the fundamental unit is the
// "codepoint", which represents things like letters, symbols, emojis,
// combiners, and modifiers that alter other codepoints. However, most people
// have an intuitive notion of what a "letter" is that corresponds to the
// concept formally known as a grapheme cluster. A grapheme cluster is roughly
// speaking the amount of text that your cursor moves over when you press the
// left or right arrow key once. This often corresponds to a single codepoint,
// but some codepoints act as modifiers on other codepoints. For example, U+0301
// (COMBINING ACUTE ACCENT) can modify a letter like "e" to form "é". During
// normalization, this frequently resolves down to a single unicode codepoint,
// in this case, "é" resolves to the single codepoint U+00E9 (LATIN SMALL LETTER
// E WITH ACUTE). However, in some cases, multiple codepoints make up a grapheme
// cluster but *don't* normalize to a single codepoint. For example, LATIN SMALL
// LETTER E (U+0065) + COMBINING VERTICAL LINE BELOW (U+0329) combine to form an
// unusual glyph that is not used frequently enough to warrant its own unique
// codepoint (this is basically what Zalgo text is). Emojis also use the ZERO
// WIDTH JOINER (U+200D) to add gender, skin tone, or other modifiers to emojis.
// Tomo takes an opinionated stance that grapheme clusters, not codepoints or
// bytes, are more useful to people when doing text operations like getting the
// "length" of a text or accessing the Nth "letter" of a text. If someone sends
// you a text with WOMAN (U+1F469) + ZERO WIDTH JOINER (U+200D) + ROCKET
// (U+1F680) followed by THUMBS UP (U+1F44D), it will render on your screen as
// two things: a female astronaut and a thumbs up, and this is how most people
// will think about the text. If you wish to operate on the raw codepoints that
// comprise the message, you are free to do so with the `.utf32()`
// method and `Text.from_utf32()`, but this is not the default behavior.
// The behavior for the given example is that `text.length == 2`, `text[1]` is
// the grapheme cluster representing a female astronaut emoji, and `text[2]` is
// the grapheme cluster representing the thumbs up emoji.

// There are a lot of benefits to storing unicode text with one grapheme
// cluster per index in a densely packed list instead of storing the text as
// variable-width UTF8-encoded bytes. It lets us have one canonical length for
// the text that can be precomputed and is meaningful to users. It lets us
// quickly get the Nth "letter" in the text. Substring slicing is fast.
// However, since not all grapheme clusters take up the same number of
// codepoints, we're faced with the problem of how to jam multiple codepoints
// into a single 32-bit slot. Inspired by Raku and MoarVM's approach, this
// implementation uses "synthetic graphemes" (in Raku's terms, Normal Form
// Graphemes, aka NFG). A synthetic grapheme is a negative 32-bit signed
// integer that represents a multi-codepoint grapheme cluster that has been
// encountered during the program's runtime. These clusters are stored in a
// lookup list and hash map so that we can rapidly convert between the
// synthetic grapheme integer ID and the unicode codepoints associated with it.
// Essentially, it's like we create a supplement to the unicode standard with
// things that would be nice if they had their own codepoint so things worked
// out nicely because we're using them right now, and we'll give them a
// negative number so it doesn't overlap with any real codepoints.

// Example 1: U+0048, U+00E9 AKA: LATIN CAPITAL LETTER H, LATIN SMALL LETTER E
// WITH ACUTE This would be stored as: (int32_t[]){0x48, 0xE9} Example 2:
// U+0048, U+0065, U+0309 AKA: LATIN CAPITAL LETTER H, LATIN SMALL LETTER E,
// COMBINING VERTICAL LINE BELOW This would be stored as: (int32_t[]){0x48, -2}
// Where -2 is used as a lookup in a list that holds the actual unicode
// codepoints: (ucs4_t[]){0x65, 0x0309}

// The text datastructure also uses a compact encoding (TEXT_BLOB) to store a
// per-chunk compressed form of the text when long stretches of text contain
// 256 or fewer unique grapheme clusters, which lets the text use a single byte
// for each grapheme cluster along with a lookup table. For typical text
// written in a variety of non-English natural languages (e.g. Spanish, Arabic,
// Japanese, Greek, German, Finnish, Basque), the in-memory representation
// takes up between 50-101% as much space as UTF8 encoding and between 24-39%
// as much space as UTF32 encoding, but with the advantage of extremely fast
// random access for indexing or slicing, unlike UTF8. In other words, this
// representation offers ASCII-like compactness and fast random access for
// non-English languages.

#include <assert.h>
#include <ctype.h>
#include <gc.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <sys/param.h>

#include "../unistr-fixed.h"

#include <unicase.h>
#include <unictype.h>
#include <unigbrk.h>
#include <uniname.h>
#include <unistring/version.h>
#include <uniwidth.h>

#include "bytes.h"
#include "datatypes.h"
#include "integers.h"
#include "lists.h"
#include "optionals.h"
#include "tables.h"
#include "text.h"

// Use inline version of the siphash code for performance:
#include "siphash-internals.h"
#include "siphash.h"

typedef struct {
    ucs4_t main_codepoint;
    ucs4_t *utf32_cluster; // length-prefixed
    const uint8_t *utf8;
} synthetic_grapheme_t;

// Synthetic grapheme clusters (clusters of more than one codepoint):
static Table_t grapheme_ids_by_codepoints = EMPTY_TABLE; // ucs4_t* length-prefixed codepoints -> int32_t ID

// This will hold a dynamically growing list of synthetic graphemes:
static synthetic_grapheme_t *synthetic_graphemes = NULL;
static int32_t synthetic_grapheme_capacity = 0;
static int32_t num_synthetic_graphemes = 0;

#define NUM_GRAPHEME_CODEPOINTS(id) (synthetic_graphemes[-(id) - 1].utf32_cluster[0])
#define GRAPHEME_CODEPOINTS(id) (&synthetic_graphemes[-(id) - 1].utf32_cluster[1])
#define GRAPHEME_UTF8(id) (synthetic_graphemes[-(id) - 1].utf8)

// Somewhat arbitrarily chosen, if two short literal ASCII or grapheme chunks
// are concatenated below this length threshold, we just merge them into a
// single literal node instead of a concatenation node.
#define SHORT_ASCII_LENGTH 64
#define SHORT_GRAPHEMES_LENGTH 16

static Text_t simple_concatenation(Text_t a, Text_t b);

PUREFUNC static bool graphemes_equal(const void *va, const void *vb, const TypeInfo_t *info) {
    (void)info;
    ucs4_t *a = *(ucs4_t **)va;
    ucs4_t *b = *(ucs4_t **)vb;
    if (a[0] != b[0]) return false;
    for (int i = 0; i < (int)a[0]; i++)
        if (a[i] != b[i]) return false;
    return true;
}

PUREFUNC static uint64_t grapheme_hash(const void *g, const TypeInfo_t *info) {
    (void)info;
    ucs4_t *cluster = *(ucs4_t **)g;
    return siphash24((void *)&cluster[1], sizeof(ucs4_t[cluster[0]]));
}

static const TypeInfo_t GraphemeClusterInfo = {
    .size = sizeof(ucs4_t *),
    .align = __alignof__(ucs4_t *),
    .metamethods =
        {
            .equal = graphemes_equal,
            .hash = grapheme_hash,
        },
};

#ifdef __GNUC__
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wstack-protector"
#endif
public
int32_t get_synthetic_grapheme(const ucs4_t *codepoints, int64_t utf32_len) {
    if (utf32_len == 1) return (int32_t)*codepoints;

    ucs4_t length_prefixed[1 + utf32_len];
    length_prefixed[0] = (ucs4_t)utf32_len;
    for (int i = 0; i < utf32_len; i++)
        length_prefixed[i + 1] = codepoints[i];
    ucs4_t *ptr = &length_prefixed[0];

    // Optimization for common case of one frequently used synthetic grapheme:
    static int32_t last_grapheme = 0;
    if (last_grapheme != 0 && graphemes_equal(&ptr, &synthetic_graphemes[-last_grapheme - 1].utf32_cluster, NULL))
        return last_grapheme;

    TypeInfo_t GraphemeIDLookupTableInfo = *Table$info(&GraphemeClusterInfo, &Int32$info);
    int32_t *found = Table$get(grapheme_ids_by_codepoints, &ptr, &GraphemeIDLookupTableInfo);
    if (found) return *found;

    // New synthetic grapheme:
    if (num_synthetic_graphemes >= synthetic_grapheme_capacity) {
        // If we don't have space, allocate more:
        synthetic_grapheme_capacity = MAX(128, synthetic_grapheme_capacity * 2);
        synthetic_grapheme_t *new = GC_MALLOC_ATOMIC(sizeof(synthetic_grapheme_t[synthetic_grapheme_capacity]));
        memcpy(new, synthetic_graphemes, sizeof(synthetic_grapheme_t[num_synthetic_graphemes]));
        synthetic_graphemes = new;
    }

    int32_t grapheme_id = -(num_synthetic_graphemes + 1);
    num_synthetic_graphemes += 1;

    // Get UTF8 representation:
    uint8_t u8_buf[64];
    size_t u8_len = sizeof(u8_buf) / sizeof(u8_buf[0]);
    uint8_t *u8 = u32_to_u8(codepoints, (size_t)utf32_len, u8_buf, &u8_len);
    if (u8 == NULL) fail("Invalid graphemes encountered!");

    // For performance reasons, use an arena allocator here to ensure that
    // synthetic graphemes store all of their information in a densely packed
    // area with good cache locality:
    static void *arena = NULL, *arena_end = NULL;
    if (arena != NULL && (size_t)arena % __alignof__(ucs4_t) != 0)
        arena += __alignof__(ucs4_t) - ((size_t)arena % __alignof__(ucs4_t));

    // If we have filled up this arena, allocate a new one:
    size_t needed_memory = sizeof(ucs4_t[1 + utf32_len]) + sizeof(uint8_t[u8_len + 1]);
    if (arena == NULL || arena + needed_memory > arena_end) {
        // Do reasonably big chunks at a time, so most synthetic codepoints are
        // nearby each other in memory and cache locality is good. This is a
        // rough guess at a good size:
        size_t chunk_size = MAX(needed_memory, 512);
        arena = GC_MALLOC_ATOMIC(chunk_size);
        assert(arena != NULL);
        arena_end = arena + chunk_size;
    }

    // Copy length-prefixed UTF32 codepoints into the arena and store where they live:
    ucs4_t *codepoint_copy = arena;
    memcpy(codepoint_copy, length_prefixed, sizeof(ucs4_t[1 + utf32_len]));
    synthetic_graphemes[-grapheme_id - 1].utf32_cluster = codepoint_copy;
    arena += sizeof(ucs4_t[1 + utf32_len]);

    // Copy UTF8 units into the arena and store where they live:
    uint8_t *utf8_final = arena;
    memcpy(utf8_final, u8, sizeof(uint8_t[u8_len]));
    utf8_final[u8_len] = '\0'; // Add a terminating NUL byte
    synthetic_graphemes[-grapheme_id - 1].utf8 = utf8_final;
    arena += sizeof(uint8_t[u8_len + 1]);

    // Sickos at the unicode consortium decreed that you can have grapheme clusters
    // that begin with *prefix* modifiers, so we gotta check for that case:
    synthetic_graphemes[-grapheme_id - 1].main_codepoint = length_prefixed[1];
    for (ucs4_t i = 0; i < utf32_len; i++) {
#if _LIBUNISTRING_VERSION >= 0x010200
        // libuinstring version 1.2.0 introduced uc_is_property_prepended_concatenation_mark()
        // It's not critical, but it's technically more correct to have this check:
        if (unlikely(uc_is_property_prepended_concatenation_mark(length_prefixed[1 + i]))) continue;
#endif
        synthetic_graphemes[-grapheme_id - 1].main_codepoint = length_prefixed[1 + i];
        break;
    }

    // Cleanup from unicode API:
    if (u8 != u8_buf) free(u8);

    Table$set(&grapheme_ids_by_codepoints, &codepoint_copy, &grapheme_id, &GraphemeIDLookupTableInfo);

    last_grapheme = grapheme_id;
    return grapheme_id;
}
#ifdef __GNUC__
#pragma GCC diagnostic pop
#endif

public
int Text$print(FILE *stream, Text_t t) {
    if (t.length == 0) return 0;

    switch (t.tag) {
    case TEXT_ASCII: return fwrite(t.ascii, sizeof(char), (size_t)t.length, stream);
    case TEXT_GRAPHEMES: {
        const int32_t *graphemes = t.graphemes;
        int written = 0;
        for (int64_t i = 0; i < (int64_t)t.length; i++) {
            int32_t grapheme = graphemes[i];
            if (grapheme >= 0) {
                uint8_t buf[8];
                size_t len = sizeof(buf);
                uint8_t *u8 = u32_to_u8((ucs4_t *)&grapheme, 1, buf, &len);
                if (u8 == NULL) fail("Invalid grapheme encountered: ", grapheme);
                written += (int)fwrite(u8, sizeof(char), len, stream);
                if (u8 != buf) free(u8);
            } else {
                const uint8_t *u8 = GRAPHEME_UTF8(grapheme);
                assert(u8);
                written += (int)fwrite(u8, sizeof(uint8_t), strlen((char *)u8), stream);
            }
        }
        return written;
    }
    case TEXT_BLOB: {
        int written = 0;
        for (int64_t i = 0; i < (int64_t)t.length; i++) {
            int32_t grapheme = t.blob.map[t.blob.bytes[i]];
            if (grapheme >= 0) {
                uint8_t buf[8];
                size_t len = sizeof(buf);
                uint8_t *u8 = u32_to_u8((ucs4_t *)&grapheme, 1, buf, &len);
                if (u8 == NULL) fail("Invalid grapheme encountered: ", grapheme);
                written += (int)fwrite(u8, sizeof(char), len, stream);
                if (u8 != buf) free(u8);
            } else {
                const uint8_t *u8 = GRAPHEME_UTF8(grapheme);
                assert(u8);
                written += (int)fwrite(u8, sizeof(uint8_t), strlen((char *)u8), stream);
            }
        }
        return written;
    }
    case TEXT_CONCAT: {
        int written = Text$print(stream, *t.left);
        written += Text$print(stream, *t.right);
        return written;
    }
    default: return 0;
    }
}

static const uint64_t min_len_for_depth[MAX_TEXT_DEPTH] = {
    // Fibonacci numbers (skipping first two)
    1,         2,         3,         5,          8,          13,         21,         34,         55,        89,
    144,       233,       377,       610,        987,        1597,       2584,       4181,       6765,      10946,
    17711,     28657,     46368,     75025,      121393,     196418,     317811,     514229,     832040,    1346269,
    2178309,   3524578,   5702887,   9227465,    14930352,   24157817,   39088169,   63245986,   102334155, 165580141,
    267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049,
};

#define IS_BALANCED_TEXT(t) ((t).length >= min_len_for_depth[(t).depth])

static void insert_balanced_recursive(Text_t balanced_texts[MAX_TEXT_DEPTH], Text_t text) {
    if (text.tag == TEXT_CONCAT && (!IS_BALANCED_TEXT(text) || text.depth >= MAX_TEXT_DEPTH)) {
        insert_balanced_recursive(balanced_texts, *text.left);
        insert_balanced_recursive(balanced_texts, *text.right);
        return;
    }

    int i = 0;
    Text_t accumulator = EMPTY_TEXT;
    for (; text.length > min_len_for_depth[i + 1]; i++) {
        if (balanced_texts[i].length) {
            accumulator = simple_concatenation(balanced_texts[i], accumulator);
            balanced_texts[i] = EMPTY_TEXT;
        }
    }

    accumulator = simple_concatenation(accumulator, text);

    while (accumulator.length >= min_len_for_depth[i]) {
        if (balanced_texts[i].length) {
            accumulator = simple_concatenation(balanced_texts[i], accumulator);
            balanced_texts[i] = EMPTY_TEXT;
        }
        i++;
    }
    i--;
    balanced_texts[i] = accumulator;
}

static Text_t rebalanced(Text_t a, Text_t b) {
    Text_t balanced_texts[MAX_TEXT_DEPTH];
    memset(balanced_texts, 0, sizeof(balanced_texts));
    insert_balanced_recursive(balanced_texts, a);
    insert_balanced_recursive(balanced_texts, b);

    Text_t ret = EMPTY_TEXT;
    for (int64_t i = 0; ret.length < a.length + b.length; i++) {
        if (balanced_texts[i].length) ret = simple_concatenation(balanced_texts[i], ret);
    }
    return ret;
}

Text_t simple_concatenation(Text_t a, Text_t b) {
    if (a.length == 0) return b;
    if (b.length == 0) return a;

    uint16_t new_depth = 1 + MAX(a.depth, b.depth);
    // Rebalance only if depth exceeds the maximum allowed. We don't require
    // every concatenation to yield a balanced text, since many concatenations
    // are ephemeral (e.g. doing a loop repeatedly concatenating without using
    // the intermediary values).
    if (new_depth >= MAX_TEXT_DEPTH) return rebalanced(a, b);

    Text_t *children = GC_MALLOC(sizeof(Text_t[2]));
    children[0] = a;
    children[1] = b;
    return (Text_t){
        .tag = TEXT_CONCAT,
        .length = a.length + b.length,
        .depth = new_depth,
        .left = &children[0],
        .right = &children[1],
    };
}

static Text_t concat2_assuming_safe(Text_t a, Text_t b) {
    if (a.length == 0) return b;
    if (b.length == 0) return a;

    if (a.tag == TEXT_ASCII && b.tag == TEXT_ASCII && (size_t)(a.length + b.length) <= SHORT_ASCII_LENGTH) {
        struct Text_s ret = {
            .tag = TEXT_ASCII,
            .length = a.length + b.length,
        };
        ret.ascii = GC_MALLOC_ATOMIC(sizeof(char[ret.length]));
        memcpy((char *)ret.ascii, a.ascii, sizeof(char[a.length]));
        memcpy((char *)&ret.ascii[a.length], b.ascii, sizeof(char[b.length]));
        return ret;
    } else if (a.tag == TEXT_GRAPHEMES && b.tag == TEXT_GRAPHEMES
               && (size_t)(a.length + b.length) <= SHORT_GRAPHEMES_LENGTH) {
        struct Text_s ret = {
            .tag = TEXT_GRAPHEMES,
            .length = a.length + b.length,
        };
        ret.graphemes = GC_MALLOC_ATOMIC(sizeof(int32_t[ret.length]));
        memcpy((int32_t *)ret.graphemes, a.graphemes, sizeof(int32_t[a.length]));
        memcpy((int32_t *)&ret.graphemes[a.length], b.graphemes, sizeof(int32_t[b.length]));
        return ret;
    } else if (a.tag != TEXT_CONCAT && b.tag != TEXT_CONCAT
               && (size_t)(a.length + b.length) <= SHORT_GRAPHEMES_LENGTH) {
        // Turn a small bit of ASCII into graphemes if it helps make things smaller
        // Text structs come with an extra 8 bytes, so allocate enough to hold the text
        struct Text_s ret = {
            .tag = TEXT_GRAPHEMES,
            .length = a.length + b.length,
        };
        ret.graphemes = GC_MALLOC_ATOMIC(sizeof(int32_t[ret.length]));
        int32_t *dest = (int32_t *)ret.graphemes;
        if (a.tag == TEXT_GRAPHEMES) {
            memcpy(dest, a.graphemes, sizeof(int32_t[a.length]));
            dest += a.length;
        } else if (a.tag == TEXT_ASCII) {
            for (int64_t i = 0; i < (int64_t)a.length; i++)
                *(dest++) = (int32_t)a.ascii[i];
        } else if (a.tag == TEXT_BLOB) {
            for (int64_t i = 0; i < (int64_t)a.length; i++)
                *(dest++) = a.blob.map[a.blob.bytes[i]];
        } else {
            errx(1, "Unreachable");
        }
        if (b.tag == TEXT_GRAPHEMES) {
            memcpy(dest, b.graphemes, sizeof(int32_t[b.length]));
        } else if (b.tag == TEXT_ASCII) {
            for (int64_t i = 0; i < (int64_t)b.length; i++)
                *(dest++) = (int32_t)b.ascii[i];
        } else if (b.tag == TEXT_BLOB) {
            for (int64_t i = 0; i < (int64_t)b.length; i++)
                *(dest++) = b.blob.map[b.blob.bytes[i]];
        } else {
            errx(1, "Unreachable");
        }
        return ret;
    }

    if (a.tag == TEXT_CONCAT && b.tag != TEXT_CONCAT && a.right->tag != TEXT_CONCAT)
        return concat2_assuming_safe(*a.left, concat2_assuming_safe(*a.right, b));

    return simple_concatenation(a, b);
}

static Text_t concat2(Text_t a, Text_t b) {
    if (a.length == 0) return b;
    if (b.length == 0) return a;

    int32_t last_a = Text$get_grapheme(a, a.length - 1);
    int32_t first_b = Text$get_grapheme(b, 0);

    // Magic number, we know that no codepoints below here trigger instability:
    static const int32_t LOWEST_CODEPOINT_TO_CHECK = 0x300; // COMBINING GRAVE ACCENT
    if (last_a >= 0 && last_a < LOWEST_CODEPOINT_TO_CHECK && first_b >= 0 && first_b < LOWEST_CODEPOINT_TO_CHECK)
        return concat2_assuming_safe(a, b);

    size_t len = (last_a >= 0) ? 1 : NUM_GRAPHEME_CODEPOINTS(last_a);
    len += (first_b >= 0) ? 1 : NUM_GRAPHEME_CODEPOINTS(first_b);

    ucs4_t codepoints[len];
    ucs4_t *dest = codepoints;
    if (last_a < 0) {
        memcpy(dest, GRAPHEME_CODEPOINTS(last_a), sizeof(ucs4_t[NUM_GRAPHEME_CODEPOINTS(last_a)]));
        dest += NUM_GRAPHEME_CODEPOINTS(last_a);
    } else {
        *(dest++) = (ucs4_t)last_a;
    }

    if (first_b < 0) {
        memcpy(dest, GRAPHEME_CODEPOINTS(first_b), sizeof(ucs4_t[NUM_GRAPHEME_CODEPOINTS(first_b)]));
    } else {
        *dest = (ucs4_t)first_b;
    }

    // Do a normalization run for these two codepoints and see if it looks different.
    // Normalization should not exceed 3x in the input length (but if it does, it will be
    // handled gracefully)
    ucs4_t norm_buf[3 * len];
    size_t norm_length = sizeof(norm_buf) / sizeof(norm_buf[0]);
    ucs4_t *normalized = u32_normalize(UNINORM_NFC, codepoints, len, norm_buf, &norm_length);
    bool stable = (norm_length == len && memcmp(codepoints, normalized, sizeof(codepoints)) == 0);

    if (stable) {
        const void *second_grapheme = u32_grapheme_next(normalized, &normalized[norm_length]);
        if (second_grapheme == &normalized[norm_length]) stable = false;
    }

    if likely (stable) {
        if (normalized != norm_buf) free(normalized);
        return concat2_assuming_safe(a, b);
    }

    OptionalText_t glue =
        Text$from_utf32((List_t){.data = normalized, .length = (uint64_t)norm_length, .stride = sizeof(ucs4_t)});

    if (normalized != norm_buf) free(normalized);

    if (a.length == 1 && b.length == 1) return glue;
    else if (a.length == 1) return concat2_assuming_safe(glue, Text$slice(b, I(2), I(b.length)));
    else if (b.length == 1) return concat2_assuming_safe(Text$slice(a, I(1), I(a.length - 1)), glue);
    else
        return concat2_assuming_safe(concat2_assuming_safe(Text$slice(a, I(1), I(a.length - 1)), glue),
                                     Text$slice(b, I(2), I(b.length)));
}

public
Text_t Text$_concat(int n, Text_t items[n]) {
    if (n == 0) return EMPTY_TEXT;

    Text_t ret = items[0];
    for (int i = 1; i < n; i++) {
        if (items[i].length > 0) ret = concat2(ret, items[i]);
    }
    return ret;
}

public
Text_t Text$repeat(Text_t text, Int_t count) {
    if (text.length == 0 || Int$is_negative(count)) return EMPTY_TEXT;

    Int_t result_len = Int$times(count, I(text.length));
    if (Int$compare_value(result_len, I(1l << 40)) > 0) fail("Text repeating would produce too big of an result!");

    int64_t count64 = Int64$from_int(count, false);
    Text_t ret = text;
    for (int64_t c = 1; c < count64; c++)
        ret = concat2(ret, text);
    return ret;
}

public
Int_t Text$width(Text_t text, Text_t language) {
    int width = u8_strwidth((const uint8_t *)Text$as_c_string(text), Text$as_c_string(language));
    return Int$from_int32(width);
}

static Text_t Text$repeat_to_width(Text_t to_repeat, int64_t target_width, Text_t language) {
    if (target_width <= 0) return EMPTY_TEXT;

    const char *lang_str = Text$as_c_string(language);
    int64_t width = (int64_t)u8_strwidth((const uint8_t *)Text$as_c_string(to_repeat), lang_str);
    Text_t repeated = EMPTY_TEXT;
    int64_t repeated_width = 0;
    while (repeated_width + width <= target_width) {
        repeated = concat2(repeated, to_repeat);
        repeated_width += width;
    }

    if (repeated_width < target_width) {
        for (int64_t i = 0; repeated_width < target_width && i < (int64_t)to_repeat.length; i++) {
            Text_t c = Text$slice(to_repeat, I_small(i + 1), I_small(i + 1));
            int64_t w = (int64_t)u8_strwidth((const uint8_t *)Text$as_c_string(c), lang_str);
            if (repeated_width + w > target_width) {
                repeated = concat2(repeated, Text$repeat(Text(" "), I(target_width - repeated_width)));
                break;
            }
            repeated = concat2(repeated, c);
            repeated_width += w;
        }
    }

    return repeated;
}

public
Text_t Text$left_pad(Text_t text, Int_t width, Text_t padding, Text_t language) {
    if (padding.length == 0) fail("Cannot pad with an empty text!");

    int64_t needed = Int64$from_int(width, false) - Int64$from_int(Text$width(text, language), false);
    return concat2(Text$repeat_to_width(padding, needed, language), text);
}

public
Text_t Text$right_pad(Text_t text, Int_t width, Text_t padding, Text_t language) {
    if (padding.length == 0) fail("Cannot pad with an empty text!");

    int64_t needed = Int64$from_int(width, false) - Int64$from_int(Text$width(text, language), false);
    return concat2(text, Text$repeat_to_width(padding, needed, language));
}

public
Text_t Text$middle_pad(Text_t text, Int_t width, Text_t padding, Text_t language) {
    if (padding.length == 0) fail("Cannot pad with an empty text!");

    int64_t needed = Int64$from_int(width, false) - Int64$from_int(Text$width(text, language), false);
    return Text$concat(Text$repeat_to_width(padding, needed / 2, language), text,
                       Text$repeat_to_width(padding, (needed + 1) / 2, language));
}

public
Text_t Text$slice(Text_t text, Int_t first_int, Int_t last_int) {
    int64_t first = Int64$from_int(first_int, false);
    int64_t last = Int64$from_int(last_int, false);
    if (first == 0) fail("Invalid index: 0");
    if (last == 0) return EMPTY_TEXT;

    if (first < 0) first = (int64_t)text.length + first + 1;
    if (last < 0) last = (int64_t)text.length + last + 1;

    if (last > (int64_t)text.length) last = (int64_t)text.length;

    if (first > (int64_t)text.length || last < first) return EMPTY_TEXT;

    if (first == 1 && last == (int64_t)text.length) return text;

    while (text.tag == TEXT_CONCAT) {
        if (last < (int64_t)text.left->length) {
            text = *text.left;
        } else if (first > (int64_t)text.left->length) {
            first -= (int64_t)text.left->length;
            last -= (int64_t)text.left->length;
            text = *text.right;
        } else {
            return concat2_assuming_safe(Text$slice(*text.left, I(first), I(text.length)),
                                         Text$slice(*text.right, I(1), I(last - text.left->length)));
        }
    }

    switch (text.tag) {
    case TEXT_ASCII: {
        return (Text_t){
            .tag = TEXT_ASCII,
            .length = last - first + 1,
            .ascii = text.ascii + (first - 1),
        };
    }
    case TEXT_GRAPHEMES: {
        return (Text_t){
            .tag = TEXT_GRAPHEMES,
            .length = last - first + 1,
            .graphemes = text.graphemes + (first - 1),
        };
    }
    case TEXT_BLOB: {
        Text_t ret = (Text_t){
            .tag = TEXT_BLOB,
            .length = last - first + 1,
            .blob.map = text.blob.map,
            .blob.bytes = text.blob.bytes + (first - 1),
        };
        return ret;
    }
    default: errx(1, "Invalid tag");
    }
    return EMPTY_TEXT;
}

public
Text_t Text$from(Text_t text, Int_t first) { return Text$slice(text, first, I_small(-1)); }

public
Text_t Text$to(Text_t text, Int_t last) { return Text$slice(text, I_small(1), last); }

public
Text_t Text$reversed(Text_t text) {
    switch (text.tag) {
    case TEXT_ASCII: {
        struct Text_s ret = {
            .tag = TEXT_ASCII,
            .length = text.length,
        };
        ret.ascii = GC_MALLOC_ATOMIC(sizeof(char[ret.length]));
        for (int64_t i = 0; i < (int64_t)text.length; i++)
            ((char *)ret.ascii)[text.length - 1 - i] = text.ascii[i];
        return ret;
    }
    case TEXT_GRAPHEMES: {
        struct Text_s ret = {
            .tag = TEXT_GRAPHEMES,
            .length = text.length,
        };
        ret.graphemes = GC_MALLOC_ATOMIC(sizeof(int32_t[ret.length]));
        for (int64_t i = 0; i < (int64_t)text.length; i++)
            ((int32_t *)ret.graphemes)[text.length - 1 - i] = text.graphemes[i];
        return ret;
    }
    case TEXT_BLOB: {
        struct Text_s ret = {
            .tag = TEXT_BLOB,
            .length = text.length,
            .blob.map = text.blob.map,
        };
        ret.blob.bytes = GC_MALLOC_ATOMIC(sizeof(uint8_t[ret.length]));
        for (int64_t i = 0; i < (int64_t)text.length; i++)
            ((uint8_t *)ret.blob.bytes)[text.length - 1 - i] = text.graphemes[i];
        return ret;
    }
    case TEXT_CONCAT: {
        return concat2_assuming_safe(Text$reversed(*text.right), Text$reversed(*text.left));
    }
    default: errx(1, "Invalid tag");
    }
    return EMPTY_TEXT;
}

public
PUREFUNC OptionalText_t Text$cluster(Text_t text, Int_t index) {
    Text_t slice = Text$slice(text, index, index);
    return slice.length <= 0 ? NONE_TEXT : slice;
}

static Text_t Text$from_components(List_t graphemes, Table_t unique_clusters) {
    if (graphemes.length == 0) return EMPTY_TEXT;
    size_t blob_size = (sizeof(int32_t[unique_clusters.entries.length]) + sizeof(uint8_t[graphemes.length]));
    // If blob optimization will save at least 200 bytes:
    if (unique_clusters.entries.length <= 256 && blob_size + 200 < sizeof(int32_t[graphemes.length])) {
        Text_t ret = {
            .tag = TEXT_BLOB,
            .length = graphemes.length,
            .depth = 0,
        };
        void *blob = GC_MALLOC_ATOMIC(blob_size);
        int32_t *map = blob;
        uint8_t *bytes = blob + sizeof(int32_t[unique_clusters.entries.length]);
        for (int64_t i = 0; i < (int64_t)unique_clusters.entries.length; i++) {
            struct {
                int32_t g;
                uint8_t b;
            } *entry = unique_clusters.entries.data + i * unique_clusters.entries.stride;
            map[entry->b] = entry->g;
        }
        for (int64_t i = 0; i < (int64_t)graphemes.length; i++) {
            int32_t g = *(int32_t *)(graphemes.data + i * graphemes.stride);
            uint8_t *byte = Table$get(unique_clusters, &g, Table$info(&Int32$info, &Byte$info));
            assert(byte);
            bytes[i] = *byte;
        }
        ret.blob.map = map;
        ret.blob.bytes = bytes;
        return ret;
    } else {
        return (Text_t){
            .tag = TEXT_GRAPHEMES,
            .length = graphemes.length,
            .graphemes = graphemes.data,
        };
    }
}

public
OptionalText_t Text$from_strn(const char *str, size_t len) {
    int64_t ascii_span = 0;
    for (size_t i = 0; i < len && isascii(str[i]); i++) {
        ascii_span++;
        if (str[i] == 0) return NONE_TEXT;
    }

    if (ascii_span == (int64_t)len) { // All ASCII
        char *copy = GC_MALLOC_ATOMIC(len);
        memcpy(copy, str, len);
        return (Text_t){
            .tag = TEXT_ASCII,
            .length = ascii_span,
            .ascii = copy,
        };
    }
    if (u8_check((uint8_t *)str, len) != NULL) return NONE_TEXT;

    List_t graphemes = EMPTY_LIST;
    Table_t unique_clusters = EMPTY_TABLE;
    const uint8_t *pos = (const uint8_t *)str;
    const uint8_t *end = (const uint8_t *)&str[len];
    // Iterate over grapheme clusters
    for (const uint8_t *next; (next = u8_grapheme_next(pos, end)); pos = next) {
        uint32_t buf[256];
        size_t u32_len = sizeof(buf) / sizeof(buf[0]);
        uint32_t *u32s = u8_to_u32(pos, (size_t)(next - pos), buf, &u32_len);
        if (u32s == NULL) return NONE_TEXT;

        uint32_t buf2[256];
        size_t u32_normlen = sizeof(buf2) / sizeof(buf2[0]);
        uint32_t *u32s_normalized = u32_normalize(UNINORM_NFC, u32s, u32_len, buf2, &u32_normlen);
        if (u32s_normalized == NULL) return NONE_TEXT;

        int32_t g = get_synthetic_grapheme(u32s_normalized, (int64_t)u32_normlen);
        if (g == 0) return NONE_TEXT;
        List$insert(&graphemes, &g, I(0), sizeof(int32_t));
        Table$get_or_setdefault(&unique_clusters, int32_t, uint8_t, g, (uint8_t)unique_clusters.entries.length,
                                Table$info(&Int32$info, &Byte$info));

        if (u32s != buf) free(u32s);
        if (u32s_normalized != buf2) free(u32s_normalized);

        if (unique_clusters.entries.length >= 256) {
            return concat2_assuming_safe(Text$from_components(graphemes, unique_clusters),
                                         Text$from_strn((const char *)next, (size_t)(end - next)));
        }
    }

    return Text$from_components(graphemes, unique_clusters);
}

public
OptionalText_t Text$from_str(const char *str) { return str ? Text$from_strn(str, strlen(str)) : Text(""); }

static void u8_buf_append(Text_t text, Byte_t **buf, int64_t *capacity, int64_t *i) {
    switch (text.tag) {
    case TEXT_ASCII: {
        if (*i + (int64_t)text.length > (int64_t)*capacity) {
            *capacity = *i + (int64_t)text.length + 1;
            *buf = GC_REALLOC(*buf, sizeof(Byte_t[*capacity]));
        }

        const char *bytes = text.ascii;
        memcpy(*buf + *i, bytes, (size_t)text.length);
        *i += text.length;
        break;
    }
    case TEXT_GRAPHEMES: {
        const int32_t *graphemes = text.graphemes;
        for (int64_t g = 0; g < (int64_t)text.length; g++) {
            if (graphemes[g] >= 0) {
                uint8_t u8_buf[64];
                size_t u8_len = sizeof(u8_buf);
                uint8_t *u8 = u32_to_u8((ucs4_t *)&graphemes[g], 1, u8_buf, &u8_len);
                if (u8 == NULL) fail("Invalid grapheme encountered: ", graphemes[g]);

                if (*i + (int64_t)u8_len > (int64_t)*capacity) {
                    *capacity = *i + (int64_t)u8_len + 1;
                    *buf = GC_REALLOC(*buf, sizeof(Byte_t[*capacity]));
                }

                memcpy(*buf + *i, u8, u8_len);
                *i += (int64_t)u8_len;
                if (u8 != u8_buf) free(u8);
            } else {
                const uint8_t *u8 = GRAPHEME_UTF8(graphemes[g]);
                size_t u8_len = u8_strlen(u8);
                if (*i + (int64_t)u8_len > (int64_t)*capacity) {
                    *capacity = *i + (int64_t)u8_len + 1;
                    *buf = GC_REALLOC(*buf, sizeof(Byte_t[*capacity]));
                }

                memcpy(*buf + *i, u8, u8_len);
                *i += (int64_t)u8_len;
            }
        }
        break;
    }
    case TEXT_BLOB: {
        for (int64_t g = 0; g < (int64_t)text.length; g++) {
            int32_t grapheme = text.blob.map[text.blob.bytes[g]];
            if (grapheme >= 0) {
                uint8_t u8_buf[64];
                size_t u8_len = sizeof(u8_buf);
                uint8_t *u8 = u32_to_u8((ucs4_t *)&grapheme, 1, u8_buf, &u8_len);
                if (u8 == NULL) fail("Invalid grapheme encountered: ", grapheme);

                if (*i + (int64_t)u8_len > (int64_t)*capacity) {
                    *capacity = *i + (int64_t)u8_len + 1;
                    *buf = GC_REALLOC(*buf, sizeof(Byte_t[*capacity]));
                }

                memcpy(*buf + *i, u8, u8_len);
                *i += (int64_t)u8_len;
                if (u8 != u8_buf) free(u8);
            } else {
                const uint8_t *u8 = GRAPHEME_UTF8(grapheme);
                size_t u8_len = u8_strlen(u8);
                if (*i + (int64_t)u8_len > (int64_t)*capacity) {
                    *capacity = *i + (int64_t)u8_len + 1;
                    *buf = GC_REALLOC(*buf, sizeof(Byte_t[*capacity]));
                }

                memcpy(*buf + *i, u8, u8_len);
                *i += (int64_t)u8_len;
            }
        }
        break;
    }
    case TEXT_CONCAT: {
        u8_buf_append(*text.left, buf, capacity, i);
        u8_buf_append(*text.right, buf, capacity, i);
        break;
    }
    default: break;
    }
}

public
char *Text$as_c_string(Text_t text) {
    int64_t capacity = text.length + 1;
    char *buf = GC_MALLOC_ATOMIC((size_t)capacity);
    int64_t i = 0;
    u8_buf_append(text, (Byte_t **)&buf, &capacity, &i);

    if (i + 1 > (int64_t)capacity) {
        capacity = i + 1;
        buf = GC_REALLOC(buf, (size_t)capacity);
    }
    buf[i] = '\0';
    return buf;
}

PUREFUNC public uint64_t Text$hash(const void *obj, const TypeInfo_t *info) {
    (void)info;
    Text_t text = *(Text_t *)obj;
    siphash sh;
    siphashinit(&sh, sizeof(int32_t[text.length]));

    union {
        int32_t chunks[2];
        uint64_t whole;
    } tmp;
    switch (text.tag) {
    case TEXT_ASCII: {
        const char *bytes = text.ascii;
        for (int64_t i = 0; i + 1 < (int64_t)text.length; i += 2) {
            tmp.chunks[0] = (int32_t)bytes[i];
            tmp.chunks[1] = (int32_t)bytes[i + 1];
            siphashadd64bits(&sh, tmp.whole);
        }
        int32_t last = text.length & 0x1 ? (int32_t)bytes[text.length - 1] : 0; // Odd number of graphemes
        return siphashfinish_last_part(&sh, (uint64_t)last);
    }
    case TEXT_GRAPHEMES: {
        const int32_t *graphemes = text.graphemes;
        for (int64_t i = 0; i + 1 < (int64_t)text.length; i += 2) {
            tmp.chunks[0] = graphemes[i];
            tmp.chunks[1] = graphemes[i + 1];
            siphashadd64bits(&sh, tmp.whole);
        }
        int32_t last = text.length & 0x1 ? graphemes[text.length - 1] : 0; // Odd number of graphemes
        return siphashfinish_last_part(&sh, (uint64_t)last);
    }
    case TEXT_BLOB: {
        for (int64_t i = 0; i + 1 < (int64_t)text.length; i += 2) {
            tmp.chunks[0] = text.blob.map[text.blob.bytes[i]];
            tmp.chunks[1] = text.blob.map[text.blob.bytes[i + 1]];
            siphashadd64bits(&sh, tmp.whole);
        }
        int32_t last =
            text.length & 0x1 ? text.blob.map[text.blob.bytes[text.length - 1]] : 0; // Odd number of graphemes
        return siphashfinish_last_part(&sh, (uint64_t)last);
    }
    case TEXT_CONCAT: {
        TextIter_t state = NEW_TEXT_ITER_STATE(text);
        for (int64_t i = 0; i + 1 < (int64_t)text.length; i += 2) {
            tmp.chunks[0] = Text$get_grapheme_fast(&state, i);
            tmp.chunks[1] = Text$get_grapheme_fast(&state, i + 1);
            siphashadd64bits(&sh, tmp.whole);
        }

        int32_t last = (text.length & 0x1) ? Text$get_grapheme_fast(&state, text.length - 1) : 0;
        return siphashfinish_last_part(&sh, (uint64_t)last);
    }
    default: errx(1, "Invalid text");
    }
    return 0;
}

public
int32_t Text$get_grapheme_fast(TextIter_t *state, int64_t index) {
    if (index < 0) return 0;
    if (index >= (int64_t)state->stack[0].text.length) return 0;

    assert(state->stack[0].text.depth <= MAX_TEXT_DEPTH);

    // Go up the stack as needed:
    while (index < state->stack[state->stack_index].offset
           || index
                  >= state->stack[state->stack_index].offset + (int64_t)state->stack[state->stack_index].text.length) {
        state->stack_index -= 1;
        assert(state->stack_index >= 0);
    }

    assert(state->stack_index >= 0 && state->stack_index <= MAX_TEXT_DEPTH);

    // Go down the stack as needed:
    while (state->stack[state->stack_index].text.tag == TEXT_CONCAT) {
        Text_t text = state->stack[state->stack_index].text;
        int64_t offset = state->stack[state->stack_index].offset;
        assert(state->stack_index <= MAX_TEXT_DEPTH);
        assert(index >= offset);
        assert(index < offset + (int64_t)text.length);

        state->stack_index += 1;
        if (index < offset + (int64_t)text.left->length) {
            state->stack[state->stack_index].text = *text.left;
            state->stack[state->stack_index].offset = offset;
        } else {
            state->stack[state->stack_index].text = *text.right;
            state->stack[state->stack_index].offset = offset + text.left->length;
        }
        assert(state->stack_index >= 0 && state->stack_index <= MAX_TEXT_DEPTH);
    }

    Text_t text = state->stack[state->stack_index].text;
    int64_t offset = state->stack[state->stack_index].offset;

    if (index < offset || index >= offset + (int64_t)text.length) {
        return 0;
    }

    switch (text.tag) {
    case TEXT_ASCII: return (int32_t)text.ascii[index - offset];
    case TEXT_GRAPHEMES: return text.graphemes[index - offset];
    case TEXT_BLOB: return text.blob.map[text.blob.bytes[index - offset]];
    default: errx(1, "Invalid text");
    }
    return 0;
}

public
uint32_t Text$get_main_grapheme_fast(TextIter_t *state, int64_t index) {
    int32_t g = Text$get_grapheme_fast(state, index);
    return (g) >= 0 ? (ucs4_t)(g) : synthetic_graphemes[-(g)-1].main_codepoint;
}

PUREFUNC public int32_t Text$compare(const void *va, const void *vb, const TypeInfo_t *info) {
    (void)info;
    if (va == vb) return 0;
    const Text_t a = *(const Text_t *)va;
    const Text_t b = *(const Text_t *)vb;

    // TODO: make this smarter and more efficient
    int64_t len = MAX(a.length, b.length);
    TextIter_t a_state = NEW_TEXT_ITER_STATE(a), b_state = NEW_TEXT_ITER_STATE(b);
    for (int64_t i = 0; i < len; i++) {
        int32_t ai = Text$get_grapheme_fast(&a_state, i);
        int32_t bi = Text$get_grapheme_fast(&b_state, i);
        if (ai == bi) continue;
        int32_t cmp;
        if (ai > 0 && bi > 0) {
            cmp = u32_cmp((ucs4_t *)&ai, (ucs4_t *)&bi, 1);
        } else if (ai > 0) {
            cmp = u32_cmp2((ucs4_t *)&ai, 1, GRAPHEME_CODEPOINTS(bi), NUM_GRAPHEME_CODEPOINTS(bi));
        } else if (bi > 0) {
            cmp = u32_cmp2(GRAPHEME_CODEPOINTS(ai), NUM_GRAPHEME_CODEPOINTS(ai), (ucs4_t *)&bi, 1);
        } else {
            cmp = u32_cmp2(GRAPHEME_CODEPOINTS(ai), NUM_GRAPHEME_CODEPOINTS(ai), GRAPHEME_CODEPOINTS(bi),
                           NUM_GRAPHEME_CODEPOINTS(bi));
        }
        if (cmp != 0) return cmp;
    }
    return 0;
}

bool _matches(TextIter_t *text_state, TextIter_t *target_state, int64_t pos) {
    for (int64_t i = 0; i < (int64_t)target_state->stack[0].text.length; i++) {
        int32_t text_i = Text$get_grapheme_fast(text_state, pos + i);
        int32_t target_i = Text$get_grapheme_fast(target_state, i);
        if (text_i != target_i) return false;
    }
    return true;
}

PUREFUNC public bool Text$starts_with(Text_t text, Text_t prefix, Text_t *remainder) {
    if (text.length < prefix.length) return false;
    TextIter_t text_state = NEW_TEXT_ITER_STATE(text), prefix_state = NEW_TEXT_ITER_STATE(prefix);
    if (_matches(&text_state, &prefix_state, 0)) {
        if (remainder) *remainder = Text$from(text, Int$from_int64(prefix.length + 1));
        return true;
    } else {
        if (remainder) *remainder = text;
        return false;
    }
}

PUREFUNC public bool Text$ends_with(Text_t text, Text_t suffix, Text_t *remainder) {
    if (text.length < suffix.length) return false;
    TextIter_t text_state = NEW_TEXT_ITER_STATE(text), suffix_state = NEW_TEXT_ITER_STATE(suffix);
    if (_matches(&text_state, &suffix_state, text.length - suffix.length)) {
        if (remainder) *remainder = Text$to(text, Int$from_int64(text.length - suffix.length));
        return true;
    } else {
        if (remainder) *remainder = text;
        return false;
    }
}

public
Text_t Text$without_prefix(Text_t text, Text_t prefix) {
    return Text$starts_with(text, prefix, NULL) ? Text$slice(text, I(prefix.length + 1), I(text.length)) : text;
}

public
Text_t Text$without_suffix(Text_t text, Text_t suffix) {
    return Text$ends_with(text, suffix, NULL) ? Text$slice(text, I(1), I(text.length - suffix.length)) : text;
}

static bool _has_grapheme(TextIter_t *text, int32_t g) {
    for (int64_t t = 0; t < (int64_t)text->stack[0].text.length; t++) {
        if (g == Text$get_grapheme_fast(text, t)) {
            return true;
        }
    }
    return false;
}

public
OptionalInt_t Text$find(Text_t text, Text_t target, Int_t start) {
    if (text.length < target.length) return NONE_INT;
    if (target.length <= 0) return I(1);
    TextIter_t text_state = NEW_TEXT_ITER_STATE(text), target_state = NEW_TEXT_ITER_STATE(target);
    for (int64_t i = Int64$from_int(start, false) - 1; i < text.length - target.length + 1; i++) {
        if (_matches(&text_state, &target_state, i)) {
            return Int$from_int64(i + 1);
        }
    }
    return NONE_INT;
}

public
Text_t Text$trim(Text_t text, Text_t to_trim, bool left, bool right) {
    int64_t first = 0;
    TextIter_t text_state = NEW_TEXT_ITER_STATE(text), trim_state = NEW_TEXT_ITER_STATE(to_trim);
    if (left) {
        while (first < (int64_t)text.length && _has_grapheme(&trim_state, Text$get_grapheme_fast(&text_state, first))) {
            first += 1;
        }
    }
    int64_t last = text.length - 1;
    if (right) {
        while (last >= first && _has_grapheme(&trim_state, Text$get_grapheme_fast(&text_state, last))) {
            last -= 1;
        }
    }
    return (first != 0 || last != text.length - 1) ? Text$slice(text, I(first + 1), I(last + 1)) : text;
}

public
Text_t Text$translate(Text_t text, Table_t translations) {
    TextIter_t text_state = NEW_TEXT_ITER_STATE(text);
    Text_t result = EMPTY_TEXT;
    int64_t span_start = 0;
    List_t replacement_list = translations.entries;
    for (int64_t i = 0; i < (int64_t)text.length;) {
        for (int64_t r = 0; r < (int64_t)replacement_list.length; r++) {
            struct {
                Text_t target, replacement;
            } *entry = replacement_list.data + r * replacement_list.stride;
            if (entry->target.length <= 0) continue;
            TextIter_t target_state = NEW_TEXT_ITER_STATE(entry->target);
            if (_matches(&text_state, &target_state, i)) {
                if (i > span_start) result = concat2(result, Text$slice(text, I(span_start + 1), I(i)));

                result = concat2(result, entry->replacement);
                i += entry->target.length;
                span_start = i;
                goto found_match;
            }
        }
        i += 1;
    found_match:
        continue;
    }
    if (span_start < (int64_t)text.length)
        result = concat2(result, Text$slice(text, I(span_start + 1), I((int64_t)text.length)));
    return result;
}

public
Text_t Text$replace(Text_t text, Text_t target, Text_t replacement) {
    if (target.length <= 0) return text;
    TextIter_t text_state = NEW_TEXT_ITER_STATE(text), target_state = NEW_TEXT_ITER_STATE(target);
    Text_t result = EMPTY_TEXT;
    int64_t span_start = 0;
    for (int64_t i = 0; i < (int64_t)text.length;) {
        if (_matches(&text_state, &target_state, i)) {
            if (i > span_start) result = concat2(result, Text$slice(text, I(span_start + 1), I(i)));

            result = concat2(result, replacement);
            i += target.length;
            span_start = i;
        } else {
            i += 1;
        }
    }
    if (span_start < (int64_t)text.length)
        result = concat2(result, Text$slice(text, I(span_start + 1), I((int64_t)text.length)));
    return result;
}

public
PUREFUNC bool Text$has(Text_t text, Text_t target) {
    TextIter_t text_state = NEW_TEXT_ITER_STATE(text), target_state = NEW_TEXT_ITER_STATE(target);
    for (int64_t i = 0; i < (int64_t)text.length; i++) {
        if (_matches(&text_state, &target_state, i)) return true;
    }
    return false;
}

public
List_t Text$split(Text_t text, Text_t delimiters) {
    if (delimiters.length == 0) return Text$clusters(text);

    TextIter_t text_state = NEW_TEXT_ITER_STATE(text), delim_state = NEW_TEXT_ITER_STATE(delimiters);
    List_t splits = EMPTY_LIST;
    for (int64_t i = 0; i < (int64_t)text.length;) {
        int64_t span_len = 0;
        while (i + span_len < (int64_t)text.length && !_matches(&text_state, &delim_state, i + span_len)) {
            span_len += 1;
        }
        Text_t slice = Text$slice(text, I(i + 1), I(i + span_len));
        List$insert(&splits, &slice, I(0), sizeof(slice));
        i += span_len + delimiters.length;
        if (i == text.length) {
            Text_t empty = Text("");
            List$insert(&splits, &empty, I(0), sizeof(empty));
        }
    }
    return splits;
}

public
List_t Text$split_any(Text_t text, Text_t delimiters) {
    if (delimiters.length == 0) return List(text);

    TextIter_t text_state = NEW_TEXT_ITER_STATE(text), delim_state = NEW_TEXT_ITER_STATE(delimiters);
    List_t splits = EMPTY_LIST;
    for (int64_t i = 0; i < (int64_t)text.length;) {
        int64_t span_len = 0;
        while (i + span_len < (int64_t)text.length
               && !_has_grapheme(&delim_state, Text$get_grapheme_fast(&text_state, i + span_len))) {
            span_len += 1;
        }
        bool trailing_delim = i + span_len < (int64_t)text.length;
        Text_t slice = Text$slice(text, I(i + 1), I(i + span_len));
        List$insert(&splits, &slice, I(0), sizeof(slice));
        i += span_len + 1;
        while (i < (int64_t)text.length && _has_grapheme(&delim_state, Text$get_grapheme_fast(&text_state, i))) {
            i += 1;
        }
        if (i >= (int64_t)text.length && trailing_delim) {
            Text_t empty = Text("");
            List$insert(&splits, &empty, I(0), sizeof(empty));
        }
    }
    return splits;
}

typedef struct {
    TextIter_t state;
    int64_t i;
    Text_t delimiter;
} split_iter_state_t;

static OptionalText_t next_split(split_iter_state_t *state) {
    Text_t text = state->state.stack[0].text;
    if (state->i >= (int64_t)text.length) {
        if (state->delimiter.length > 0 && state->i == text.length) { // special case
            state->i = text.length + 1;
            return EMPTY_TEXT;
        }
        return NONE_TEXT;
    }

    if (state->delimiter.length == 0) { // special case
        state->i = text.length + 1;
        return text;
    }

    TextIter_t delim_state = NEW_TEXT_ITER_STATE(state->delimiter);
    int64_t i = state->i;
    int64_t span_len = 0;
    while (i + span_len < (int64_t)text.length && !_matches(&state->state, &delim_state, i + span_len)) {
        span_len += 1;
    }
    Text_t slice = Text$slice(text, I(i + 1), I(i + span_len));
    state->i = i + span_len + state->delimiter.length;
    return slice;
}

public
Closure_t Text$by_split(Text_t text, Text_t delimiter) {
    return (Closure_t){
        .fn = (void *)next_split,
        .userdata = new (split_iter_state_t, .state = NEW_TEXT_ITER_STATE(text), .i = 0, .delimiter = delimiter),
    };
}

static OptionalText_t next_split_any(split_iter_state_t *state) {
    Text_t text = state->state.stack[0].text;
    if (state->i >= (int64_t)text.length) {
        if (state->delimiter.length > 0 && state->i == text.length) { // special case
            state->i = text.length + 1;
            return EMPTY_TEXT;
        }
        return NONE_TEXT;
    }

    if (state->delimiter.length == 0) { // special case
        Text_t ret = Text$cluster(text, I(state->i + 1));
        state->i += 1;
        return ret;
    }

    TextIter_t delim_state = NEW_TEXT_ITER_STATE(state->delimiter);
    int64_t i = state->i;
    int64_t span_len = 0;
    while (i + span_len < (int64_t)text.length
           && !_has_grapheme(&delim_state, Text$get_grapheme_fast(&state->state, i + span_len))) {
        span_len += 1;
    }
    Text_t slice = Text$slice(text, I(i + 1), I(i + span_len));
    i += span_len + 1;
    while (i < (int64_t)text.length && _has_grapheme(&delim_state, Text$get_grapheme_fast(&state->state, i))) {
        i += 1;
    }
    state->i = i;
    return slice;
}

public
Closure_t Text$by_split_any(Text_t text, Text_t delimiters) {
    return (Closure_t){
        .fn = (void *)next_split_any,
        .userdata = new (split_iter_state_t, .state = NEW_TEXT_ITER_STATE(text), .i = 0, .delimiter = delimiters),
    };
}

PUREFUNC public bool Text$equal_values(Text_t a, Text_t b) {
    if (a.length != b.length) return false;
    int64_t len = a.length;
    TextIter_t a_state = NEW_TEXT_ITER_STATE(a), b_state = NEW_TEXT_ITER_STATE(b);
    // TODO: make this smarter and more efficient
    for (int64_t i = 0; i < len; i++) {
        int32_t ai = Text$get_grapheme_fast(&a_state, i);
        int32_t bi = Text$get_grapheme_fast(&b_state, i);
        if (ai != bi) return false;
    }
    return true;
}

PUREFUNC public bool Text$equal(const void *a, const void *b, const TypeInfo_t *info) {
    (void)info;
    if (a == b) return true;
    return Text$equal_values(*(Text_t *)a, *(Text_t *)b);
}

PUREFUNC public bool Text$equal_ignoring_case(Text_t a, Text_t b, Text_t language) {
    if (a.length != b.length) return false;
    int64_t len = a.length;
    TextIter_t a_state = NEW_TEXT_ITER_STATE(a), b_state = NEW_TEXT_ITER_STATE(b);
    const char *uc_language = Text$as_c_string(language);
    for (int64_t i = 0; i < len; i++) {
        int32_t ai = Text$get_grapheme_fast(&a_state, i);
        int32_t bi = Text$get_grapheme_fast(&b_state, i);
        if (ai != bi) {
            const ucs4_t *a_codepoints = ai >= 0 ? (ucs4_t *)&ai : GRAPHEME_CODEPOINTS(ai);
            int64_t a_len = ai >= 0 ? 1 : NUM_GRAPHEME_CODEPOINTS(ai);

            const ucs4_t *b_codepoints = bi >= 0 ? (ucs4_t *)&bi : GRAPHEME_CODEPOINTS(bi);
            int64_t b_len = bi >= 0 ? 1 : NUM_GRAPHEME_CODEPOINTS(bi);

            int cmp = 0;
            (void)u32_casecmp(a_codepoints, (size_t)a_len, b_codepoints, (size_t)b_len, uc_language, UNINORM_NFC, &cmp);
            if (cmp != 0) return false;
        }
    }
    return true;
}

public
Text_t Text$upper(Text_t text, Text_t language) {
    if (text.length == 0) return text;
    List_t codepoints = Text$utf32(text);
    if (codepoints.stride != sizeof(int32_t)) List$compact(&codepoints, sizeof(int32_t));
    const char *uc_language = Text$as_c_string(language);
    size_t out_len = 256;
    uint32_t buf[out_len];
    ucs4_t *upper = u32_toupper(codepoints.data, (size_t)codepoints.length, uc_language, UNINORM_NFC, buf, &out_len);
    OptionalText_t ret =
        Text$from_utf32((List_t){.data = upper, .length = (uint64_t)out_len, .stride = sizeof(int32_t)});
    if (upper != buf) free(upper);
    return ret;
}

public
Text_t Text$lower(Text_t text, Text_t language) {
    if (text.length == 0) return text;
    List_t codepoints = Text$utf32(text);
    if (codepoints.stride != sizeof(int32_t)) List$compact(&codepoints, sizeof(int32_t));
    const char *uc_language = Text$as_c_string(language);
    size_t out_len = 256;
    uint32_t buf[out_len];
    ucs4_t *lower = u32_tolower(codepoints.data, (size_t)codepoints.length, uc_language, UNINORM_NFC, buf, &out_len);
    OptionalText_t ret =
        Text$from_utf32((List_t){.data = lower, .length = (uint64_t)out_len, .stride = sizeof(int32_t)});
    if (lower != buf) free(lower);
    return ret;
}

public
Text_t Text$title(Text_t text, Text_t language) {
    if (text.length == 0) return text;
    List_t codepoints = Text$utf32(text);
    if (codepoints.stride != sizeof(int32_t)) List$compact(&codepoints, sizeof(int32_t));
    const char *uc_language = Text$as_c_string(language);
    size_t out_len = 256;
    uint32_t buf[out_len];
    ucs4_t *title = u32_totitle(codepoints.data, (size_t)codepoints.length, uc_language, UNINORM_NFC, buf, &out_len);
    OptionalText_t ret =
        Text$from_utf32((List_t){.data = title, .length = (uint64_t)out_len, .stride = sizeof(int32_t)});
    if (title != buf) free(title);
    return ret;
}

public
Text_t Text$escaped(Text_t text, bool colorize, Text_t extra_escapes) {
    Text_t ret = colorize ? Text("\x1b[35m") : EMPTY_TEXT;
#define flush_unquoted()                                                                                               \
    ({                                                                                                                 \
        if (unquoted_span > 0) {                                                                                       \
            ret = concat2_assuming_safe(ret, Text$slice(text, I(i - unquoted_span + 1), I(i)));                        \
            unquoted_span = 0;                                                                                         \
        }                                                                                                              \
    })
#define add_escaped(str)                                                                                               \
    ({                                                                                                                 \
        flush_unquoted();                                                                                              \
        if (colorize) ret = concat2_assuming_safe(ret, Text("\x1b[34;1m"));                                            \
        ret = concat2_assuming_safe(ret, Text("\\" str));                                                              \
        if (colorize) ret = concat2_assuming_safe(ret, Text("\x1b[0;35m"));                                            \
    })
    TextIter_t state = NEW_TEXT_ITER_STATE(text);
    int64_t unquoted_span = 0;
    int64_t i = 0;
    for (i = 0; i < (int64_t)text.length; i++) {
        int32_t g = Text$get_grapheme_fast(&state, i);
        switch (g) {
        case '\a': add_escaped("a"); break;
        case '\b': add_escaped("b"); break;
        case '\x1b': add_escaped("e"); break;
        case '\f': add_escaped("f"); break;
        case '\n': add_escaped("n"); break;
        case '\r': add_escaped("r"); break;
        case '\t': add_escaped("t"); break;
        case '\v': add_escaped("v"); break;
        case '\\': {
            add_escaped("\\");
            break;
        }
        case '$': {
            add_escaped("$");
            break;
        }
        case '\x00' ... '\x06':
        case '\x0E' ... '\x1A':
        case '\x1C' ... '\x1F':
        case '\x7F' ... '\x7F': {
            flush_unquoted();
            if (colorize) ret = concat2_assuming_safe(ret, Text("\x1b[34;1m"));
            ret = concat2_assuming_safe(ret, Text("\\x"));
            char tmp[3] = {
                (g / 16) > 9 ? 'a' + (g / 16) - 10 : '0' + (g / 16),
                (g & 15) > 9 ? 'a' + (g & 15) - 10 : '0' + (g & 15),
                '\0',
            };
            ret = concat2_assuming_safe(ret, Text$from_strn(tmp, 2));
            if (colorize) ret = concat2_assuming_safe(ret, Text("\x1b[0;35m"));
            break;
        }
        default: {
            TextIter_t esc_state = NEW_TEXT_ITER_STATE(extra_escapes);
            for (int64_t j = 0; j < (int64_t)extra_escapes.length; j++) {
                int32_t esc = Text$get_grapheme_fast(&esc_state, j);
                if (g == esc) {
                    flush_unquoted();
                    if (colorize) ret = concat2_assuming_safe(ret, Text("\x1b[34;1m"));
                    ret = concat2_assuming_safe(ret, Text("\\"));
                    if (colorize) ret = concat2_assuming_safe(ret, Text("\x1b[0;35m"));
                    break;
                }
            }
            unquoted_span += 1;
            break;
        }
        }
    }
    flush_unquoted();
#undef add_escaped
#undef flush_unquoted
    if (colorize) ret = concat2_assuming_safe(ret, Text("\x1b[m"));
    return ret;
}

public
Text_t Text$quoted(Text_t text, bool colorize, Text_t quotation_mark) {
    if (quotation_mark.length != 1) fail("Invalid quote text: ", quotation_mark, " (must have length == 1)");

    Text_t ret = Text$escaped(text, colorize, quotation_mark);
    if (!(Text$equal_values(quotation_mark, Text("\"")) || Text$equal_values(quotation_mark, Text("'"))
          || Text$equal_values(quotation_mark, Text("`"))))
        ret = Text$concat(Text("$"), quotation_mark, ret, quotation_mark);
    else ret = Text$concat(quotation_mark, ret, quotation_mark);
    return ret;
}

public
Text_t Text$as_text(const void *vtext, bool colorize, const TypeInfo_t *info) {
    (void)info;
    if (!vtext) return info && info->TextInfo.lang ? Text$from_str(info->TextInfo.lang) : Text("Text");

    Text_t text = *(Text_t *)vtext;
    // Figure out the best quotation mark to use:
    bool has_double_quote = false, has_backtick = false, has_single_quote = false, needs_escapes = false;
    TextIter_t state = NEW_TEXT_ITER_STATE(text);
    for (int64_t i = 0; i < (int64_t)text.length; i++) {
        int32_t g = Text$get_grapheme_fast(&state, i);
        if (g == '"') {
            has_double_quote = true;
        } else if (g == '`') {
            has_backtick = true;
        } else if (g == (g & 0x7F) && (g == '\'' || g == '\n' || g == '\r' || g == '\t' || !isprint((char)g))) {
            needs_escapes = true;
        }
    }

    Text_t quote;
    // If there's double quotes in the string, it would be nice to avoid
    // needing to escape them by using single quotes, but only if we don't have
    // single quotes or need to escape anything else (because single quotes
    // don't have interpolation):
    if (has_double_quote && !has_single_quote) quote = Text("'");
    // If there is a double quote, but no backtick, we can save a bit of
    // escaping by using backtick instead of double quote:
    else if (has_double_quote && has_single_quote && !has_backtick && !needs_escapes) quote = Text("`");
    // Otherwise fall back to double quotes as the default quoting style:
    else quote = Text("\"");

    Text_t as_text = Text$quoted(text, colorize, quote);
    if (info && info->TextInfo.lang && info != &Text$info)
        as_text = Text$concat(colorize ? Text("\x1b[1m$") : Text("$"), Text$from_str(info->TextInfo.lang),
                              colorize ? Text("\x1b[0m") : Text(""), as_text);
    return as_text;
}

public
Text_t Text$join(Text_t glue, List_t pieces) {
    if (pieces.length == 0) return EMPTY_TEXT;

    Text_t result = *(Text_t *)pieces.data;
    for (int64_t i = 1; i < (int64_t)pieces.length; i++) {
        result = Text$concat(result, glue, *(Text_t *)(pieces.data + i * pieces.stride));
    }
    return result;
}

public
List_t Text$clusters(Text_t text) {
    List_t clusters = EMPTY_LIST;
    for (int64_t i = 1; i <= (int64_t)text.length; i++) {
        Text_t cluster = Text$slice(text, I(i), I(i));
        List$insert(&clusters, &cluster, I_small(0), sizeof(Text_t));
    }
    return clusters;
}

public
List_t Text$utf8(Text_t text) {
    if (text.length == 0) return EMPTY_ATOMIC_LIST;
    int64_t capacity = (int64_t)text.length;
    Byte_t *buf = GC_MALLOC_ATOMIC(sizeof(Byte_t[capacity]));
    int64_t i = 0;
    u8_buf_append(text, &buf, &capacity, &i);
    return (List_t){
        .data = buf, .length = (uint64_t)i, .stride = 1, .atomic = 1, .free = MIN(LIST_MAX_FREE_ENTRIES, capacity - i)};
}

public
List_t Text$utf16(Text_t text) {
    if (text.length == 0) return EMPTY_ATOMIC_LIST;
    List_t utf32 = Text$utf32(text);
    if (utf32.length == 0) return EMPTY_ATOMIC_LIST;
    List_t utf16 = {.free = MIN(LIST_MAX_FREE_ENTRIES, (uint64_t)utf32.length), .atomic = 1};
    utf16.data = GC_MALLOC_ATOMIC(sizeof(int32_t[utf16.free]));
    for (int64_t i = 0; i < (int64_t)utf32.length; i++) {
        uint16_t u16_buf[4];
        size_t u16_len = sizeof(u16_buf) / sizeof(u16_buf[0]);
        uint16_t *chunk_u16 = u32_to_u16(utf32.data + utf32.stride * i, 1, u16_buf, &u16_len);
        if (chunk_u16 == NULL) fail("Invalid codepoints encountered!");
        List$insert_all(&utf16, (List_t){.data = chunk_u16, .stride = sizeof(uint16_t), .length = (uint64_t)u16_len},
                        I(0), sizeof(uint16_t));
        if (chunk_u16 != u16_buf) free(chunk_u16);
    }
    return utf16;
}

public
List_t Text$utf32(Text_t text) {
    if (text.length == 0) return EMPTY_ATOMIC_LIST;
    List_t codepoints = EMPTY_ATOMIC_LIST;
    TextIter_t state = NEW_TEXT_ITER_STATE(text);
    for (int64_t i = 0; i < (int64_t)text.length; i++) {
        int32_t grapheme = Text$get_grapheme_fast(&state, i);
        if (grapheme < 0) {
            for (int64_t c = 0; c < NUM_GRAPHEME_CODEPOINTS(grapheme); c++) {
                ucs4_t subg = GRAPHEME_CODEPOINTS(grapheme)[c];
                List$insert(&codepoints, &subg, I_small(0), sizeof(ucs4_t));
            }
        } else {
            List$insert(&codepoints, &grapheme, I_small(0), sizeof(ucs4_t));
        }
    }
    return codepoints;
}

static INLINE const char *codepoint_name(ucs4_t c) {
    char *name = GC_MALLOC_ATOMIC(UNINAME_MAX);
    char *found_name = unicode_character_name(c, name);
    if (found_name) return found_name;
    const uc_block_t *block = uc_block(c);
    if (!block) return "???";
    assert(block);
    return String(block->name, "-", hex(c, .no_prefix = true, .uppercase = true));
}

public
List_t Text$codepoint_names(Text_t text) {
    List_t names = EMPTY_LIST;
    TextIter_t state = NEW_TEXT_ITER_STATE(text);
    for (int64_t i = 0; i < (int64_t)text.length; i++) {
        int32_t grapheme = Text$get_grapheme_fast(&state, i);
        if (grapheme < 0) {
            for (int64_t c = 0; c < NUM_GRAPHEME_CODEPOINTS(grapheme); c++) {
                const char *name = codepoint_name(GRAPHEME_CODEPOINTS(grapheme)[c]);
                Text_t name_text = Text$from_str(name);
                List$insert(&names, &name_text, I_small(0), sizeof(Text_t));
            }
        } else {
            const char *name = codepoint_name((ucs4_t)grapheme);
            Text_t name_text = Text$from_str(name);
            List$insert(&names, &name_text, I_small(0), sizeof(Text_t));
        }
    }
    return names;
}

public
OptionalText_t Text$from_utf8(List_t units) {
    if (units.length == 0) return EMPTY_TEXT;
    if (units.stride != sizeof(uint8_t)) List$compact(&units, sizeof(uint8_t));
    return Text$from_strn(units.data, (size_t)units.length);
}

public
OptionalText_t Text$from_utf16(List_t units) {
    if (units.length == 0) return EMPTY_TEXT;
    if (units.stride != sizeof(int16_t)) List$compact(&units, sizeof(int16_t));

    size_t length = 256;
    uint8_t buf[length];
    uint8_t *u8 = u16_to_u8(units.data, (size_t)units.length, buf, &length);
    Text_t ret =
        Text$from_utf8((List_t){.data = u8, .length = (uint64_t)length, .stride = sizeof(uint8_t), .atomic = 1});
    if (u8 != buf) free(u8);
    return ret;
}

public
OptionalText_t Text$from_utf32(List_t codepoints) {
    if (codepoints.length == 0) return EMPTY_TEXT;
    if (codepoints.stride != sizeof(uint32_t)) List$compact(&codepoints, sizeof(uint32_t));

    List_t graphemes = EMPTY_ATOMIC_LIST;
    Table_t unique_clusters = EMPTY_TABLE;
    const uint32_t *pos = (const uint32_t *)codepoints.data;
    const uint32_t *end = (const uint32_t *)&pos[codepoints.length];
    // Iterate over grapheme clusters
    for (const uint32_t *next; (next = u32_grapheme_next(pos, end)); pos = next) {
        // Buffer for normalized cluster:
        uint32_t buf[256];
        size_t u32_normlen = sizeof(buf) / sizeof(buf[0]);
        if (u32_check(pos, (size_t)(next - pos)) != NULL) return NONE_TEXT;
        uint32_t *u32s_normalized = u32_normalize(UNINORM_NFC, pos, (size_t)(next - pos), buf, &u32_normlen);

        int32_t g = get_synthetic_grapheme(u32s_normalized, (int64_t)u32_normlen);
        List$insert(&graphemes, &g, I(0), sizeof(int32_t));
        Table$get_or_setdefault(&unique_clusters, int32_t, uint8_t, g, (uint8_t)unique_clusters.entries.length,
                                Table$info(&Int32$info, &Byte$info));

        if (u32s_normalized != buf) free(u32s_normalized);

        if (unique_clusters.entries.length == 256) {
            List_t remaining_codepoints = {
                .length = (uint64_t)(end - next),
                .data = (void *)next,
                .stride = sizeof(int32_t),
            };
            OptionalText_t remainder = Text$from_utf32(remaining_codepoints);
            if (remainder.tag == TEXT_NONE) return NONE_TEXT;
            return concat2_assuming_safe(Text$from_components(graphemes, unique_clusters), remainder);
        }
    }
    return Text$from_components(graphemes, unique_clusters);
}

public
OptionalText_t Text$from_codepoint_names(List_t codepoint_names) {
    List_t codepoints = EMPTY_LIST;
    for (int64_t i = 0; i < (int64_t)codepoint_names.length; i++) {
        Text_t *name = ((Text_t *)(codepoint_names.data + i * codepoint_names.stride));
        const char *name_str = Text$as_c_string(*name);
        ucs4_t codepoint = unicode_name_character(name_str);
        if (codepoint == UNINAME_INVALID) return NONE_TEXT;
        List$insert(&codepoints, &codepoint, I_small(0), sizeof(ucs4_t));
    }
    return Text$from_utf32(codepoints);
}

public
List_t Text$lines(Text_t text) {
    List_t lines = EMPTY_LIST;
    TextIter_t state = NEW_TEXT_ITER_STATE(text);
    for (int64_t i = 0, line_start = 0; i < (int64_t)text.length; i++) {
        int32_t grapheme = Text$get_grapheme_fast(&state, i);
        if (grapheme == '\r' && Text$get_grapheme_fast(&state, i + 1) == '\n') { // CRLF
            Text_t line = Text$slice(text, I(line_start + 1), I(i));
            List$insert(&lines, &line, I_small(0), sizeof(Text_t));
            i += 1; // skip one extra for CR
            line_start = i + 1;
        } else if (grapheme == '\n') { // newline
            Text_t line = Text$slice(text, I(line_start + 1), I(i));
            List$insert(&lines, &line, I_small(0), sizeof(Text_t));
            line_start = i + 1;
        } else if (i == text.length - 1 && line_start != i) { // last line
            Text_t line = Text$slice(text, I(line_start + 1), I(i + 1));
            List$insert(&lines, &line, I_small(0), sizeof(Text_t));
        }
    }
    return lines;
}

typedef struct {
    TextIter_t state;
    int64_t i;
} line_iter_state_t;

static OptionalText_t next_line(line_iter_state_t *state) {
    Text_t text = state->state.stack[0].text;
    for (int64_t i = state->i; i < (int64_t)text.length; i++) {
        int32_t grapheme = Text$get_grapheme_fast(&state->state, i);
        if (grapheme == '\r' && Text$get_grapheme_fast(&state->state, i + 1) == '\n') { // CRLF
            Text_t line = Text$slice(text, I(state->i + 1), I(i));
            state->i = i + 2; // skip one extra for CR
            return line;
        } else if (grapheme == '\n') { // newline
            Text_t line = Text$slice(text, I(state->i + 1), I(i));
            state->i = i + 1;
            return line;
        } else if (i == text.length - 1 && state->i != i) { // last line
            Text_t line = Text$slice(text, I(state->i + 1), I(i + 1));
            state->i = i + 1;
            return line;
        }
    }
    return NONE_TEXT;
}

public
Closure_t Text$by_line(Text_t text) {
    return (Closure_t){
        .fn = (void *)next_line,
        .userdata = new (line_iter_state_t, .state = NEW_TEXT_ITER_STATE(text), .i = 0),
    };
}

PUREFUNC public bool Text$is_none(const void *t, const TypeInfo_t *info) {
    (void)info;
    return ((Text_t *)t)->tag == TEXT_NONE;
}

public
Int_t Text$memory_size(Text_t text) {
    switch (text.tag) {
    case TEXT_ASCII: return Int$from_int64((int64_t)sizeof(Text_t) + (int64_t)sizeof(char[text.length]));
    case TEXT_GRAPHEMES: return Int$from_int64((int64_t)sizeof(Text_t) + (int64_t)sizeof(int32_t[text.length]));
    case TEXT_BLOB:
        return Int$from_int64((int64_t)sizeof(Text_t) + (int64_t)((void *)text.blob.bytes - (void *)text.blob.map)
                              + (int64_t)sizeof(uint8_t[text.length]));
    case TEXT_CONCAT:
        return Int$plus(Int$from_int64((int64_t)sizeof(Text_t)),
                        Int$plus(Text$memory_size(*text.left), Text$memory_size(*text.right)));
    default: errx(1, "Invalid text tag: %d", text.tag);
    }
}

public
Text_t Text$layout(Text_t text) {
    switch (text.tag) {
    case TEXT_ASCII: return Text$concat(Text("ASCII("), Int64$value_as_text(text.length), Text(")"));
    case TEXT_GRAPHEMES: return Text$concat(Text("Graphemes("), Int64$value_as_text(text.length), Text(")"));
    case TEXT_BLOB: return Text$concat(Text("Blob("), Int64$value_as_text(text.length), Text(")"));
    case TEXT_CONCAT:
        return Text$concat(Text("Concat("), Text$layout(*text.left), Text(", "), Text$layout(*text.right), Text(")"));
    default: errx(1, "Invalid text tag: %d", text.tag);
    }
}

public
void Text$serialize(const void *obj, FILE *out, Table_t *pointers, const TypeInfo_t *info) {
    (void)info;
    const char *str = Text$as_c_string(*(Text_t *)obj);
    int64_t len = (int64_t)strlen(str);
    Int64$serialize(&len, out, pointers, &Int64$info);
    fwrite(str, sizeof(char), (size_t)len, out);
}

public
void Text$deserialize(FILE *in, void *out, List_t *pointers, const TypeInfo_t *info) {
    (void)info;
    int64_t len = 0;
    Int64$deserialize(in, &len, pointers, &Int64$info);
    if (len < 0) fail("Cannot deserialize text with a negative length!");
    char *buf = GC_MALLOC_ATOMIC((size_t)len + 1);
    if (fread(buf, sizeof(char), (size_t)len, in) != (size_t)len) fail("Not enough data in stream to deserialize");
    buf[len + 1] = '\0';
    *(Text_t *)out = Text$from_strn(buf, (size_t)len);
}

public
const TypeInfo_t Text$info = {
    .size = sizeof(Text_t),
    .align = __alignof__(Text_t),
    .tag = TextInfo,
    .TextInfo = {.lang = "Text"},
    .metamethods = Text$metamethods,
};