Incremental Search

Every editor needs /pattern. The modern refinement — vim's incsearch, now everyone's default — is incremental search: the view jumps to the first match after every keystroke of the pattern, before you press Enter. The UX loop lives in your editor (a mini input loop reading into the query string, rendering each frame with the candidate match highlighted, Esc restoring the pre-search cursor — save it before you start!). The engine underneath is one pure function, and that's the graded part:

find the next match for `needle`, starting from the cursor,
in this direction, wrapping around the ends of the file

Design decisions worth making explicit, because each is a behavior users have 45 years of muscle memory about:

Strictly after. Searching forward from a cursor on a match must find the next one — otherwise pressing n (repeat search) pins you in place forever. So the scan starts one position after the cursor (one before, going backward).
Wraparound. Hitting the end of the file continues from the top (vi flashes "search hit BOTTOM, continuing at TOP"). The cursor position itself is the last candidate checked — so if the file contains exactly one match and you're standing on it, n finds it again (having gone all the way around), not "no match".
A match is a starting position. Matches don't span lines (needle "ab" never matches across "...a" / "b..." — true to vi, where patterns are line-oriented), and overlapping matches count: "aa" occurs twice in "aaa", at columns 0 and 1.

The workhorse inside is std::string::find(needle, pos) and its mirror rfind — but the interesting code is the scan order: a forward search from (row, col) must visit, in order: the rest of that row, the rows below, then (wrapping) the rows above, and finally the beginning of the starting row up to and including the cursor. Backward is the exact mirror. Get the boundary arithmetic right at the seams — last column of a row, the wrap point, the final partial row — and the tests below walk every seam.

std::optional<Pos> is again the honest return type: "no match" is a normal outcome (the user typed a needle that isn't there — the editor shows "pattern not found" and stays put), not an exception, not a sentinel Pos{-1,-1} that someone forgets to check.

Implement search(lines, needle, from, forward):

Returns the position of the first character of the nearest match strictly after from (forward) or strictly before it (backward), scanning with wraparound through the entire file; the match starting exactly at from, if any, is found last (after a full loop).
"After" and "before" order positions by (row, col), matches ordered by their starting position; on a backward scan the nearest match is the one with the greatest starting position less than from.
Empty needle → std::nullopt (vi treats bare / as "repeat last search"; with no history there's nothing to do). No match anywhere → std::nullopt.
from is a valid cursor position; matches may start at any column c with c + needle.size() <= line.size().

This is the function your editor calls on every keystroke of the incremental query (always from the saved pre-search cursor, so the candidate match doesn't run away as you type) and on every n/N (from the current cursor, direction flipped for N).

› Search with Wraparound