← Algorithms

Breaking text into lines

Greedy line breaking, why not the optimal kind, and measuring text without a font.

In the code: foundation/geometry.py

Every label in every diagram goes through this, and it starts from an embarrassing position: there is no font engine.

Measuring text you cannot measure

To size a box around a label you must know how wide the label is, which properly means asking a font for the advance width of each glyph, applying kerning, and handling ligatures. Sauvignon is stdlib-only and emits SVG for someone else's renderer to draw, so it has none of that.

So it approximates. Glyph advance is taken as a fixed fraction of the font size — about 0.58 for common sans-serif faces — and a string's width is its length times that. It is wrong for every individual string, and close enough on average that boxes look right.

The honest consequence: Illlli and WWWWWW measure the same, so a label of all-narrow or all-wide characters gets a box that is too roomy or slightly tight. The fix is a real metrics table per font, which is a bounded amount of work and a lot of data. The approximation buys the whole library being dependency-free.

<diagram padding="16">
  <row gap="14" align="start">
    <contains padding="10">
      <text width="150">A label long enough that it has to wrap onto several lines</text>
    </contains>
    <contains padding="10">
      <text width="150">Il lililli illi lilli illil lilil illi lillil ill lilli il</text>
    </contains>
  </row>
</diagram>

Both boxes are the same width and hold exactly the same number of characters — fifty-eight each. Character count is the only input the model has, so it breaks both into four lines and reserves both the same height. The second is visibly emptier: every one of its glyphs is narrower than the 0.58 average, and the error compounds across the whole string. That is the approximation showing its edge.

(The text is inside a <contains> because a shape's own label does not wrap — only the <text> mark does. That asymmetry is itself a limitation worth knowing about: a long label on a <rect> runs past its box rather than breaking.)

Greedy is the right kind of wrong

Given widths, breaking into lines is the classic problem. Fill the current line with words until the next one would not fit, then start a new line. It is greedy (or first-fit): each break is decided locally, in one pass, without looking ahead.

The famous alternative is Knuth and Plass's total-fit algorithm, from TeX: score each possible set of breakpoints by total "badness" — how stretched or squeezed the lines are — and use dynamic programming to find the arrangement minimising it over the whole paragraph. It produces noticeably better-looking text, because a slightly worse early break can save a terrible later one.

Sauvignon uses greedy, deliberately:

• diagram labels are short. Knuth-Plass earns its keep over paragraphs; over three words there is usually only one sensible arrangement anyway;
• it is what CSS does, so a diagram wraps the way the page around it does;
• it is a few lines, and the difference would be invisible at this scale.

This is the same trade as everywhere else in the engine: the good-enough algorithm, chosen knowingly, with the better one named so the choice can be revisited.

The two intrinsic widths fall out of it

Wrapping is what gives the sizing pass its two numbers (see measure, then place):

• max-content is the width with no breaks at all — the whole string on one line;
• min-content is the width when you break at every opportunity, which is the width of the single longest word.

Neither needs the wrapping algorithm to run; both are computed directly. But they bound it: no useful line is wider than max-content, and a box narrower than min-content cannot hold the text without breaking a word.

When a word is wider than the line

Which happens. A URL, an identifier, a German compound. The word cannot fit, and greedy has nothing to give.

The last resort is to break the word itself, at character boundaries, into chunks that do fit — CSS calls this overflow-wrap: break-word. It is deliberately a separate pass that runs before the normal wrapping, chopping over-long words into pieces, so the main algorithm never has to cope with an unbreakable item. Otherwise every line-breaking loop needs an "and what if this single word doesn't fit" branch, which is how such code becomes unreadable.

Proper hyphenation — breaking at syllable boundaries with a dictionary or Liang's pattern algorithm, again from TeX — would be nicer and is a great deal more machinery for a diagram label.

Further reading. Knuth & Plass, Breaking Paragraphs into Lines (1981), which is worth reading even if you never implement it; Liang's thesis on hyphenation patterns (1983) for the other half of TeX's typesetting.