// 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_codepoints()`
// method and `Text.from_codepoints()`, 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 <unicase.h>
#include <unictype.h>
#include <unigbrk.h>
#include <uniname.h>
#include <unistr.h>
#include <unistring/version.h>
#include <uniwidth.h>

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

// Use inline version of the siphash code for performance:
#include "siphash.h"
#include "siphash-internals.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 = {}; // 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);

public Text_t EMPTY_TEXT = {
    .length=0,
    .tag=TEXT_ASCII,
    .ascii=0,
};

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;
    // Eat up any space needed to make arena 32-bit aligned:
    if ((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 + 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);
        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 bytes 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 < 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 < 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 int64_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 (int 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 < a.length; i++)
                *(dest++) = (int32_t)a.ascii[i];
        } else if (a.tag == TEXT_BLOB) {
            for (int64_t i = 0; i < 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 < b.length; i++)
                *(dest++) = (int32_t)b.ascii[i];
        } else if (b.tag == TEXT_BLOB) {
            for (int64_t i = 0; i < 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)]));
        dest += 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);
    }

    Text_t glue = Textヽfrom_codepoints((List_t){.data=norm_buf, .length=(int64_t)norm_length, .stride=sizeof(int32_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 < 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)));
                repeated_width = target_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 Texts(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 = text.length + first + 1;
    if (last < 0) last = text.length + last + 1;

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

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

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

    while (text.tag == TEXT_CONCAT) {
        if (last < text.left->length) {
            text = *text.left;
        } else if (first > text.left->length) {
            first -= text.left->length;
            last -= 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 < 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 < 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 < 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 Text_t Textヽcluster(Text_t text, Int_t index)
{
    return Textヽslice(text, index, index);
}

static Text_t Textヽfrom_components(List_t graphemes, Table_t unique_clusters)
{
    struct {
        int32_t map[unique_clusters.entries.length];
        uint8_t bytes[graphemes.length];
    } *blob;
    // If blob optimization will save at least 200 bytes:
    if (unique_clusters.entries.length <= 256 && sizeof(*blob) + 200 < sizeof(int32_t[graphemes.length])) {
        Text_t ret = {
            .tag=TEXT_BLOB,
            .length=graphemes.length,
            .depth=0,
        };
        blob = GC_MALLOC_ATOMIC(sizeof(*blob));
        for (int64_t i = 0; i < unique_clusters.entries.length; i++) {
            struct { int32_t g; uint8_t b; } *entry = unique_clusters.entries.data + i*unique_clusters.entries.stride;
            blob->map[entry->b] = entry->g;
        }
        for (int64_t i = 0; i < 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);
            blob->bytes[i] = *byte;
        }
        ret.blob.map = &blob->map[0];
        ret.blob.bytes = &blob->bytes[0];
        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 (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 = {};
    Table_t unique_clusters = {};
    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);

        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);

        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 != 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(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, char **buf, int64_t *capacity, int64_t *i)
{
    switch (text.tag) {
    case TEXT_ASCII: {
        if (*i + text.length > (int64_t)*capacity) {
            *capacity = *i + text.length + 1;
            *buf = GC_REALLOC(*buf, (size_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 < 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, (size_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, (size_t)*capacity);
                }

                memcpy(*buf + *i, u8, u8_len);
                *i += (int64_t)u8_len;
            }
        }
        break;
    }
    case TEXT_BLOB: {
        for (int64_t g = 0; g < 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, (size_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, (size_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, &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 < 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 < 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 < 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 < 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 >= 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 + 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 + text.length);

        state->stack_index += 1;
        if (index < offset + 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 + 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 < target_state->stack[0].text.length; i++) {
        int32_t text_i = Textヽget_grapheme_fast(text_state, pos + i);
        int32_t prefix_i = Textヽget_grapheme_fast(target_state, i);
        if (text_i != prefix_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, false) ? 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, false) ? 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 < text->stack[0].text.length; t++) {
        if (g == Textヽget_grapheme_fast(text, t)) {
            return true;
        }
    }
    return false;
}

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 < 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 < text.length; ) {
        for (int64_t r = 0; r < replacement_list.length; r++) {
            struct { Text_t target, replacement; } *entry = replacement_list.data + r*replacement_list.stride;
            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 < text.length)
        result = concat2(result, Textヽslice(text, I(span_start+1), I(text.length)));
    return result;
}

public Text_t Textヽreplace(Text_t text, Text_t target, Text_t replacement)
{
    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 < 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 < text.length)
        result = concat2(result, Textヽslice(text, I(span_start+1), I(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 < 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 = {};
    for (int64_t i = 0; i < text.length; ) {
        int64_t span_len = 0;
        while (i + span_len < 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 = {};
    for (int64_t i = 0; i < text.length; ) {
        int64_t span_len = 0;
        while (i + span_len < text.length && !_has_grapheme(&delim_state, Textヽget_grapheme_fast(&text_state, i + span_len))) {
            span_len += 1;
        }
        bool trailing_delim = i + span_len < 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 < text.length && _has_grapheme(&delim_state, Textヽget_grapheme_fast(&text_state, i))) {
            i += 1;
        }
        if (i >= 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 >= 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 < 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 >= 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 < 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 < 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_codepoints(text);
    const char *uc_language = Textヽas_c_string(language);
    size_t out_len = 0;
    ucs4_t *upper = u32_toupper(codepoints.data, (size_t)codepoints.length, uc_language, UNINORM_NFC, NULL, &out_len);
    Text_t ret = Textヽfrom_codepoints((List_t){.data=upper, .length=(int64_t)out_len, .stride=sizeof(int32_t)});
    return ret;
}

public Text_t Textヽlower(Text_t text, Text_t language)
{
    if (text.length == 0) return text;
    List_t codepoints = Textヽutf32_codepoints(text);
    const char *uc_language = Textヽas_c_string(language);
    size_t out_len = 0;
    ucs4_t *lower = u32_tolower(codepoints.data, (size_t)codepoints.length, uc_language, UNINORM_NFC, NULL, &out_len);
    Text_t ret = Textヽfrom_codepoints((List_t){.data=lower, .length=(int64_t)out_len, .stride=sizeof(int32_t)});
    return ret;
}

public Text_t Textヽtitle(Text_t text, Text_t language)
{
    if (text.length == 0) return text;
    List_t codepoints = Textヽutf32_codepoints(text);
    const char *uc_language = Textヽas_c_string(language);
    size_t out_len = 0;
    ucs4_t *title = u32_totitle(codepoints.data, (size_t)codepoints.length, uc_language, UNINORM_NFC, NULL, &out_len);
    Text_t ret = Textヽfrom_codepoints((List_t){.data=title, .length=(int64_t)out_len, .stride=sizeof(int32_t)});
    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 = colorize ? Text("\x1b[35m") : EMPTY_TEXT;
    if (!Textヽequal_values(quotation_mark, Text("\"")) && !Textヽequal_values(quotation_mark, Text("'")) && !Textヽequal_values(quotation_mark, Text("`")))
        ret = concat2_assuming_safe(ret, Text("$"));

    ret = concat2_assuming_safe(ret, quotation_mark);
    int32_t quote_char = Textヽget_grapheme(quotation_mark, 0);

#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 < 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: {
            if (g == quote_char) {
                flush_unquoted();
                if (colorize) ret = concat2_assuming_safe(ret, Text("\x1b[34;1m"));
                ret = concat2_assuming_safe(ret, Text("\\"));
                ret = concat2_assuming_safe(ret, quotation_mark);
                if (colorize) ret = concat2_assuming_safe(ret, Text("\x1b[0;35m"));
            } else {
                unquoted_span += 1;
            }
            break;
        }
        }
    }
    flush_unquoted();
#undef add_escaped
#undef flush_unquoted

    ret = concat2_assuming_safe(ret, quotation_mark);
    if (colorize)
        ret = concat2_assuming_safe(ret, Text("\x1b[m"));

    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 < 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") : EMPTY_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 < 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 = {};
    for (int64_t i = 1; i <= 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ヽutf32_codepoints(Text_t text)
{
    List_t codepoints = {.atomic=1};
    TextIter_t state = NEW_TEXT_ITER_STATE(text);
    for (int64_t i = 0; i < 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;
}

public List_t Textヽutf8_bytes(Text_t text)
{
    const char *str = Textヽas_c_string(text);
    return (List_t){.length=(int64_t)strlen(str), .stride=1, .atomic=1, .data=(void*)str};
}

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);
    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 = {};
    TextIter_t state = NEW_TEXT_ITER_STATE(text);
    for (int64_t i = 0; i < 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 Text_t Textヽfrom_codepoints(List_t codepoints)
{
    if (codepoints.stride != sizeof(uint32_t))
        Listヽcompact(&codepoints, sizeof(uint32_t));

    List_t graphemes = {};
    Table_t unique_clusters = {};
    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]);
        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=(int64_t)(end-next),
                .data=(void*)next,
                .stride=sizeof(int32_t),
            };
            return concat2_assuming_safe(Textヽfrom_components(graphemes, unique_clusters), Textヽfrom_codepoints(remaining_codepoints));
        }
    }
    return Textヽfrom_components(graphemes, unique_clusters);
}

public OptionalText_t Textヽfrom_codepoint_names(List_t codepoint_names)
{
    List_t codepoints = {};
    for (int64_t i = 0; i < 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_codepoints(codepoints);
}

public OptionalText_t Textヽfrom_bytes(List_t bytes)
{
    if (bytes.stride != sizeof(int8_t))
        Listヽcompact(&bytes, sizeof(int8_t));

    return Textヽfrom_strn(bytes.data, (size_t)bytes.length);
}

public List_t Textヽlines(Text_t text)
{
    List_t lines = {};
    TextIter_t state = NEW_TEXT_ITER_STATE(text);
    for (int64_t i = 0, line_start = 0; i < 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 < 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)->length < 0;
}

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: ", text.tag);
    }
}

public Text_t Textヽlayout(Text_t text)
{
    switch (text.tag) {
    case TEXT_ASCII:
        return Texts(Text("ASCII("), Int64ヽas_text((int64_t[1]){text.length}, false, NULL), Text(")"));
    case TEXT_GRAPHEMES:
        return Texts(Text("Graphemes("), Int64ヽas_text((int64_t[1]){text.length}, false, NULL), Text(")"));
    case TEXT_BLOB:
        return Texts(Text("Blob("), Int64ヽas_text((int64_t[1]){text.length}, false, NULL), Text(")"));
    case TEXT_CONCAT:
        return Texts(Text("Concat("), Textヽlayout(*text.left), Text(", "), Textヽlayout(*text.right), Text(")"));
    default: errx(1, "Invalid text tag: ", 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,
};

// vim: ts=4 sw=0 et cino=L2,l1,(0,W4,m1,\:0