linebreak

linebreak

Optimal line breaking for Go — pure Go, no cgo, no dependencies.

Give it a sequence of boxes, glue and penalties and a line width; it returns the breakpoints that minimise the total cost of the paragraph.

Why not just fill lines greedily

A greedy breaker decides each line without looking ahead, so one tight line early forces a bad one later, and the ragged edge wanders. This one treats the paragraph as a whole: every legal breakpoint is a node, every candidate line is an edge weighted by how far its spaces had to stretch or shrink, and the answer is the path of least total cost. Hyphenation points, forced breaks and discouraged breaks all enter as penalties, so a caller controls the outcome without special cases.

The algorithm is Knuth and Plass, Breaking Paragraphs into Lines (1981) — the same one behind the paragraphs people find noticeably even.

Useful wherever text is laid out and the result is looked at: PDF generation, e-book rendering, terminal and console formatting, SVG text, a UI toolkit's text layout.

Use

import "github.com/go-typeset/linebreak"

items := []linebreak.Item{
    linebreak.Box(30),                  // a word, 30 units wide
    linebreak.Glue(10, 5, 3),           // a space: 10 wide, may stretch 5, shrink 3
    linebreak.Box(45),
    // End a paragraph the way TeX does (tex.web §16077-16084): an INFINITE penalty,
    // then the finishing glue, then the forced break. The infinite penalty is not
    // decoration — §16070 says the \parfillskip "is preceded by an infinite penalty,
    // so it will never be considered as a potential breakpoint". Leave it out and that
    // glue IS a legal breakpoint (a glue after a box), which offers one break TeX never
    // offers, right at the end. A trailing glue should be REPLACED by the penalty
    // rather than kept, since "spaces usually precede blank lines" (§16068).
    linebreak.Penalty(0, linebreak.InfPenalty, false),
    linebreak.Glue(0, 1e6, 0),
    linebreak.Penalty(0, -linebreak.InfPenalty, false), // forced break: end of paragraph
}

lines, ok := linebreak.KnuthPlass(items, 100 /*line width*/, 1 /*tolerance*/, 10 /*line penalty*/)
if !ok {
    // no set of breaks fits within the tolerance; retry with linebreak.MaxBadRatio
}
for _, l := range lines {
    // l.Start, l.End index into items; l.Ratio is the space adjustment
    // (>0 stretched, <0 shrunk, 0 exact).
}

Glyph(r, w, h, d) is a box that also carries its rune and vertical metrics, for callers that draw what they measure.

Units are yours. The algorithm never looks at what a width means — points, pixels, ems or terminal columns all work, as long as one paragraph is consistent.

A forced break is mandatory. A Penalty of −InfPenalty is not a strong preference: every active node is deactivated there (tex.web §16769), so no line spans it. The paragraph's last line ends at the last forced penalty in the list.

An overfull line's ratio is negative. Ratio below −1 means the line is longer than the measure by more than its shrink can absorb, and −Inf means it cannot shrink at all. The sign is the contract: r >= -1 is the test for "this line can be set", and an unshrinkable overfull line must fail it. An underfull line with nothing to stretch is MaxBadRatio, deliberately finite — TeX gives it b := inf_bad, which does not exceed inf_bad, so such a line is bad but still usable.

Params.FinalPass arms TeX's artificial_demerits (§16824-16831): at a breakpoint where nothing feasible was recorded and only one node is active, the break is taken at zero cost instead of the node being deactivated. That is what makes TeX prefer two hopeless short lines to one overfull line. ⛔ Set it only on a genuine final pass, after the earlier passes failed, and keep the tolerance as it was — raising the tolerance makes a hopeless line feasible at its full cost, which defeats the clause. A caller that arms it on every pass will see breaks TeX never takes.

Tests

go test ./... — 100% statement coverage, run on six 64-bit architectures (amd64, arm64, riscv64, loong64, ppc64le, s390x), three operating systems, and both wasm targets.

Licence

BSD-3-Clause.