linebreak

README

linebreak — go-typeset

Knuth–Plass optimal line breaking, in pure Go (no cgo, no dependencies.)

Given a horizontal list of boxes, glue and penalties, and a line width, it chooses the breakpoints that minimise total demerits — the algorithm TeX uses to break a paragraph, and the reason TeX's paragraphs look better than a greedy first-fit. It is the paragraph builder extracted from go-tex/engine, where it is used in anger.

Why you might want it

A greedy line breaker decides each line without looking ahead, so one tight line early forces a bad one later. Knuth–Plass looks at the paragraph as a whole: every legal breakpoint is a node, every line is an edge weighted by how far its glue had to stretch or shrink, and the chosen path is the one of least total cost. Hyphenation points, forced breaks and discouraged breaks all enter as penalties.

Useful wherever text is laid out and quality matters: PDF generation, e-book rendering, terminal formatting, an SVG typesetter, 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),                // interword space: 10, 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 /*width*/, 1 /*tolerance*/, 10 /*\linepenalty*/)
if !ok {
    // no set of breaks fits within the tolerance
}
for _, l := range lines {
    // l.Start, l.End index into items; l.Ratio is the glue 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.

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)

Constants

const InfPenalty = 10000.0

InfPenalty is TeX's "infinite" penalty (∞ = forbidden break, −∞ = forced).

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 analogue of TeX's inf_bad): 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 demerits (linePenalty is TeX's \linepenalty). It returns the chosen lines in order and ok=false if no sequence of feasible breaks exists within tolerance.