Line breaking

func Linebreak(n Node, settings *LinebreakSettings) (*VList, []*Breakpoint)

func NewLinebreakSettings() *LinebreakSettings

type LinebreakSettings struct {
	// LineEndGlue is put at the right end of every line, TeX's \rightskip.
	// Stretch of order fil or higher sets the lines ragged right, and
	// centered together with the same stretch in LineStartGlue. IndentRight
	// is added to its width. It must not be nil; the default is a glue of
	// zero width.
	LineEndGlue *Glue
	// LineStartGlue is put at the left end of every line, TeX's \leftskip.
	// Stretch of order fil or higher sets the lines ragged left. Indent is
	// added to its width. It must not be nil; the default is a glue of zero
	// width.
	LineStartGlue *Glue
	// DemeritsFitness is added to the demerits of a line whose fitness
	// class (tight, decent, loose or very loose) is more than one class
	// away from the line before, TeX's \adjdemerits. Default 10000.
	DemeritsFitness int
	// DoublehyphenDemerits is added when two lines in a row end at a
	// discretionary, TeX's \doublehyphendemerits. Default 10000.
	DoublehyphenDemerits int
	// FinalHyphenDemerits is added when the second to last line of a
	// paragraph ends at a discretionary, TeX's \finalhyphendemerits.
	// Default 5000.
	FinalHyphenDemerits int
	// EmergencyStretch is stretch the line breaker adds to every line it
	// measures in a last pass, TeX's \emergencystretch: a paragraph is
	// broken again with it only when it cannot be broken within Tolerance
	// without an emergency line. Packing a line does not know it, so a line
	// that needs it comes out loose. Under a Breaker it counts for every
	// line. Default 0.
	EmergencyStretch bag.ScaledPoint
	// FontExpansion is the fraction of its width by which a glyph may be
	// narrowed or widened, 0.02 for 2 percent (hz, microtype's expansion).
	// The line breaker counts it as stretch and shrink; packing a line uses
	// it only to narrow the glyphs of a line that is still too wide when
	// its glue has shrunk all it can. Default 0, off.
	FontExpansion float64
	// HSize is the width of every line, TeX's \hsize. Indent and IndentRight
	// are taken off it.
	HSize bag.ScaledPoint
	// Hyphenpenalty is added to a discretionary's own penalty when a line
	// breaks there, TeX's \hyphenpenalty. Default 50.
	Hyphenpenalty int
	// Indent is the left inset of the rows IndentRows selects. It moves their
	// content to the right and shortens them, as a paragraph indent or a
	// hanging indent does.
	Indent bag.ScaledPoint
	// IndentRows selects the rows Indent applies to: 0 all rows, a positive
	// n the first n rows, a negative n every row but the first n. That is
	// TeX's \hangafter with the sign turned around. IndentForRow returns
	// the inset of a row.
	IndentRows int
	// IndentRight is the mirror of Indent: it narrows a line from the right
	// without moving where the line starts. IndentRightRows selects the rows it
	// applies to with the same sign convention as IndentRows (positive: the
	// first n rows; negative: every row but the first n; 0: all rows).
	//
	// The two are separate because they are not the same operation. Indent
	// shifts the line's content to the right as well as shortening it, which is
	// what a paragraph indent means; IndentRight only takes width away from the
	// end, which is what is needed to lay text beside something on the right:
	// the line box still spans the full HSize, so alignment inside the narrowed
	// measure keeps working.
	IndentRight     bag.ScaledPoint
	IndentRightRows int
	// IndentSteps, when not empty, replaces Indent and IndentRows: the left
	// inset changes from row to row as the steps say, a staircase that can
	// follow the edge of something beside the paragraph, such as two floats
	// of different heights or the outline of an image. IndentRightSteps does
	// the same for IndentRight and IndentRightRows. The two sides are
	// independent, so steps on one side leave the plain inset of the other
	// as it is.
	IndentSteps      []IndentStep
	IndentRightSteps []IndentStep
	// LineHeight is the room a line takes up, its box and the glue below it
	// together: Linebreak pads each line to LineHeight with glue. Lines of
	// the same height are therefore LineHeight apart from baseline to
	// baseline. A line taller than LineHeight gets no glue. HalfLeading and
	// LineModel change how the room is made.
	LineHeight bag.ScaledPoint
	// LinePenalty is added to the badness of every line before the sum is
	// squared into the line's demerits, TeX's \linepenalty. It makes each
	// line cost something, also a perfect one, so of two breaks of the same
	// quality the one with fewer lines wins. Default 10.
	LinePenalty int
	// Tolerance is the largest adjustment ratio a line may have, the amount
	// its glue stretches or shrinks as a multiple of its stretchability or
	// shrinkability; a line never shrinks by more than 1. A break that needs
	// more is not feasible; if no break is, Linebreak still breaks and
	// leaves a line overfull. Unlike TeX's \tolerance it is a ratio, not a
	// badness, but it limits a line the same way, as badness grows with the
	// ratio: the default 4.0 is a badness of 6400, and TeX's 200 is a ratio
	// of about 1.26. 0 takes only lines that fit exactly.
	Tolerance float64
	// SqueezeOverfullBoxes lets the glue of a line that is still too wide
	// shrink past its shrinkability, so the line keeps to HSize with spaces
	// narrower than allowed. It has no effect with FontExpansion, which
	// narrows the glyphs instead. Default false.
	SqueezeOverfullBoxes bool
	// HangingPunctuationEnd lets punctuation at the end of a line, and the
	// hyphen of a hyphenated line, hang into the margin: it takes no width
	// there. Default false.
	HangingPunctuationEnd bool
	// OmitLastLeading leaves out the glue below the last line (with a
	// LineModel, its Leading there), so the paragraph ends at the last
	// line's depth. Default false.
	OmitLastLeading bool
	// HalfLeading distributes the leading (LineHeight minus the line's
	// natural Height+Depth) into the line box itself, half above and half
	// below (CSS 2.1 section 10.8.1), instead of emitting lineskip glue
	// after each line (the TeX-flavored default). Baseline-to-baseline
	// distances and the total paragraph height stay the same; only the
	// box edges and the first baseline (down by half the leading) move.
	// Lines taller than LineHeight keep their natural size. In this mode
	// OmitLastLeading has no meaning: half the leading sits in the last
	// line's depth by construction.
	HalfLeading bool
	// LineModel, when set, places each line in its line box and decides the
	// glue between lines, in place of HalfLeading and the lineskip glue
	// (see LineModel). Nil keeps the built-in behavior.
	LineModel LineModel
	// Breaker, when set, chooses where the paragraph breaks among its legal
	// breakpoints, in place of Knuth-Plass (see Breaker). Linebreak still
	// measures, packs and sets the lines. Nil keeps Knuth-Plass.
	Breaker Breaker
	// Font is the paragraph's own font, the one its root inline box has
	// (CSS Inline 3 text-box-edge). When it is set, Linebreak records on
	// each line how far its height reaches above the font's text-over edge,
	// its ContentAscent, as the line's LineTrimStart, and how far its depth
	// reaches below the text-under edge, its ContentDescent, as its
	// LineTrimEnd. Nil records nothing.
	Font *font.Font
	// TextDirection is the paragraph's base direction. The insets and the
	// edge glues are physical whatever it says; what it decides is which
	// side is the line end: where a forced break leaves its slack, and
	// where hanging punctuation protrudes. Every line and the paragraph
	// box carry it as TextDir.
	TextDirection TextDirection
	// TabStops are the positions a tab (a Glue of subtype GlueTab) advances
	// to, measured from the paragraph's start edge: the left edge of a left
	// to right paragraph, the right edge of a right to left one. A tab moves
	// to the first stop past the text before it on the line; after the last
	// stop it keeps its own width. Without stops tabs are ordinary glue.
	TabStops []TabStop
}

type IndentStep struct {
	Inset bag.ScaledPoint
	Rows  int
}

type Breakpoint struct {
	Position Node
	Pre      Node
	Line    int
	Fitness int
	Width   bag.ScaledPoint
	R        float64
	Demerits int
	// Emergency is set on a line that no feasible break could end, which
	// the line breaker sets anyway. Its R is past Tolerance, or below -1
	// for an overfull line.
	Emergency bool
}

type Breaker interface {
	// Breaks returns the indexes into p.Candidates at which the paragraph
	// breaks, in order, the last one being the paragraph's end. Linebreak
	// breaks at every forced candidate and at the last one whether or not
	// they are returned, and ignores an index out of range or out of order.
	Breaks(p *BreakProblem) []int
}

type BreakProblem struct {
	// Candidates are the legal breakpoints, in order.
	Candidates []Candidate
	// Settings are the paragraph's own settings, which Fit reads; a
	// Breaker must not change them during Breaks.
	Settings *LinebreakSettings
	// Fit measures a line from candidate from (-1 for the paragraph's
	// start) to candidate to, set as row row (0 for the first line), the
	// way Knuth-Plass measures it: with the width of a penalty or a
	// discretionary's pre-break text at its end, without the glue discarded
	// at its start, from a tab stop the line reaches, and with the row's
	// Indent and IndentRight. Fit is valid only during Breaks. It assumes
	// from < to; otherwise it returns a line of negative width, not an
	// error.
	Fit func(from, to, row int) LineFit
}

type Candidate struct {
	// Node is the node the paragraph breaks at: a Glue, Penalty, Disc or
	// HardBreak.
	Node Node
	// Penalty is the cost of breaking here as Knuth-Plass counts it: 0 at a
	// glue, the penalty's, a discretionary's plus the Hyphenpenalty, and
	// -10000 at a HardBreak. -10000 or less is a forced break.
	Penalty int
	// Flagged is set at a discretionary, a hyphenated break.
	Flagged bool
}

type LineFit struct {
	// Natural is the line's width with its glue unset, Measure the width it
	// is set to: HSize less the row's insets. Stretch and Shrink are its
	// finite stretch and shrink, with the font expansion and, for Stretch,
	// the EmergencyStretch; fil glue is not in them, see Ratio.
	Natural, Stretch, Shrink, Measure bag.ScaledPoint
	// Ratio is the adjustment ratio as Knuth-Plass computes it: 0 for a
	// line short of its measure that has fil glue (a ragged line), +Inf for
	// one that cannot reach its measure, negative for one that shrinks, less
	// than -1 for one too wide even shrunk.
	Ratio float64
	// Feasible is whether Knuth-Plass would take the line: Ratio from
	// -Tolerance (-1 at most) to Tolerance.
	Feasible bool
}

type greedy struct{}

func (greedy) Breaks(p *node.BreakProblem) []int {
	var breaks []int
	from, fits := -1, -1
	for i := 0; i < len(p.Candidates); i++ {
		f := p.Fit(from, i, len(breaks))
		switch {
		case f.Natural <= f.Measure && p.Candidates[i].Forced():
			breaks, from, fits = append(breaks, i), i, -1
		case f.Natural <= f.Measure:
			fits = i
		case fits >= 0:
			// End the line at the last break that fit, measure i again.
			breaks, from, fits = append(breaks, fits), fits, -1
			i--
		default:
			// Nothing fits: the line is overfull up to i.
			breaks, from = append(breaks, i), i
		}
	}
	return breaks
}

ls := node.NewLinebreakSettings()
ls.HSize = bag.MustSP("150pt")
ls.Breaker = greedy{}
vl, _ := node.Linebreak(hl, ls)

type LineModel interface {
	// LineBox returns the height above the baseline and the depth below it
	// of line, a line Linebreak has just packed to HSize. line.Height and
	// line.Depth are its natural extent; each glyph on it carries its font
	// (with the size and the face's vertical metrics) and its LineShift.
	// A model whose lines end elsewhere than LinebreakSettings.Font's text
	// edges may record the line's trims as its LineTrimStart and
	// LineTrimEnd attributes; Linebreak keeps them, and takes one off again
	// when it is 0.
	LineBox(line *HList, settings *LinebreakSettings) (height, depth bag.ScaledPoint)
	// Leading returns the glue Linebreak puts next to line, whose line box
	// is already set: above each line but the first, and below the last
	// line unless OmitLastLeading is set. A nil glue puts nothing there.
	Leading(line *HList, settings *LinebreakSettings) *Glue
}

type exactly struct {
	height, depth bag.ScaledPoint
}

func (m exactly) LineBox(line *node.HList, settings *node.LinebreakSettings) (bag.ScaledPoint, bag.ScaledPoint) {
	return m.height, m.depth
}

func (m exactly) Leading(line *node.HList, settings *node.LinebreakSettings) *node.Glue {
	return nil
}

ls := node.NewLinebreakSettings()
ls.HSize = bag.MustSP("150pt")
ls.LineModel = exactly{height: bag.MustSP("10pt"), depth: bag.MustSP("4pt")}
vl, _ := node.Linebreak(hl, ls)

type BackgroundAreaModel interface {
	// BackgroundArea returns the height above and the depth below the
	// baseline of the band an inline background in font f covers.
	BackgroundArea(f *font.Font) (height, depth bag.ScaledPoint)
}