88f5a00e389b
breaker.rs
//! Line breaking: the paragraph composer (Knuth–Plass total fit), the single-line composer
//! (greedy first fit) and balanced ragged lines. All work on a paragraph's glyphs and a per-line
//! measure function.
//!
//! Justification uses *prioritised* elastic material (plan: typography §5.2): word spaces first,
//! then letter spacing (every glyph gets elastic width from the paragraph's letter-spacing range),
//! then glyph scaling. The adjustment ratio charges letter and glyph adjustments extra
//! ([`TIER_COST`]), so the composer prefers word-space changes, then hyphenation, then letter
//! spacing, then glyph scaling.
use crate::shape::{Glyph, SOFT_HYPHEN};
/// One line chosen by a breaker: glyphs `start..end` are visible; `next` is where the next line starts.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct Break {
pub start: usize,
pub end: usize,
pub next: usize,
/// Broken at a hyphenation point (a hyphen glyph must be added).
pub hyphen: bool,
/// Ended by a forced break (paragraph end, forced line break, column/frame/page break).
pub forced: bool,
}
/// Spacing parameters (from the paragraph's Justification and Hyphenation settings), as fractions.
#[derive(Clone, Copy, Debug)]
pub struct Spacing {
pub justify: bool,
pub word_min: f64,
pub word_desired: f64,
pub word_max: f64,
/// Letter spacing, as fractions of the space width added between glyphs.
pub letter_min: f64,
pub letter_desired: f64,
pub letter_max: f64,
/// Horizontal glyph scaling (1 = 100%).
pub glyph_min: f64,
pub glyph_desired: f64,
pub glyph_max: f64,
/// Penalty for a hyphenated break (0 = free, larger = fewer hyphens).
pub hyphen_penalty: f64,
/// Maximum consecutive hyphenated lines (0 = unlimited) — a hard constraint.
pub hyphen_limit: u32,
/// Ragged-right stretchability (points) for unjustified paragraphs.
pub ragged_stretch: f64,
/// Hyphenation zone (points, unjustified text only): a word is not hyphenated when breaking
/// before it would leave less than this much space at the end of the line.
pub hyph_zone: f64,
/// Optical margin alignment: punctuation hangs outside the measure (counted as extra width).
pub optical: bool,
/// The type size the hang amounts are set for (Story ▸ Optical Margin Alignment's size);
/// `None`: each glyph's own size, so the hang is [`hang`]'s proportion of its advance.
pub optical_size: Option<f64>,
/// Korean text breaks between syllables instead of at spaces.
pub korean_char_breaks: bool,
/// JIS X 4051 禁則処理 type: 0: minimum adjustment (調整量優先); 1: push in first (追い込み
/// 優先, the default); 2: push out first (追い出し優先); 3: push out only (追い出しのみ).
pub kinsoku_priority: u8,
/// The paragraph has CJK text, so the 禁則 priority biases its breaks. A Latin paragraph's
/// breaks are left alone by the (default) push-in-first policy.
pub kinsoku_cjk: bool,
}
impl Default for Spacing {
fn default() -> Self {
Spacing {
justify: false,
word_min: 0.8,
word_desired: 1.0,
word_max: 1.33,
letter_min: 0.0,
letter_desired: 0.0,
letter_max: 0.0,
glyph_min: 1.0,
glyph_desired: 1.0,
glyph_max: 1.0,
hyphen_penalty: 275.0,
hyphen_limit: 3,
ragged_stretch: 24.0,
hyph_zone: 0.0,
optical: false,
optical_size: None,
korean_char_breaks: false,
kinsoku_priority: 1,
kinsoku_cjk: false,
}
}
}
impl Spacing {
/// Push out only: the 追い込み (compression that would pull the next character in) is
/// unavailable, so every line end is pushed out (and no line is compressed at its end).
pub(crate) fn push_out_only(&self) -> bool {
self.kinsoku_cjk && self.kinsoku_priority == 3
}
/// Per-tier (word, letter, glyph) stretch and shrink of glyph `g` as a box.
fn box_elastic(&self, g: &Glyph) -> ([f64; 3], [f64; 3]) {
if g.locked_advance {
return ([0.0; 3], [0.0; 3]);
}
let moji_stretch = if self.justify { g.moji.stretch } else { 0.0 };
let moji_shrink = if self.push_out_only() { 0.0 } else { g.moji.shrink };
if !self.justify {
return ([0.0; 3], [moji_shrink, 0.0, 0.0]);
}
// A space that is no break opportunity (No Break, U+00A0) is a box with word-space elasticity.
if g.is_justify_space() {
let (st, sh) = self.space_elastic(g);
return ([moji_stretch + st, 0.0, 0.0], [moji_shrink + sh, 0.0, 0.0]);
}
let natural = g.adv / self.glyph_desired.max(0.01);
(
[moji_stretch, g.space * (self.letter_max - self.letter_desired).max(0.0), natural * (self.glyph_max - self.glyph_desired).max(0.0)],
[moji_shrink, g.space * (self.letter_desired - self.letter_min).max(0.0), natural * (self.glyph_desired - self.glyph_min).max(0.0)],
)
}
/// Word-space stretch and shrink of space glyph `g` (see [`Glyph::is_word_space`]); none
/// inside a jidori run, whose width is fitted.
fn space_elastic(&self, g: &Glyph) -> (f64, f64) {
if !g.is_word_space() || g.locked_advance {
return (0.0, 0.0);
}
(g.space * (self.word_max - self.word_desired).max(0.0), g.space * (self.word_desired - self.word_min).max(0.0))
}
/// The unit in which stretch past the maximum word spacing is rated (see [`tiered_ratio`]): the
/// word space's own stretch, but at least [`OVERFLOW_STRETCH`] of its width, so a tight
/// spacing range doesn't make a loose line with several word spaces look worse than a line
/// letter-spaced across the measure.
fn space_overflow(&self, g: &Glyph) -> f64 {
if !g.is_word_space() {
return 0.0;
}
g.space * (self.word_max - self.word_desired).max(OVERFLOW_STRETCH)
}
}
/// Minimum stretch of a word space, as a fraction of its width, for rating lines that stretch
/// past the maximum word spacing (the default range's 133% − 100%).
const OVERFLOW_STRETCH: f64 = 0.33;
/// Relative cost of using each tier of elastic material (word, letter, glyph).
pub const TIER_COST: [f64; 3] = [1.0, 0.75, 1.0];
/// Effective adjustment ratio for `d` points of stretch (`d > 0`) or shrink (`d < 0`), consuming
/// the tiers in priority order. Returns `(r, feasible)`; shrinking beyond all tiers is infeasible.
/// Stretch past every tier goes into the word spaces and is rated in units of `over` (their
/// overflow stretch, see [`Spacing::space_overflow`]); a line without word spaces rates it
/// against its letter and glyph stretch.
pub fn tiered_ratio(d: f64, y: [f64; 3], z: [f64; 3], over: f64) -> (f64, bool) {
const EPS: f64 = 1e-9;
if d.abs() < EPS {
return (0.0, true);
}
let (mut rem, cap) = if d > 0.0 { (d, y) } else { (-d, z) };
let mut r = 0.0;
for t in 0..3 {
if cap[t] > EPS && rem > EPS {
let take = rem.min(cap[t]);
r += TIER_COST[t] * take / cap[t];
rem -= take;
}
}
if d < 0.0 {
return (-r, rem <= 1e-6);
}
if rem > 1e-6 {
// Beyond every maximum: word spaces grow without bound (an H&J violation).
let unit = if over > EPS { over } else { cap.iter().sum::<f64>() };
r = if unit > EPS { r + rem / unit } else { INF };
}
(r, true)
}
#[derive(Clone, Copy, Debug, PartialEq)]
enum Kind {
Box,
Glue,
Penalty,
}
#[derive(Clone, Copy, Debug)]
struct Item {
kind: Kind,
w: f64,
st: [f64; 3],
sh: [f64; 3],
/// Penalty value (penalties only).
p: f64,
flagged: bool,
/// An automatic/discretionary hyphenation point (subject to the hyphenation zone).
auto: bool,
/// Breaks: optical hang of the glyph ending the line. Boxes: hang of the glyph starting one.
hang: f64,
edge_elastic: [f64; 2],
start_elastic: [f64; 2],
/// Auto hyphenation points: index of the break opportunity before the word (or `NONE`).
zone_from: usize,
/// An emergency break inside a word wider than the measure.
emergency: bool,
/// Glue: stretch past the maximum word spacing ([`Spacing::space_overflow`]).
over: f64,
}
const NONE: usize = usize::MAX;
impl Item {
fn boxed(w: f64, st: [f64; 3], sh: [f64; 3]) -> Item {
Item {
kind: Kind::Box,
w,
st,
sh,
p: 0.0,
flagged: false,
auto: false,
hang: 0.0,
edge_elastic: [0.0; 2],
start_elastic: [0.0; 2],
zone_from: NONE,
emergency: false,
over: 0.0,
}
}
fn glue(w: f64, st: f64, sh: f64) -> Item {
Item {
kind: Kind::Glue,
w,
st: [st, 0.0, 0.0],
sh: [sh, 0.0, 0.0],
p: 0.0,
flagged: false,
auto: false,
hang: 0.0,
edge_elastic: [0.0; 2],
start_elastic: [0.0; 2],
zone_from: NONE,
emergency: false,
over: 0.0,
}
}
fn penalty(w: f64, p: f64, flagged: bool) -> Item {
Item {
kind: Kind::Penalty,
w,
st: [0.0; 3],
sh: [0.0; 3],
p,
flagged,
auto: false,
hang: 0.0,
edge_elastic: [0.0; 2],
start_elastic: [0.0; 2],
zone_from: NONE,
emergency: false,
over: 0.0,
}
}
}
const INF: f64 = 10000.0;
/// A line whose natural width exceeds its measure by no more than this (points) still fits: frame
/// widths and glyph advances are rounded, so a line that exactly fills the measure can come out a
/// hair too wide.
const FIT_EPS: f64 = 0.01;
/// Penalty for an emergency break inside a word wider than the measure: high, so a paragraph
/// takes no more of them than it must, but below [`INF`] so they are legal.
const EMERGENCY_PENALTY: f64 = 5000.0;
/// Does the glyph force a line end after it?
/// A line may break between `a` and `b` in CJK text (any break next to an ideograph, kana or
/// hangul), except where kinsoku forbids it: no line starts with closing punctuation, small
/// kana or the prolonged sound mark, and none ends with opening brackets.
pub fn cjk_break_between(a: char, b: char) -> bool {
(is_cjk(a) || is_cjk(b)) && kinsoku_allows(a, b)
}
fn is_cjk(c: char) -> bool {
crate::upright_in_vertical(c) || matches!(c as u32, 0x3000..=0x303F)
}
fn kinsoku_allows(a: char, b: char) -> bool {
const NO_START: &str = "、。,.・:;?!ー)」』】〕〉》}]〙〗ぁぃぅぇぉっゃゅょゎァィゥェォッャュョヮヵヶ々〻ゝゞヽヾ!),.:;?]}";
const NO_END: &str = "(「『【〔〈《{[〘〖([{";
!NO_START.contains(b) && !NO_END.contains(a)
}
/// Hangul: Jamo, compatibility Jamo, the syllables, and Jamo Extended-A/B. Shared with the
/// paragraph's CJK gate so the two classifications cannot drift apart.
pub(crate) fn is_hangul(c: char) -> bool {
matches!(c as u32, 0x1100..=0x11FF | 0x3130..=0x318F | 0xA960..=0xA97F | 0xAC00..=0xD7FF)
}
/// Hangul, and Han ideographs (hanja) in Korean text: Korean is set word by word (KLREQ), so
/// these letters break like Western ones, at spaces.
fn korean_letter(g: &Glyph) -> bool {
let c = g.ch;
let han = matches!(c as u32, 0x3400..=0x4DBF | 0x4E00..=0x9FFF | 0xF900..=0xFAFF | 0x20000..=0x3FFFF);
is_hangul(c) || (han && g.lang.is_some_and(|t| designcraft_doc::language_subtag(t) == "ko"))
}
/// Is the place between glyphs `a` and `b` one where CJK text may break (next to an ideograph, kana
/// or hangul)? Korean letters take no breaks between characters unless the paragraph asks for
/// character-based breaking.
pub(crate) fn cjk_pair(a: &Glyph, b: &Glyph, korean_char_breaks: bool) -> bool {
let cjk = |g: &Glyph| is_cjk(g.ch) && (korean_char_breaks || !korean_letter(g));
cjk(a) || cjk(b)
}
/// [`cjk_break_between`] for glyphs `a` and `b` (see [`cjk_pair`]).
fn cjk_break(a: &Glyph, b: &Glyph, sp: &Spacing) -> bool {
cjk_pair(a, b, sp.korean_char_breaks) && kinsoku_allows(a.ch, b.ch)
}
pub fn is_forced(c: char) -> bool {
use designcraft_doc::story::{FORCED_LINE_BREAK, is_break_char};
c == FORCED_LINE_BREAK || is_break_char(c)
}
/// Optical margin protrusion of `c` as fractions of its advance: (left edge, right edge).
pub fn hang(c: char) -> (f64, f64) {
match c {
'.' | ',' => (0.0, 1.0),
'-' | '\u{2010}' | '\u{2011}' | '\u{AD}' => (0.75, 0.75),
'\'' | '"' | '‘' | '’' | '“' | '”' | '‚' | '„' | '‹' | '›' | '«' | '»' => (1.0, 1.0),
'\u{2013}' | '\u{2014}' => (0.5, 0.5),
':' | ';' => (0.0, 0.5),
'!' | '?' => (0.0, 0.2),
'*' => (0.3, 0.3),
'(' | '[' | '{' => (0.1, 0.0),
')' | ']' | '}' => (0.0, 0.1),
'A' | 'V' | 'W' | 'Y' | 'v' | 'w' | 'y' => (0.05, 0.05),
'T' => (0.05, 0.05),
'O' | 'C' | 'G' | 'Q' | 'o' | 'c' => (0.03, 0.03),
_ => (0.0, 0.0),
}
}
/// How much more than [`hang`]'s proportions `g` hangs: the hang is set for
/// [`Spacing::optical_size`] and grows with it, relative to the glyph's own size.
pub(crate) fn optical_scale(g: &Glyph, sp: &Spacing) -> f64 {
match sp.optical_size {
Some(s) if s.is_finite() && g.size.is_finite() && g.size > 0.0 => s / g.size,
_ => 1.0,
}
}
/// Optical hang of `g` at the start of a line (0 without optical margin alignment).
pub(crate) fn hang_left(g: &Glyph, sp: &Spacing) -> f64 {
if sp.optical { hang(g.ch).0 * g.adv * optical_scale(g, sp) } else { 0.0 }
}
/// Optical hang of `g` at the end of a line (0 without optical margin alignment).
pub(crate) fn hang_right(g: &Glyph, sp: &Spacing) -> f64 {
if sp.optical { hang(g.ch).1 * g.adv * optical_scale(g, sp) } else { 0.0 }
}
fn right_hang(g: &Glyph, sp: &Spacing) -> f64 {
g.cjk_hang.max(hang_right(g, sp)) - g.moji.end
}
/// The part of a hyphen after `g` (of width `hw`) that hangs past the line's end.
fn hyphen_hang(g: &Glyph, hw: f64, sp: &Spacing) -> f64 {
if sp.optical { hw * hang('-').1 * optical_scale(g, sp) } else { 0.0 }
}
/// Advance of the hyphen glyph that would follow `g` (cached per face).
fn hyphen_width(g: &Glyph, cache: &mut Vec<(u32, f64)>) -> f64 {
let id = g.face.id();
let units = match cache.iter().find(|c| c.0 == id) {
Some(c) => c.1,
None => {
let gid = designcraft_fonts::first_glyph(&g.face, &['-', '\u{2010}']);
let u = g.face.advance(gid);
cache.push((id, u));
u
}
};
units * g.sx
}
/// Push a break inside a word. Ragged text gets the line-end stretch around it
/// (`penalty(∞) glue(0, s) penalty glue(0, −s)`), so hyphenated ragged lines are measured like
/// lines broken at spaces.
fn push_inword(it: &mut Vec<Item>, ig: &mut Vec<usize>, p: Item, g: usize, sp: &Spacing) {
if sp.justify {
it.push(p);
ig.push(g);
return;
}
it.push(Item::penalty(0.0, INF, false));
it.push(Item::glue(0.0, sp.ragged_stretch, 0.0));
it.push(p);
it.push(Item::glue(0.0, -sp.ragged_stretch, 0.0));
ig.extend([g; 4]);
}
/// Build Knuth items. `item_glyph[k]` = glyph index of item k (penalties: the glyph *before* which the break happens).
/// `emergency_after[i]` allows an emergency break after glyph `i` (see [`overlong_words`]).
fn items(glyphs: &[Glyph], hyph_after: &[bool], emergency_after: &[bool], sp: &Spacing) -> (Vec<Item>, Vec<usize>) {
let mut it: Vec<Item> = Vec::with_capacity(glyphs.len() * 2 + 2);
let mut ig = Vec::with_capacity(glyphs.len() * 2 + 2);
let n = glyphs.len();
let mut hy_cache = Vec::new();
let mut last_space = NONE;
// Spaces before the paragraph end or a forced break hang: they take no room on the line (as
// in InDesign, where "2 VOOR " fits a frame as wide as "2 VOOR").
let mut hangs = vec![false; n];
for i in (0..n).rev() {
hangs[i] = glyphs[i].is_space() && glyphs.get(i + 1).is_none_or(|nx| hangs[i + 1] || is_forced(nx.ch));
}
// The last glyph that isn't a soft hyphen, kept as the loop goes (a run of soft hyphens
// searched back over all of them for every one).
let mut last_plain: Option<&Glyph> = None;
for (i, g) in glyphs.iter().enumerate() {
// Set before the soft-hyphen case below reads it; a soft hyphen leaves it as it was.
if g.ch != SOFT_HYPHEN {
last_plain = Some(g);
}
let prev_hang = if i > 0 { right_hang(&glyphs[i - 1], sp) } else { 0.0 };
if hangs[i] {
continue;
}
if is_forced(g.ch) {
it.push(Item::glue(0.0, INF, 0.0));
ig.push(i);
let mut p = Item::penalty(0.0, -INF, false);
p.hang = prev_hang;
if let Some(prev) = i.checked_sub(1).and_then(|j| glyphs.get(j)) {
p.edge_elastic = crate::mojikumi::end_elastic(prev, sp.justify, !sp.push_out_only());
}
it.push(p);
ig.push(i + 1);
last_space = NONE;
continue;
}
if g.is_space() && !g.no_break && g.break_after != Some(false) {
let w = g.adv;
if sp.justify {
let (st, sh) = sp.space_elastic(g);
let mut gl = Item::glue(w, st, sh);
gl.hang = prev_hang;
if let Some(prev) = i.checked_sub(1).and_then(|j| glyphs.get(j)) {
gl.edge_elastic = crate::mojikumi::end_elastic(prev, sp.justify, !sp.push_out_only());
}
gl.over = sp.space_overflow(g);
last_space = it.len();
it.push(gl);
ig.push(i);
} else {
// Ragged right (Knuth): glue(0, s, 0) penalty(0) glue(w, -s, 0).
it.push(Item::glue(0.0, sp.ragged_stretch, 0.0));
ig.push(i);
let mut p = Item::penalty(0.0, 0.0, false);
p.hang = prev_hang;
if let Some(prev) = i.checked_sub(1).and_then(|j| glyphs.get(j)) {
p.edge_elastic = crate::mojikumi::end_elastic(prev, sp.justify, !sp.push_out_only());
}
last_space = it.len();
it.push(p);
ig.push(i);
it.push(Item::glue(w, -sp.ragged_stretch, 0.0));
ig.push(i);
}
continue;
}
if g.ch == SOFT_HYPHEN {
let hw = last_plain.map_or(g.size * 0.33, |p| hyphen_width(p, &mut hy_cache));
let mut p = Item::penalty(hw, sp.hyphen_penalty, true);
p.auto = true;
p.zone_from = last_space;
p.hang = hyphen_hang(g, hw, sp);
push_inword(&mut it, &mut ig, p, i + 1, sp);
continue;
}
let (st, sh) = sp.box_elastic(g);
let mut bx = Item::boxed(g.adv, st, sh);
bx.hang = hang_left(g, sp) - g.moji.start;
bx.start_elastic = crate::mojikumi::start_elastic(g, sp.justify, !sp.push_out_only());
it.push(bx);
ig.push(i);
let next_is_space = glyphs.get(i + 1).is_none_or(|n| n.is_space());
if i + 1 < n && !next_is_space && !g.no_break && g.break_after != Some(false) {
if matches!(g.ch, '-' | '\u{2010}') {
let mut p = Item::penalty(0.0, 50.0, true);
p.hang = right_hang(g, sp);
p.edge_elastic = crate::mojikumi::end_elastic(g, sp.justify, !sp.push_out_only());
push_inword(&mut it, &mut ig, p, i + 1, sp);
} else if matches!(g.ch, '\u{2013}' | '\u{2014}' | '/') || g.break_after.unwrap_or_else(|| cjk_break(g, &glyphs[i + 1], sp)) {
let mut p = Item::penalty(0.0, 0.0, false);
p.hang = right_hang(g, sp);
p.edge_elastic = crate::mojikumi::end_elastic(g, sp.justify, !sp.push_out_only());
push_inword(&mut it, &mut ig, p, i + 1, sp);
} else if hyph_after[i] {
let hw = hyphen_width(g, &mut hy_cache);
let mut p = Item::penalty(hw, sp.hyphen_penalty, true);
p.auto = true;
p.zone_from = last_space;
p.hang = hyphen_hang(g, hw, sp);
push_inword(&mut it, &mut ig, p, i + 1, sp);
} else if emergency_after.get(i) == Some(&true) {
let mut p = Item::penalty(0.0, EMERGENCY_PENALTY, false);
p.emergency = true;
push_inword(&mut it, &mut ig, p, i + 1, sp);
}
}
}
// Paragraph end: fill glue + forced break.
it.push(Item::glue(0.0, INF, 0.0));
ig.push(n);
let mut p = Item::penalty(0.0, -INF, false);
p.hang = if n > 0 { right_hang(&glyphs[n - 1], sp) } else { 0.0 };
if let Some(g) = glyphs.last() {
p.edge_elastic = crate::mojikumi::end_elastic(g, sp.justify, !sp.push_out_only());
}
it.push(p);
ig.push(n);
(it, ig)
}
#[derive(Clone, Copy, Debug)]
struct Node {
pos: usize,
line: usize,
fitness: u8,
tw: f64,
ty: [f64; 3],
tz: [f64; 3],
to: f64,
demerits: f64,
prev: Option<usize>,
hyphens: u32,
flagged: bool,
}
/// Knuth–Plass total-fit line breaking. `width(line)` gives each line's measure.
pub fn knuth_plass(glyphs: &[Glyph], hyph_after: &[bool], sp: &Spacing, width: &dyn Fn(usize) -> f64) -> Vec<Break> {
if glyphs.is_empty() {
return vec![Break { start: 0, end: 0, next: 0, hyphen: false, forced: true }];
}
let (mut items, mut ig) = items(glyphs, hyph_after, &[], sp);
// A word gets emergency breaks only when no line could hold it: beside a wrap object some
// lines are slivers much narrower than the measure, and a word that fits a full line goes
// there instead of being split.
let widest = (0..=glyphs.len().min(64)).map(width).fold(1.0, f64::max);
if let Some(emergency_after) = overlong_words(&items, &ig, glyphs, widest) {
(items, ig) = self::items(glyphs, hyph_after, &emergency_after, sp);
}
for tolerance in [2.5, 12.0, f64::INFINITY] {
if let Some(b) =
kp_pass(PassInput { items: &items, item_glyphs: &ig, glyphs, spacing: sp, width, tolerance, emergency: tolerance.is_infinite() })
{
return b;
}
}
greedy(glyphs, hyph_after, sp, width, &|_, _, _| 0.0)
}
/// Width of the first word of `glyphs` after any leading spaces, fully shrunk (the boxes up to
/// the first break opportunity, emergency breaks aside, and the hyphen a break there adds).
pub fn first_word_width(glyphs: &[Glyph], hyph_after: &[bool], sp: &Spacing) -> f64 {
// A word this long is wider than any line; the rest of the paragraph doesn't matter.
let n = glyphs.len().min(256);
let (items, _) = items(glyphs.get(..n).unwrap_or(glyphs), hyph_after.get(..n).unwrap_or(hyph_after), &[], sp);
let mut w = 0.0;
let mut started = false;
for it in &items {
match it.kind {
Kind::Box => {
started = true;
w += it.w - it.sh.iter().sum::<f64>();
}
Kind::Penalty if it.p >= INF => {}
Kind::Penalty if started => return w + it.w,
Kind::Glue if started => return w,
Kind::Glue | Kind::Penalty => {}
}
}
w
}
/// Glyphs after which a word wider than `measure` may take an emergency break, or `None` when every
/// word fits. A word is a run of boxes between two break opportunities (so a word with hyphenation
/// points only gets emergency breaks where a part between them is still too wide), measured at
/// its narrowest (fully shrunk) width. Emergency breaks respect no-break text and kinsoku.
fn overlong_words(items: &[Item], ig: &[usize], glyphs: &[Glyph], measure: f64) -> Option<Vec<bool>> {
let mut out: Option<Vec<bool>> = None;
let mut seg: Option<(usize, usize)> = None;
let mut w = 0.0;
for (k, it) in items.iter().enumerate() {
match it.kind {
Kind::Box => {
let g = ig.get(k).copied().unwrap_or(0);
seg = Some(seg.map_or((g, g), |(a, _)| (a, g)));
w += it.w - it.sh.iter().sum::<f64>();
}
Kind::Penalty if it.p >= INF => {}
Kind::Glue | Kind::Penalty => {
if let Some((a, b)) = seg.take()
&& w > measure + FIT_EPS
{
let marks = out.get_or_insert_with(|| vec![false; glyphs.len()]);
for i in a..b {
let (Some(g), Some(next)) = (glyphs.get(i), glyphs.get(i + 1)) else { continue };
// Glyphs of one source character (an automatic page number's digits, a
// multi-glyph cluster) stay together, as InDesign keeps them.
let one_char = next.byte == g.byte && (next.len == 0 || next.len == g.len);
let ok = !g.no_break
&& !one_char
&& g.break_after != Some(false)
&& next.ch != SOFT_HYPHEN
&& !is_forced(next.ch)
&& kinsoku_allows(g.ch, next.ch);
if let Some(m) = marks.get_mut(i) {
*m = ok;
}
}
}
w = 0.0;
}
}
}
out
}
/// Upper bound on the hyphen-count states tracked per breakpoint.
const MAX_HYPHEN_STATES: usize = 8;
struct PassInput<'a> {
items: &'a [Item],
item_glyphs: &'a [usize],
glyphs: &'a [Glyph],
spacing: &'a Spacing,
width: &'a dyn Fn(usize) -> f64,
tolerance: f64,
emergency: bool,
}
/// Enforce consecutive-hyphen limits and the unjustified hyphenation zone.
fn hyphen_allowed(it: Item, n: Node, sp: &Spacing, widths: &[f64], items: &[Item], target: f64) -> bool {
let limit = sp.hyphen_limit as usize;
if limit > 0 && n.hyphens as usize >= limit {
return false;
}
if it.auto && !sp.justify && sp.hyph_zone > 0.0 && it.zone_from != NONE && it.zone_from > n.pos {
let before = widths[it.zone_from] - n.tw - items[it.zone_from].hang;
if target - before < sp.hyph_zone {
return false;
}
}
true
}
/// Fitness class and cumulative penalty for a candidate line break.
fn break_demerits(n: Node, r: f64, pp: f64, flagged: bool, priority: u8, cjk: bool) -> (usize, f64) {
// 禁則 priority (JIS X 4051): push-in-first rates breaks whose line would have to be
// stretched (r > 0: the next character is pushed out) worse than ones it can reach by
// compressing (追い込み); push-out-first the other way. Adjustment-amount mode and a
// paragraph without CJK text rate every candidate by its adjustment alone.
let preference = if !cjk {
1.0
} else {
match priority {
1 if r > 0.0 => 4.0,
2 if r < 0.0 => 4.0,
_ => 1.0,
}
};
let bad = preference * 100.0 * r.abs().powi(3);
let lp = 10.0 + bad;
let mut d = if pp >= 0.0 {
lp * lp + pp * pp
} else if pp > -INF {
lp * lp - pp * pp
} else {
lp * lp
};
if flagged && n.flagged {
d += 3000.0;
}
let fit = if r < -0.5 {
0
} else if r <= 0.5 {
1
} else if r <= 1.0 {
2
} else {
3
};
if (fit as i32 - n.fitness as i32).abs() > 1 {
d += 3000.0;
}
(fit, n.demerits + d)
}
/// Width, stretch, shrink and overhang totals before each item.
struct PrefixSums {
sw: Vec<f64>,
sy: Vec<[f64; 3]>,
sz: Vec<[f64; 3]>,
so: Vec<f64>,
}
fn prefix_sums(items: &[Item]) -> PrefixSums {
let mut sw = vec![0.0; items.len() + 1];
let mut sy = vec![[0.0; 3]; items.len() + 1];
let mut sz = vec![[0.0; 3]; items.len() + 1];
let mut so = vec![0.0; items.len() + 1];
for (i, it) in items.iter().enumerate() {
let (w, y, z) = match it.kind {
Kind::Box | Kind::Glue => (it.w, it.st, it.sh),
Kind::Penalty => (0.0, [0.0; 3], [0.0; 3]),
};
sw[i + 1] = sw[i] + w;
so[i + 1] = so[i] + it.over;
for t in 0..3 {
sy[i + 1][t] = sy[i][t] + y[t];
sz[i + 1][t] = sz[i][t] + z[t];
}
}
PrefixSums { sw, sy, sz, so }
}
fn kp_pass(input: PassInput<'_>) -> Option<Vec<Break>> {
let PassInput { items, item_glyphs, glyphs, spacing: sp, width, tolerance: tol, emergency } = input;
let m = items.len();
let PrefixSums { sw, sy, sz, so } = prefix_sums(items);
let first_box = items.iter().find(|i| i.kind == Kind::Box);
let first_hang = first_box.map_or(0.0, |b| b.hang);
let first_elastic = first_box.map_or([0.0; 2], |b| b.start_elastic);
let mut arena: Vec<Node> = vec![Node {
pos: 0,
line: 0,
fitness: 1,
tw: first_hang,
ty: [-first_elastic[0], 0.0, 0.0],
tz: [-first_elastic[1], 0.0, 0.0],
to: 0.0,
demerits: 0.0,
prev: None,
hyphens: 0,
flagged: false,
}];
let limit = sp.hyphen_limit as usize;
let states = if limit == 0 { 2 } else { (limit + 1).min(MAX_HYPHEN_STATES) };
let mut active: Vec<usize> = vec![0];
let mut best: Vec<Option<(f64, usize)>> = vec![None; 4 * states];
let mut keep = Vec::new();
for b in 0..m {
let it = items[b];
let (is_break, pw, pp, flagged) = match it.kind {
Kind::Penalty if it.p < INF => (true, it.w, it.p, it.flagged),
Kind::Glue if b > 0 && items[b - 1].kind == Kind::Box => (true, 0.0, 0.0, false),
_ => (false, 0.0, 0.0, false),
};
if !is_break {
continue;
}
let forced = pp <= -INF;
best.iter_mut().for_each(|x| *x = None);
keep.clear();
let mut last_removed: Option<usize> = None;
for &a in &active {
let n = arena[a];
let l = sw[b] - n.tw + pw - it.hang;
let target = width(n.line).max(1.0);
let mut y = [0.0; 3];
let mut z = [0.0; 3];
for t in 0..3 {
y[t] = sy[b][t] - n.ty[t];
z[t] = sz[b][t] - n.tz[t];
}
y[0] = (y[0] + it.edge_elastic[0]).max(0.0);
z[0] = (z[0] + it.edge_elastic[1]).max(0.0);
// A line that overruns its measure by a rounding error fits exactly.
let d = target - l;
let d = if d < 0.0 && d > -FIT_EPS { 0.0 } else { d };
let (mut r, feasible) = tiered_ratio(d, y, z, so[b] - n.to);
if it.emergency && sp.justify && r > 0.0 {
// A piece of an overlong word usually has no elastic material: rate it by the
// space it leaves, so the fullest piece wins (the break at the last glyph that fits).
r = d / target;
}
if feasible && !forced {
keep.push(a);
} else {
last_removed = Some(a);
}
if !feasible || (r > tol && !forced) {
continue;
}
if flagged && !hyphen_allowed(it, n, sp, &sw, items, target) {
continue;
}
let (fit, total) = break_demerits(n, r, pp, flagged, sp.kinsoku_priority, sp.kinsoku_cjk);
let hs = if flagged { (n.hyphens as usize + 1).min(states - 1) } else { 0 };
let slot = &mut best[fit * states + hs];
if slot.is_none_or(|(bd, _)| total < bd) {
*slot = Some((total, a));
}
}
// Emergency: nothing can reach this break and nothing remains active → accept an overfull line.
if emergency
&& keep.is_empty()
&& best.iter().all(Option::is_none)
&& let Some(a) = last_removed
{
best[0] = Some((arena[a].demerits + 1e8, a));
}
std::mem::swap(&mut active, &mut keep);
if best.iter().all(Option::is_none) {
if active.is_empty() {
return None;
}
continue;
}
// Totals after the break: skip glue and penalties up to the next box.
let (mut tw, mut ty, mut tz, mut to) = (sw[b], sy[b], sz[b], so[b]);
let mut i = b;
while i < m {
let x = items[i];
match x.kind {
Kind::Box => {
tw += x.hang;
ty[0] -= x.start_elastic[0];
tz[0] -= x.start_elastic[1];
break;
}
Kind::Glue => {
tw += x.w;
to += x.over;
for t in 0..3 {
ty[t] += x.st[t];
tz[t] += x.sh[t];
}
}
Kind::Penalty if x.p <= -INF && i > b => break,
Kind::Penalty => {}
}
i += 1;
}
// Knuth's pruning: a class is only worth a node if it is within the fitness demerit of the best.
let min_d = best.iter().flatten().map(|x| x.0).fold(f64::INFINITY, f64::min);
for (k, c) in best.iter().enumerate() {
if let Some((d, a)) = *c
&& d <= min_d + 3000.0
{
let prev = arena[a];
arena.push(Node {
pos: b,
line: prev.line + 1,
fitness: (k / states) as u8,
tw,
ty,
tz,
to,
demerits: d,
prev: Some(a),
hyphens: if flagged { prev.hyphens + 1 } else { 0 },
flagged,
});
active.push(arena.len() - 1);
}
}
}
// The final forced break: best node at position m-1.
let end = active.iter().copied().filter(|&a| arena[a].pos == m - 1).min_by(|&a, &b| arena[a].demerits.total_cmp(&arena[b].demerits))?;
let mut chain = Vec::new();
let mut cur = Some(end);
while let Some(c) = cur {
if arena[c].prev.is_some() {
chain.push(arena[c].pos);
}
cur = arena[c].prev;
}
chain.reverse();
Some(breaks_from_positions(items, item_glyphs, glyphs, &chain))
}
fn breaks_from_positions(items: &[Item], ig: &[usize], glyphs: &[Glyph], chain: &[usize]) -> Vec<Break> {
let n = glyphs.len();
let mut out = Vec::with_capacity(chain.len());
let mut start = 0;
for &b in chain {
let it = items[b];
let (end, hyphen, forced) = match it.kind {
Kind::Penalty => {
let e = ig[b].min(n);
// A flagged penalty with width = an inserted hyphen (not an explicit '-').
let explicit = e > 0 && matches!(glyphs[e - 1].ch, '-' | '\u{2010}');
(e, it.flagged && it.w > 0.0 && !explicit || (it.flagged && e > 0 && glyphs[e - 1].ch == SOFT_HYPHEN), it.p <= -INF)
}
Kind::Glue | Kind::Box => (ig[b], false, false),
};
// Trim trailing spaces from the visible range; skip leading spaces of the next line.
let mut vis_end = end;
while vis_end > start && glyphs[vis_end - 1].is_space() {
vis_end -= 1;
}
let mut next = end;
while next < n && glyphs[next].is_space() {
next += 1;
}
let forced_glyph = end > 0 && end <= n && is_forced(glyphs[end - 1].ch);
out.push(Break { start, end: vis_end, next, hyphen, forced: forced || forced_glyph });
start = next;
}
if out.is_empty() {
out.push(Break { start: 0, end: n, next: n, hyphen: false, forced: true });
}
// Lines produced past the paragraph end are dropped, except the empty line after a trailing
// forced line break (a trailing column, frame or page break ends the paragraph).
let trailing_forced = glyphs.last().is_some_and(|g| g.ch == designcraft_doc::story::FORCED_LINE_BREAK);
out.retain(|b| b.start < n || (b.start == n && trailing_forced));
out
}
/// Where a line with no break opportunity before glyph `i` (a word wider than the measure) is
/// split: before `i`, or earlier where kinsoku forbids that (no line starts with closing
/// punctuation).
fn emergency_split(glyphs: &[Glyph], start: usize, i: usize) -> usize {
let allowed = |j: usize| matches!((glyphs.get(j.wrapping_sub(1)), glyphs.get(j)), (Some(a), Some(b)) if kinsoku_allows(a.ch, b.ch));
(start + 1..=i).rev().find(|&j| allowed(j)).unwrap_or(i)
}
/// Greedy first-fit breaking (single-line composer; also used for paragraphs with tabs).
///
/// `tab(line, x, i)` is the advance of the tab glyph `i` when it starts `x` from the start of
/// line `line`: tabs have no width until they reach their stop, which depends on where they sit.
pub fn greedy(
glyphs: &[Glyph],
hyph_after: &[bool],
sp: &Spacing,
width: &dyn Fn(usize) -> f64,
tab: &dyn Fn(usize, f64, usize) -> f64,
) -> Vec<Break> {
let n = glyphs.len();
let mut out = Vec::new();
let mut start = 0;
let mut line = 0;
let mut hyphens = 0u32;
let mut hy_cache = Vec::new();
if n == 0 {
return vec![Break { start: 0, end: 0, next: 0, hyphen: false, forced: true }];
}
let may_hyphenate = |hyphens: u32| sp.hyphen_limit == 0 || hyphens < sp.hyphen_limit;
while start < n {
let w = width(line).max(1.0);
let mut x = -hang_left(&glyphs[start], sp) + glyphs[start].moji.start;
let mut shrink = crate::mojikumi::start_elastic(&glyphs[start], sp.justify, !sp.push_out_only())[1];
let mut last_natural: Option<(usize, bool)> = None;
let mut last_ok: Option<(usize, bool)> = None; // (break position = end glyph, hyphen)
let mut last_space: Option<(usize, f64)> = None; // (break position, line width there)
let mut i = start;
let mut brk: Option<(usize, bool, bool)> = None;
while i < n {
let g = &glyphs[i];
if is_forced(g.ch) {
brk = Some((i + 1, false, true));
break;
}
if g.is_space() && !g.no_break && g.break_after != Some(false) {
if sp.justify {
shrink += sp.space_elastic(g).1;
}
last_ok = Some((i, false));
if x <= w + FIT_EPS {
last_natural = last_ok;
}
last_space = Some((i, x));
x += g.adv;
i += 1;
continue;
}
let hang_r = right_hang(g, sp);
let adv = if g.ch == '\t' { tab(line, x, i) } else { g.adv };
let end_shrink = crate::mojikumi::end_elastic(g, sp.justify, !sp.push_out_only())[1];
let available = shrink + sp.box_elastic(g).1.iter().sum::<f64>() + end_shrink;
if sp.kinsoku_cjk
&& sp.kinsoku_priority == 2
&& x + adv - hang_r > w + FIT_EPS
&& let Some((end, hyphen)) = last_natural
{
brk = Some((end, hyphen, false));
break;
}
if x + adv - hang_r > w + available.max(0.0) + FIT_EPS
&& i > start
&& (last_ok.is_some() || glyphs.get(i - 1).is_none_or(|p| p.break_after != Some(false) && !p.no_break))
{
// Overflow: break at the last opportunity, else before this glyph.
brk = Some(match last_ok {
// Hyphenation zone: break before the word if that leaves little space.
Some((_, true)) if !sp.justify && sp.hyph_zone > 0.0 && last_space.is_some_and(|(_, xs)| w - xs < sp.hyph_zone) => {
(last_space.map_or(i, |s| s.0), false, false)
}
Some((p, h)) => (p, h, false),
None => (emergency_split(glyphs, start, i), false, false),
});
break;
}
x += adv;
shrink += sp.box_elastic(g).1.iter().sum::<f64>();
if i + 1 < n && !glyphs[i + 1].is_space() && !g.no_break && g.break_after != Some(false) {
if g.ch == SOFT_HYPHEN {
if may_hyphenate(hyphens) {
let hw = hyphen_width(g, &mut hy_cache);
let hy = (hw - hyphen_hang(g, hw, sp)).max(0.0);
if x + hy <= w + shrink + FIT_EPS {
last_ok = Some((i + 1, true));
}
}
} else if matches!(g.ch, '-' | '\u{2010}' | '\u{2013}' | '\u{2014}' | '/')
|| g.break_after.unwrap_or_else(|| cjk_break(g, &glyphs[i + 1], sp))
{
last_ok = Some((i + 1, false));
if x - hang_r <= w + FIT_EPS {
last_natural = last_ok;
}
} else if hyph_after[i] && may_hyphenate(hyphens) {
let hw = hyphen_width(g, &mut hy_cache);
let hy = (hw - hyphen_hang(g, hw, sp)).max(0.0);
if x + hy <= w + shrink + FIT_EPS {
last_ok = Some((i + 1, true));
}
}
}
i += 1;
}
let (end, hyphen, forced) = brk.unwrap_or((n, false, true));
hyphens = if hyphen { hyphens + 1 } else { 0 };
let mut vis_end = end;
while vis_end > start && glyphs[vis_end - 1].is_space() {
vis_end -= 1;
}
let mut next = end;
while next < n && glyphs[next].is_space() {
next += 1;
}
let next = next.max(start + 1).min(n.max(start + 1));
out.push(Break { start, end: vis_end, next: next.min(n), hyphen, forced: forced || end == n });
if next >= n {
break;
}
start = next;
line += 1;
}
// A forced line break as the very last glyph leaves an empty final line (InDesign shows it);
// a column, frame or page break there ends the paragraph.
if let Some(last) = glyphs.last()
&& last.ch == designcraft_doc::story::FORCED_LINE_BREAK
{
out.push(Break { start: n, end: n, next: n, hyphen: false, forced: true });
}
out
}
/// Natural width of a broken line (with its inserted hyphen).
pub fn line_width(glyphs: &[Glyph], b: &Break) -> f64 {
let w: f64 = glyphs[b.start..b.end.max(b.start)].iter().map(|g| g.adv).sum();
w + if b.hyphen && b.end > 0 { glyphs[b.end - 1].size * 0.33 } else { 0.0 }
}
/// Balance Ragged Lines: keep the composer's line count but make the lines as even as possible,
/// by composing against the narrowest measure that still yields that many lines.
pub fn balanced(glyphs: &[Glyph], hyph_after: &[bool], sp: &Spacing, width: &dyn Fn(usize) -> f64) -> Vec<Break> {
let base = knuth_plass(glyphs, hyph_after, sp, width);
let n = base.len();
if n < 2 || glyphs.len() > 3000 || base[..n - 1].iter().any(|b| b.forced) {
return base;
}
let ok = |f: f64| -> Option<Vec<Break>> {
let w = |j: usize| width(j) * f;
let br = knuth_plass(glyphs, hyph_after, sp, &w);
(br.len() == n && br.iter().enumerate().all(|(j, b)| line_width(glyphs, b) <= w(j) + 0.01)).then_some(br)
};
let (mut lo, mut hi) = (0.3, 1.0);
let mut best = base;
for _ in 0..14 {
let mid = (lo + hi) / 2.0;
match ok(mid) {
Some(b) => {
best = b;
hi = mid;
}
None => lo = mid,
}
}
best
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn tiers_are_used_in_order() {
// Word stretch alone.
let (r, ok) = tiered_ratio(5.0, [10.0, 10.0, 10.0], [0.0; 3], 10.0);
assert!(ok && (r - 0.5).abs() < 1e-9);
// Word saturated, half the letter tier.
let (r, _) = tiered_ratio(15.0, [10.0, 10.0, 10.0], [0.0; 3], 10.0);
assert!((r - (1.0 + 0.5 * TIER_COST[1])).abs() < 1e-9);
// Beyond every tier: unbounded word spacing.
let (r, _) = tiered_ratio(40.0, [10.0, 10.0, 10.0], [0.0; 3], 10.0);
assert!(r > 2.0);
// Shrink beyond the tiers is infeasible.
assert!(!tiered_ratio(-25.0, [0.0; 3], [10.0, 10.0, 0.0], 0.0).1);
assert!(tiered_ratio(-15.0, [0.0; 3], [10.0, 10.0, 0.0], 0.0).1);
}
}
No file is open. Choose one in the tree, or press Ctrl+O (⌘O on a Mac) to find one by name.
Syntax highlighting could not load. The unmodified read-only text remains available above.