linebreak

README

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),
    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.

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.

Documentation

Index

• Constants
• type Item
  • func Box(w float64) Item
  • func Glue(w, stretch, shrink float64) Item
  • func Glyph(r rune, w, h, d float64) Item
  • func Penalty(w, p float64, flagged bool) Item
• type ItemKind
• type Line
  • func KnuthPlass(items []Item, lineWidth, tolerance, linePenalty float64) ([]Line, bool)
  • func KnuthPlassWith(items []Item, lineWidth float64, p Params) ([]Line, bool)
• type Params
  • func DefaultParams(tolerance, linePenalty float64) Params

Constants

const InfPenalty = 10000.0

InfPenalty is the "infinite" penalty: +InfPenalty forbids a break, −InfPenalty forces one (the end of a paragraph is a forced break).

const MaxBadRatio = 1e4

MaxBadRatio is the worst finite badness ratio the optimiser will consider: a line that is underfull with no stretch at all. Callers pass it as the tolerance for a last-resort pass that must return SOMETHING rather than fail. MaxBadRatio caps the adjustment ratio of a short line that has no stretch (the worst finite badness): the line is very bad but still finite, so an emergency pass with a large tolerance can accept it instead of collapsing the whole paragraph onto one line.

Types

type Item

type Item struct {
	Kind            ItemKind
	Width           float64
	Height, Depth   float64 // box only (glyph metrics)
	R               rune    // box only (the glyph, 0 if none)
	Stretch, Shrink float64 // glue only
	Penalty         float64 // penalty only
	Flagged         bool    // penalty only (e.g. a hyphen) — consecutive flags are penalised
}

Item is one element of a horizontal list.

func Box

func Box(w float64) Item

Box, Glue and Penalty are constructors.

func Glue

func Glue(w, stretch, shrink float64) Item

func Glyph

func Glyph(r rune, w, h, d float64) Item

Glyph is a box carrying a rune and its height/depth (used by the typesetter).

func Penalty

func Penalty(w, p float64, flagged bool) Item

type ItemKind

type ItemKind uint8

ItemKind classifies a horizontal-list item.

const (
	KBox     ItemKind = iota // a box of fixed width
	KGlue                    // stretchable/shrinkable space (a legal breakpoint after a box)
	KPenalty                 // a penalty (a legal breakpoint; ±InfPenalty = forbidden/forced)
)

type Line

type Line struct {
	Start, End int     // item index range [Start, End) actually set on the line
	Ratio      float64 // glue adjustment ratio r (−1 fully shrunk … +tolerance stretched)
}

Line describes one output line of a broken paragraph.

func KnuthPlass

func KnuthPlass(items []Item, lineWidth, tolerance, linePenalty float64) ([]Line, bool)

KnuthPlass breaks items into lines of the given width, minimising total cost (linePenalty is charged once per line, which discourages breaking a paragraph into many short ones). It returns the chosen lines in order and ok=false if no sequence of feasible breaks exists within tolerance.

func KnuthPlassWith

func KnuthPlassWith(items []Item, lineWidth float64, p Params) ([]Line, bool)

KnuthPlassWith is KnuthPlass with the costs stated explicitly, for a caller that threads a document's own \adjdemerits and friends.

type Params

type Params struct {
	Tolerance   float64 // \tolerance: the worst BADNESS a line may have (100·ratio³)
	LinePenalty float64 // \linepenalty: charged once per line, so fewer lines cost less
	AdjDemerits float64 // \adjdemerits: adjacent lines two fitness classes apart
	DoubleHyph  float64 // \doublehyphendemerits: two hyphenated lines in a row
	FinalHyph   float64 // \finalhyphendemerits: a hyphen on the last line but one
}

Params carries the costs TeX charges besides the line's own badness. The zero value is not useful; DefaultParams holds the values every LaTeX document runs with (latex.ltx:498-514).

func DefaultParams

func DefaultParams(tolerance, linePenalty float64) Params

DefaultParams are LaTeX's own settings (latex.ltx:498-514): \tolerance=200, \linepenalty=10, \adjdemerits=10000, \doublehyphendemerits=10000, \finalhyphendemerits=5000.