UTF-8 From Scratch

Your editor's buffer will hold bytes. The user's text is characters — more precisely Unicode codepoints, integers from U+0000 to U+10FFFF. The bridge is UTF-8, and an editor cannot outsource this bridge: caret movement, backspace, hit testing, and clipboard exchange all need to know where one codepoint ends and the next begins. Get it wrong and pressing Backspace after typing "é" deletes half of the é, leaving a mangled byte that renders as garbage forever after. So we build the decoder ourselves, to specification, and the tests hold you to the specification's sharp edges.

The encoding, in one table

UTF-8 (Thompson & Pike, 1992 — famously sketched on a diner placemat) encodes each codepoint in 1–4 bytes. The first byte's high bits announce the sequence length; continuation bytes always start 10:

codepoint range      bytes  bit layout
U+0000  .. U+007F    1      0xxxxxxx
U+0080  .. U+07FF    2      110xxxxx 10xxxxxx
U+0800  .. U+FFFF    3      1110xxxx 10xxxxxx 10xxxxxx
U+10000 .. U+10FFFF  4      11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

Decoding is: read the lead byte, learn the length, shift in the low six bits of each continuation byte. é (U+00E9) is 0xC3 0xA9: 110_00011 + 10_101001 → 00011_101001 = 0xE9.

Three properties made UTF-8 conquer the world, and each one matters to your editor directly:

• ASCII is unchanged. Every ASCII file is already valid UTF-8, and bytes < 0x80 never appear inside a multi-byte sequence. Your lesson-8 line index can scan for '\n' bytes without decoding anything.
• Self-synchronizing. From any byte position you can find the nearest codepoint boundary by skipping backward over at most three 10xxxxxx bytes. Caret movement never has to decode from the start of the file — this is the entire subject of the second challenge.
• Byte-wise sort order equals codepoint order. Not editor-critical, but it's why UTF-8 works in filenames and databases without special collation shims.

The sharp edges

A decoder that only handles well-formed input is half a decoder. Editors open arbitrary files: truncated downloads, Latin-1 mislabeled as UTF-8, binary garbage. The Unicode standard is precise about what's invalid, and two rules exist for security reasons, not tidiness:

• Overlong encodings are forbidden. The byte pair 0xC0 0xAF mechanically decodes to 0x2F — / — but the two-byte form of a codepoint that fits in one byte is illegal. History's reason: pre-2001 decoders that accepted overlongs let attackers smuggle ../ past path-validation code that only checked for the one-byte spelling. Your decoder must reject any sequence longer than its codepoint needs (that's 0xC0/0xC1 outright, 0xE0 0x80-0x9F, 0xF0 0x80-0x8F).
• Surrogates (U+D800–U+DFFF) are forbidden in UTF-8. They are UTF-16 plumbing, not characters; three-byte sequences encoding them (0xED 0xA0-0xBF ...) are invalid. Also invalid: anything above U+10FFFF (leads 0xF5–0xFF), stray continuation bytes, and sequences cut off early.

What should an editor do with invalid bytes? The universal answer (HTML5, Rust's String::from_utf8_lossy, every serious editor): replace each offending byte with U+FFFD �, the replacement character, and carry on. We adopt the simplest standard-sanctioned policy: an invalid or truncated sequence consumes exactly one byte and yields U+FFFD; then decoding resumes at the next byte. One byte, not "the whole broken sequence" — restarting at the very next byte is what lets a single corrupted byte in the middle of a CJK file cost one � instead of desynchronizing the rest of the line.

A design note on types: the decoder returns char32_t (a codepoint is an integer — C++'s dedicated type documents the intent), and takes std::string_view — a non-owning pointer+length pair. All the text plumbing from here on accepts string_view, so it works on a std::string, a piece-table span, or a memory-mapped file without copying.

Boundaries without decoding

The caret challenge is subtler than it looks. "Move left one character" must work even when the text isn't valid UTF-8 — the user can place the caret in a file full of garbage, and Backspace still has to delete something sensible. The self-synchronization property gives the algorithm: from byte index i, step back over continuation bytes (at most 3 — anything more is malformed anyway), landing on a lead byte. Then sanity-check: does that lead byte actually claim enough length to reach past where you started? If yes, it's the boundary; if no, the bytes were malformed, and the single byte before i is treated as its own one-column unit — the � policy again, applied to navigation. The same logic runs forward for "move right".

This byte-level view is deliberately humble: real cursor movement also knows about combining marks (e + U+0301 = é as two codepoints), emoji joined by zero-width joiners, and other grapheme-cluster rules — that's another layer (with its own Unicode annex, UAX #29) built on top of codepoint boundaries, and libraries like ICU provide it. Codepoint boundaries are the load-bearing floor, and they're ours to get exactly right.