GitCorner

Code

ossartcraftdesigncraft🌐
88f5a00e389b
//! 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);
    }
}