The Line Index

The piece table answers "what byte is at offset 12,345?" — but nothing an editor displays is phrased in offsets. The screen shows lines; the scrollbar is a fraction of lines; clicking needs "which line is under y"; damage tracking (lesson 12) wants "which rows does this edit dirty?". Between the flat byte world and the line world sits one small, crucial structure: the line index — a sorted array of the byte offsets where each line begins.

The definition that makes every edge case fall out cleanly:

• Offset 0 is always a line start (even in an empty document — an empty document has one line, which is empty).
• Every '\n' at offset i ends a line, and offset i + 1 starts the next one. Consequently "a\nb" has starts [0, 2], and "a\n" has starts [0, 2] too — the second line exists and is empty. This matches what every editor shows: a file ending in a newline has one final empty line your caret can sit on.

Two lookups then run the whole show, both trivial over a sorted array:

• line_of(offset): the greatest L with starts[L] <= offset — one std::upper_bound, minus one. Every offset in the document (including size(), where the end-of-document caret sits) belongs to exactly one line. Note the convention this implies: the offset of a '\n' still belongs to the line it terminates.
• line_span(L): the line's content is [starts[L], starts[L+1] - 1) for interior lines (the - 1 excludes the newline), and [starts[L], text.size()) for the last one.

A pleasant consequence of UTF-8's design (lesson 6): since bytes below 0x80 never occur inside a multi-byte sequence, scanning raw bytes for 0x0A finds exactly the real newlines — the line index never needs to decode anything. (Full Unicode also defines exotic breaks — U+2028 LINE SEPARATOR and friends — which real editors mostly ignore for line structure, and so do we. Windows CRLF? Treat the '\r' as an ordinary byte of line content and strip it at file load/save time; normalizing at the boundary keeps '\n'-only logic everywhere inside, which is exactly what VS Code and friends do.)

Keeping it current: shift, don't rebuild

Rebuilding the index is O(document) — fine on load, absurd per keystroke on a big file (type "hello" and you've re-scanned 500 MB five times). But look at what an edit actually does to the array:

• Insert of n bytes at pos: every start strictly greater than pos slides right by n. (A start equal to pos stays: inserting at the head of a line prepends to that line; its start doesn't move.) If the inserted text itself contains newlines, each '\n' at inserted index k mints a brand-new start at pos + k + 1, spliced in sorted position.
• Erase of len bytes at pos: starts inside (pos, pos + len] correspond to newlines that just vanished — remove them. Starts beyond pos + len slide left by len.

Both are O(lines after the edit point) array traffic and O(newlines in the change) new entries — independent of document size. The tests keep you honest with a torture loop comparing your incremental index against a from-scratch rebuild after every random edit; if the two ever disagree, you'll get the exact reproducing sequence for free (it's deterministic).

This "notify the index after each document edit" pattern — the piece table doesn't know the index exists; the editor calls on_insert/ on_erase on both — is the shape all derived state takes in this course: the layout cache (lesson 9) and damage list (lesson 12) hang off the same notifications.