Blink's (Chromium) text layout engine works the following way.
1. Layout the entire paragraph of text as a single line.
2. If this doesn't fit into the available width, bisect to the nearest line-break opportunity which might fit.
3. Reshape the text up until this line-break opportunity.
4. If it fits great! If not goto 2.
This converges as it always steps backwards, and avoids the contradictory situations.
Harfbuzz also provides points along the section of text which is safe to reuse, so reshaping typically involes only a small portion of text at the end of the line, if any.
https://github.com/harfbuzz/harfbuzz/issues/224
This approach is different to how many text layout engines approach this problem e.g. by adding "one word at a time" to the line, and checking at each stage if it fits.
> This approach is different to how many text layout engines approach this problem e.g. by adding "one word at a time" to the line, and checking at each stage if it fits.
We found it was roughly on par performance wise for simple text (latin), and faster for more complex scripts (thai, hindi, etc). It also is more correct when there is kerning across spaces, hyphenation, etc.
For the word-by-word approach to be performant you need a cache for each word you encounter. The shape-by-paragraph approach we found was faster for cold-start (e.g. the first time you visit a webpage). But this is also more difficult to show in standard benchmarks as benchmarks typically reuse the same renderer process.
1. Layout the entire paragraph of text as a single line.
2. If this doesn't fit into the available width, bisect to the nearest line-break opportunity which might fit.
3. Reshape the text up until this line-break opportunity.
4. If it fits great! If not goto 2.
This converges as it always steps backwards, and avoids the contradictory situations.
Harfbuzz also provides points along the section of text which is safe to reuse, so reshaping typically involes only a small portion of text at the end of the line, if any. https://github.com/harfbuzz/harfbuzz/issues/224
This approach is different to how many text layout engines approach this problem e.g. by adding "one word at a time" to the line, and checking at each stage if it fits.