Layout: Greedy Word Wrap

A document line and a screen line are different things, and the moment you admit that, half the editor's remaining architecture falls into place. A logical line is what the line index tracks: bytes between newlines, possibly thousands of characters. A visual row is what fits across the window. The mapping between them is the layout engine, and in a text editor its core algorithm is greedy word wrap: pack characters into a row until the next one won't fit, then break — preferably at a space.

Everything downstream speaks in the layout's output. Hit testing (lesson 10) turns a click's y into a row index; the caret is drawn at a row + x-offset; scrolling (lesson 12) is measured in rows; damage is a band of rows. So the output type is worth fixing carefully. A row is just a byte range within its line:

struct Row {
    size_t begin;   // byte offsets into the logical line's text
    size_t end;     // half-open, as always
};

No copied text — offsets into text owned by the document, the same string_view discipline as everywhere else. Note what a Row doesn't contain: no pixel positions. Given a row, x-positions come from the same metrics used to wrap (caret_xs from lesson 5) — computed on demand, never stored to go stale.

The greedy algorithm, precisely

"Greedy" wrapping (as opposed to the global-optimizing Knuth–Plass algorithm TeX uses for paragraphs — beautiful, but no editor wants line breaks changing above the cursor as you type) is a single forward scan. The subtleties are worth spelling out, because each is a bug I promise you'd otherwise ship:

• Track the last break opportunity. As you scan, remember the position just after the most recent space in the current row. On overflow, break there if you have one — the space stays at the end of the upper row, where it invisibly "hangs" — otherwise you're inside one unbroken word longer than the window: hard-break right where you are, mid-word. (Try narrowing any editor around a long URL: mid-word breaks are correct behavior, not a cop-out.)
• Overflow means strictly greater. A row that exactly fills max_width is a fit, not an overflow. Get this backwards and every perfectly-full row wraps one character early.
• Always make progress. If the window is narrower than a single character, each character still gets a row of its own. The overflow check applies only when the row already has content (i > start) — otherwise you'd emit empty rows forever. This is the classic infinite-loop bug in wrap code; the tests include the killer case.
• After a break, re-measure the carry-over. The characters between the break point and your scan position move down to the new row; the new row's running width is their total, and the break-opportunity tracker resets to the last space among them. Then re-test the same character that overflowed — it may overflow the new row too.
• The empty line still exists. An empty logical line produces one empty row {0, 0} — it occupies vertical space and the caret can sit on it. Zero rows would make the line invisible and unclickable.

This challenge wraps printable-ASCII text (one byte = one column unit, widths from the metrics table, anything else measuring as '?'); the final challenge generalizes the same algorithm to UTF-8 codepoints using your lesson-6 decoder. Kerning is deliberately ignored during wrapping — a break destroys the pair anyway, and real shaping engines measure runs, not pairs, at this stage.

Cache it, invalidate it honestly

Wrapping is O(line length), and a keystroke changes one logical line — yet a naive editor re-wraps the whole document per keystroke (and then wonders why a 100k-line file types slowly). The cure is a layout cache: line number → its rows, filled lazily as lines become visible, so cold lines are never wrapped at all.

The hard part of any cache is invalidation, and text edits are a particularly instructive case because line numbers shift. Say lines [first, first + old_count) were edited and became new_count lines:

• Cached entries in the edited range are stale: drop them (they'll be re-wrapped lazily if ever visible again).
• Entries below the edit still hold perfectly good rows — but they're filed under old line numbers: re-key them by new_count - old_count. Dropping them instead would be correct but would re-wrap the whole visible tail after every Enter keypress — the cache would stop earning its rent exactly when files get big.
• Entries above the edit are untouched.

Two width-related notes that follow from the same honesty: when the window resizes, every row boundary is suspect — the whole cache drops (and this is fine: it refills lazily, visible lines first). And the cache key deliberately does not include the width; the owner clears on width change instead. One cache, one invalidation policy, no stale reads.