(This is a response to https://github.com/google/xi-editor/blob/master/doc/rope_science/rope_science_11.md that didn't fit in a tweet.)
CodeMirror uses a largely similar approach, with a somewhat different framing.
Firstly, it stores the mode (highlighter) state directly in the document data structure (which I probably wouldn't do again if I were to redesign this), not in a separate cache. Each line can have an optional 'highlight state after this line' field. During highlighting, a cached state is left every N lines.
The frontier is simply the line number up to which point highlighting has happened. When you edit above the frontier, it it moved back to the line before the change.
Highlighting never proceeds past the end of the viewport. So startup is cheap (only highlight the first screenful), and in the 99% case of changes happening inside the viewport, re-highlighting complexity is bounded by the size of the viewport, since only the area between the change and the end of the viewport needs to be proces