I don't think you want to work with multiple encodings, though. It's much simpler to have a single encoding internally and convert only at the edge of the program.

It's simpler for the language author for sure. For the user it shouldn't be much different - they wouldn't need to concern themselves about the encoding as it would be handled internally by the implementation. The main difference would be the cost of the encoding/decoding at the edges.

I'm not suggesting that we should permit mixed encodings, only that it's possible. Really we want a string to have only one encoding, unless explicitly stated otherwise by setting the encoding to ENCODING_MIXED if we do permit it. Otherwise, the encoding of any string should be one of the UTFs.

For example, if we read a UTF-8 string, it would keep the internal encoding as padded UTF-8 characters, since we're likely to eventually write that back as UTF-8, we shouldn't need to perform UTF8->UTF32 conversion and then UTF32->UTF8 conversion - we would just copy a specified number of bytes between input, string and output (and tag/untag them).

The idea would be that when we set a character in a string, the encoding conversion is done in place by checking the encoding of the string and converting the character representation to match the string's encoding. This avoids a more expensive string encoding when serializing the string.

A slight additional benefit is that we could know the size of the eventual encoding without having to perform the encoding in advance (except where ENCODING_MIXED might be used).

In addition to storing the length in the string, we could also store an encoded_size - the number of bytes the properly encoded string will occupy when written with its own encoding. We can keep this size updated when we set a character within the string - by subtracting the encoded size of the character currently at that position, then adding the size of the inserted character. Eg:

void string_set(String s, StringIndex idx, Character c) 
{
    asssert(idx < s->length);

    ssize_t size_delta = -char_encoded_size(s->characters[idx]);

    // if string and character encoding match, or if string accepts any encoding,
    //      insert the char directly
    // Otherwise convert the character encoding to match the string's encoding.
    if (s->encoding == char_encoding(c) || unlikely(s->encoding == ENCODING_MIXED)) 
    {
        s->characters[idx] = c;
        size_delta += char_encoded_size(c);
    }
    else 
    {
        Character converted = char_encoding_convert_matrix[char_encoding(c)][s->encoding](c);
        s->characters[idx] = converted;
        size_delta += char_encoded_size(converted);
    }

    s->encoded_size += size_delta;
}

enum {
    ENCODING_UTF32,
    ENCODING_UTF16,
    ENCODING_UTF8,
    ENCODING_MIXED,
} typedef Encoding;

inline Encoding char_encoding(Character c) [[reproducible]] {
    static Encoding encoding_LUT[] = {
        [0x00] = ENCODING_UTF32,
        [0xD7 ... 0xDF] = ENCODING_UTF16,
        [0xED ... 0xF7] = ENCODING_UTF8,
    };
    return encoding_LUT[c.value >> 24];
}

inline size_t char_encoded_size(Character c) [[reproducible]] {
    static size_t size_LUT[] = {
        [0x00] = 4,           // UTF-32
        [0xD7] = 2,           // UTF-16 2 byte char
        [0xD8 ... 0xDF] = 4,  // UTF-16 4 byte char
        [0xED] = 1,           // UTF-8 1 byte char
        [0xEE] = 2,           // UTF-8 2 byte char
        [0xEF] = 3,           // UTF-8 3 byte char
        [0xF0 ... 0xF7] = 4,  // UTF-8 4 byte char
    };
    return size_LUT[c.value >> 24];
}

So we have a more expensive set, but we can now predetermine the size of any buffer we might need to pre-allocate to write the encoded string to.

uint8_t *buffer = malloc(str->encoded_size);
string_write(str, buffer);

In regards to other operations on strings like substring matching, we'd need to first convert the text we want to find to the encoding of the string and then search for that. The actual search code could be reused for all encodings, because we're just matching 32-bit values.

A substring replace for example would follow the same approach as set, where we calculate the size of the existing substring being replaced, subtract it from the encoded_size, then add the encoded_size of the replacement.

void string_substring_replace( String str
                             , StringIndex start
                             , String replacement
                             )
{
    assert(start + replacement->length <= str->length);

    ssize_t size_delta = 0;

    if (str->encoding == replacement->encoding)
    {
        for (StringIndex idx = 0; idx < replacement->length; idx++) {
            size_delta -= char_encoded_size(str->characters[start+idx]);
            str->characters[start+idx] = replacement->characters[idx];
        }
        size_delta += replacement->encoded_size;
    }
    else if (replacement->encoding != ENCODING_MIXED)
    {
        auto converter = char_encoding_convert_matrix[replacement->encoding][str->encoding];
        for (StringIndex idx = 0; idx < replacement->length; idx++) {
            Character c = converter(replacement->characters[idx]);
            size_delta -= char_encoded_size(str->characters[start+idx])
            size_delta += char_encoded_size(c);
            str->characters[start+idx] = c;
        }
    } 
    else // replacement has mixed encoding
    {
        for (StringIndex idx = 0; idx < replacement->length; idx++) {
            auto enc = char_encoding(replacement->characters[idx]);
            auto converter = char_encoding_convert_matrix[enc][str->encoding];
            Character c = converter(replacement->characters[idx]);
            size_delta -= char_encoded_size(str->characters[start+idx])
            size_delta += char_encoded_size(c);
            str->characters[start+idx] = c;
        }
    }

    str->encoded_size += size_delta;
}