retex_engine/

linebreak.rs

//! Breaking paragraphs into lines (*TeX: The Program* §813–§890, with
//! e-TeX's `\lastlinefit` and penalty arrays, and LuaTeX's changes).
//!
//! LuaTeX differences reproduced here:
//!
//! * before breaking, the paragraph goes through the node processing
//!   passes (hyphenation, ligatures, kerns; [`crate::nodeproc`]);
//! * discretionaries carry their own penalty and hold their replacement
//!   text, so the width of a line without a break at a discretionary
//!   includes the replacement text;
//! * at a chosen discretionary break, the pre-break text is placed before
//!   the (now empty) discretionary node, which stays at the end of the
//!   line; the post-break text starts the next line;
//! * glue orders include `fi`;
//! * `\tracingparagraphs` prints `@@n: line …` for new break nodes but a
//!   single `@` when referring to them (`via @n`, `-> @n`).

#![allow(clippy::needless_range_loop)]

use std::rc::Rc;

use crate::Engine;
use crate::build::PackSpec;
use crate::glue::Glue;
use crate::nodes::{NodeData, NodeRef, glue_sub, id, kern_sub};
use crate::primitives_gen::{
    assign_dimen as dp, assign_glue as gp, assign_int as ip, set_etex_shape as es,
};
use crate::typeset::{AWFUL_BAD, EJECT_PENALTY, INF_BAD, INF_PENALTY};

const VERY_LOOSE_FIT: usize = 0;
const LOOSE_FIT: usize = 1;
const DECENT_FIT: usize = 2;
const TIGHT_FIT: usize = 3;

/// Widths: natural width, stretch of orders normal, fi, fil, fill, filll,
/// shrink, and the stretch and shrink of font expansion.
type Widths = [i32; NW];

/// The number of entries of [`Widths`].
const NW: usize = 9;
/// Index of the font expansion stretch in [`Widths`].
const FONT_STRETCH: usize = 7;
/// Index of the font expansion shrink in [`Widths`].
const FONT_SHRINK: usize = 8;

#[inline]
fn add_glue(w: &mut Widths, g: &Glue) {
    w[0] += g.width;
    w[1 + (g.stretch_order as usize).min(4)] += g.stretch;
    w[6] += g.shrink;
}

/// An entry of the active list.
#[derive(Clone, Debug)]
enum Entry {
    /// The list head and terminator (`active` = `last_active`).
    Sentinel,
    /// An active breakpoint.
    Active {
        passive: Option<usize>,
        line_number: i32,
        fitness: usize,
        hyphenated: bool,
        total_demerits: i32,
        short: i32,
        glue: i32,
    },
    /// A delta node.
    Delta(Widths),
}

struct Item {
    next: usize,
    entry: Entry,
}

/// A passive breakpoint record.
struct Passive {
    cur_break: NodeRef,
    prev_break: Option<usize>,
    serial: i32,
    /// Left protrusion of the line after this break (`\protrudechars` > 1).
    left_pw: i32,
}

/// The state of one `line_break` call.
struct Breaker {
    items: Vec<Item>,
    free: Vec<usize>,
    passive: Vec<Passive>,
    active_width: Widths,
    cur_active_width: Widths,
    background: Widths,
    break_width: Widths,
    minimal_demerits: [i32; 4],
    minimum_demerits: i32,
    best_place: [Option<usize>; 4],
    best_pl_line: [i32; 4],
    best_pl_short: [i32; 4],
    best_pl_glue: [i32; 4],
    threshold: i32,
    second_pass: bool,
    final_pass: bool,
    disc_width: i32,
    /// Font stretch and shrink of the pre-break text being tried.
    disc_fs: crate::expansion::FontStretch,
    easy_line: i32,
    last_special_line: i32,
    first_width: i32,
    second_width: i32,
    first_indent: i32,
    second_indent: i32,
    par_shape: Option<std::rc::Rc<[i32]>>,
    printed_node: NodeRef,
    pass_number: i32,
    do_last_line_fit: bool,
    fill_width: [i32; 4],
    last_line_fit: i32,
    adj_demerits: i32,
    line_penalty: i32,
    double_hyphen_demerits: i32,
    final_hyphen_demerits: i32,
    tracing: bool,
    no_shrink_error_yet: bool,
    /// `\protrudechars` > 1: protrusion counts in line breaking.
    protrude: bool,
    /// Left protrusion of the first line.
    first_left_pw: i32,
    /// The list head.
    head: NodeRef,
    /// `\adjustspacing` > 1: font expansion counts in line breaking.
    expand: bool,
    /// Kerns take part in font expansion (`\adjustspacing` = 2).
    expand_kerns: bool,
}

const ACTIVE: usize = 0;

impl Breaker {
    fn alloc(&mut self, e: Entry, next: usize) -> usize {
        if let Some(i) = self.free.pop() {
            self.items[i] = Item { next, entry: e };
            i
        } else {
            self.items.push(Item { next, entry: e });
            self.items.len() - 1
        }
    }

    fn release(&mut self, i: usize) {
        self.free.push(i);
    }

    fn is_delta(&self, i: usize) -> bool {
        matches!(self.items[i].entry, Entry::Delta(_))
    }

    fn delta(&self, i: usize) -> Widths {
        match self.items[i].entry {
            Entry::Delta(d) => d,
            _ => [0; NW],
        }
    }

    fn line_number(&self, i: usize) -> i32 {
        match self.items[i].entry {
            Entry::Active { line_number, .. } => line_number,
            Entry::Sentinel => i32::MAX,
            Entry::Delta(_) => 0,
        }
    }

    /// Frees all active and passive nodes.
    fn clean_up(&mut self) {
        self.items.truncate(1);
        self.items[ACTIVE].next = ACTIVE;
        self.free.clear();
        self.passive.clear();
    }
}

/// The parameters of line breaking: the current values of TeX's
/// parameters for a paragraph, or those given to `tex.linebreak`.
#[derive(Clone, Debug)]
pub struct ParParams {
    /// `\pretolerance`.
    pub pretolerance: i32,
    /// `\tolerance`.
    pub tolerance: i32,
    /// `\looseness`.
    pub looseness: i32,
    /// `\adjdemerits`.
    pub adj_demerits: i32,
    /// `\linepenalty`.
    pub line_penalty: i32,
    /// `\lastlinefit`.
    pub last_line_fit: i32,
    /// `\doublehyphendemerits`.
    pub double_hyphen_demerits: i32,
    /// `\finalhyphendemerits`.
    pub final_hyphen_demerits: i32,
    /// `\hangafter`.
    pub hang_after: i32,
    /// `\hangindent`.
    pub hang_indent: i32,
    /// `\hsize`.
    pub hsize: i32,
    /// `\emergencystretch`.
    pub emergency_stretch: i32,
    /// `\brokenpenalty`.
    pub broken_penalty: i32,
    /// `\protrudechars`.
    pub protrude_chars: i32,
    /// `\adjustspacing`.
    pub adjust_spacing: i32,
    /// `\tracingparagraphs`.
    pub tracing_paragraphs: i32,
    /// `\interlinepenalty`.
    pub interline_penalty: i32,
    /// `\clubpenalty`.
    pub club_penalty: i32,
    /// The penalty before the last line (`\widowpenalty` or
    /// `\displaywidowpenalty`).
    pub widow_penalty: i32,
    /// `\interlinepenalties` (values, without their count).
    pub interline_penalties: Option<Rc<[i32]>>,
    /// `\clubpenalties`.
    pub club_penalties: Option<Rc<[i32]>>,
    /// `\widowpenalties` or `\displaywidowpenalties`.
    pub widow_penalties: Option<Rc<[i32]>>,
    /// `\leftskip`.
    pub left_skip: Glue,
    /// `\rightskip`.
    pub right_skip: Glue,
    /// `\parshape`: indentation and width of each line.
    pub par_shape: Option<Rc<[i32]>>,
    /// `\pardir`.
    pub par_dir: i8,
}

/// What `tex.linebreak` reports about a paragraph it broke.
#[derive(Clone, Copy, Debug)]
pub struct LineBreakInfo {
    /// The depth of the last line.
    pub prev_depth: i32,
    /// The number of lines.
    pub prev_graf: i32,
    /// The actual looseness.
    pub looseness: i32,
    /// The total demerits of the chosen breaks.
    pub demerits: i32,
}

impl Engine {
    /// Width of a node in a discretionary text.
    fn disc_node_width(&self, s: NodeRef) -> i32 {
        match self.nodes.data(s) {
            NodeData::Glyph(_) => self.glyph_dimensions(s).0,
            _ => self.nodes.width(s),
        }
    }

    fn list_width(&self, mut s: NodeRef) -> i32 {
        let mut w = 0;
        while !s.is_null() {
            w += self.disc_node_width(s);
            s = self.nodes.next(s);
        }
        w
    }

    /// Recovers from infinite shrinkage in a paragraph (`finite_shrink`).
    fn finite_shrink(&mut self, br: &mut Breaker, g: Glue) -> Glue {
        if br.no_shrink_error_yet {
            br.no_shrink_error_yet = false;
            if br.tracing {
                self.end_diagnostic(true);
            }
            self.print_err("Infinite glue shrinkage found in a paragraph");
            self.help(&[
                "The paragraph just ended includes some glue that has",
                "infinite shrinkability, e.g., `\\hskip 0pt minus 1fil'.",
                "Such glue doesn't belong there---it allows a paragraph",
                "of any length to fit on one line. But it's safe to proceed,",
                "since the offensive shrinkability has been made finite.",
            ]);
            self.error();
            if br.tracing {
                self.begin_diagnostic();
            }
        }
        Glue {
            shrink_order: 0,
            ..g
        }
    }

    /// Breaks the current paragraph into lines and appends them to the
    /// enclosing vertical list (`line_break`). `widow_penalty` is the
    /// penalty before the last line (`\widowpenalty` or
    /// `\displaywidowpenalty`).
    pub fn line_break(&mut self, final_widow_penalty: i32) {
        self.work_begin(crate::profile::Work::LineBreak);
        self.line_break_inner(final_widow_penalty);
        self.work_end();
    }

    fn line_break_inner(&mut self, final_widow_penalty: i32) {
        self.fonts.sync_dense();
        // A display interrupts the paragraph: `$$` was just read. The
        // callbacks then get the group code `math_shift` (observed).
        let display = self.cur_cmd == crate::cmd::Cmd::MathShift;
        let group = if display { "math_shift" } else { "" };
        self.ts.pack_begin_line = self.cur_list().mode_line;
        // Get ready to start: move the list to temp_head and append the
        // \parfillskip glue.
        let temp_head = self.nodes.new_temp();
        let head = self.cur_list().head;
        let first = self.nodes.next(head);
        self.nodes.set_next(head, NodeRef::NULL);
        // LuaTeX: the node processing passes (and their callbacks) see the
        // paragraph as it is, before its final glue goes and \parfillskip
        // comes (observed).
        let first = self.node_process_list(first, crate::nodeproc::Context::Paragraph);
        self.nodes.link(temp_head, first);
        if first.is_null() {
            self.nodes.set_next(temp_head, NodeRef::NULL);
        }
        let mut tail = if first.is_null() {
            temp_head
        } else {
            self.nodes.tail_of(first)
        };
        if self.nodes.id(tail) == id::GLUE {
            // Remove a final glue node.
            let p = self.find_prev_in(temp_head, tail);
            self.nodes.set_next(p, NodeRef::NULL);
            self.nodes.flush_list(tail);
            tail = p;
        }
        let pen = self.new_penalty_node(INF_PENALTY);
        // Observed: subtype 2 (`linepenalty`).
        self.nodes.set_subtype(pen, 2);
        self.nodes.link(tail, pen);
        let pfs = self.new_param_glue(glue_sub::PAR_FILL_SKIP);
        self.nodes.link(pen, pfs);
        let last_line_fill = pfs;
        self.pop_nest();
        // LuaTeX: the pre_linebreak_filter.
        let first = self.nodes.next(temp_head);
        let had_list = !first.is_null();
        let first = self.filter_list("pre_linebreak_filter", first, group);
        if had_list && first.is_null() {
            // Observed: a callback that empties the paragraph (returning
            // false or nil) removes its local_par node, and LuaTeX stops.
            self.confusion("weird par dir");
        }
        self.nodes.link(temp_head, first);
        if first.is_null() {
            self.nodes.set_next(temp_head, NodeRef::NULL);
        }
        let old_tail = self.cur_list().tail;
        let replaced = match self.lua.clone() {
            Some(h) if h.has_callback("linebreak_filter") => {
                let first = self.nodes.next(temp_head);
                h.linebreak_filter(self, first, display)
            }
            _ => None,
        };
        if let Some(list) = replaced {
            // The callback's list goes to the vertical list as it is;
            // `\prevdepth` and `\prevgraf` stay (observed).
            let mut p = list;
            while !p.is_null() && self.nodes.id(p) != id::HLIST {
                p = self.nodes.next(p);
            }
            if p.is_null() {
                self.print_err("Invalid linebreak_filter");
                self.help(&[
                    "A linebreaking routine should return a non-empty list of nodes",
                    "and at least one of those has to be a \\hbox.",
                    "Sorry, I cannot recover from this.",
                ]);
                self.succumb();
            }
            self.nodes.link(old_tail, list);
            let t = self.nodes.tail_of(list);
            self.cur_list_mut().tail = t;
        } else {
            let params = self.par_params(final_widow_penalty, display);
            self.break_paragraph(temp_head, Some(last_line_fill), &params);
        }
        if self.has_callback("post_linebreak_filter") {
            let first = self.nodes.next(old_tail);
            self.nodes.set_next(old_tail, NodeRef::NULL);
            let first = self.filter_list("post_linebreak_filter", first, group);
            self.cur_list_mut().tail = old_tail;
            if !first.is_null() {
                self.nodes.link(old_tail, first);
                let t = self.nodes.tail_of(first);
                self.cur_list_mut().tail = t;
            }
        }
        self.nodes.free(temp_head);
        self.ts.pack_begin_line = 0;
    }

    /// The line breaking parameters of a paragraph: the current values,
    /// with `widow_penalty` (`\widowpenalty` or `\displaywidowpenalty`)
    /// before the last line.
    pub fn par_params(&self, widow_penalty: i32, display: bool) -> ParParams {
        let array = |k: u32| self.eqtb.etex_shape[k as usize].val.clone();
        ParParams {
            pretolerance: self.eqtb.int(ip::PRETOLERANCE),
            tolerance: self.eqtb.int(ip::TOLERANCE),
            looseness: self.eqtb.int(ip::LOOSENESS),
            adj_demerits: self.eqtb.int(ip::ADJDEMERITS),
            line_penalty: self.eqtb.int(ip::LINEPENALTY),
            last_line_fit: self.eqtb.int(ip::LASTLINEFIT),
            double_hyphen_demerits: self.eqtb.int(ip::DOUBLEHYPHENDEMERITS),
            final_hyphen_demerits: self.eqtb.int(ip::FINALHYPHENDEMERITS),
            hang_after: self.eqtb.int(ip::HANGAFTER),
            hang_indent: self.eqtb.dimen(dp::HANGINDENT),
            hsize: self.eqtb.dimen(dp::HSIZE),
            emergency_stretch: self.eqtb.dimen(dp::EMERGENCYSTRETCH),
            broken_penalty: self.eqtb.int(ip::BROKENPENALTY),
            protrude_chars: self.eqtb.int(ip::PROTRUDECHARS),
            adjust_spacing: self.eqtb.int(ip::ADJUSTSPACING),
            tracing_paragraphs: self.eqtb.int(ip::TRACINGPARAGRAPHS),
            interline_penalty: self.eqtb.int(ip::INTERLINEPENALTY),
            club_penalty: self.eqtb.int(ip::CLUBPENALTY),
            widow_penalty,
            interline_penalties: array(es::INTERLINEPENALTIES),
            club_penalties: array(es::CLUBPENALTIES),
            widow_penalties: array(if display {
                es::DISPLAYWIDOWPENALTIES
            } else {
                es::WIDOWPENALTIES
            }),
            left_skip: self.eqtb.glue(gp::LEFTSKIP),
            right_skip: self.eqtb.glue(gp::RIGHTSKIP),
            par_shape: self.eqtb.par_shape.val.clone(),
            par_dir: self.dir_param(crate::primitives_gen::assign_dir::PARDIR) as i8,
        }
    }

    /// `tex.linebreak`: breaks the list `head` (which should end with
    /// the `\parfillskip` glue) into lines with parameters `p`, and
    /// returns the vertical list of lines, with interline glue and
    /// penalties, and what the breaking found. The list is neither
    /// hyphenated nor given to callbacks; the current list's
    /// `\prevdepth` starts the interline glue, and line numbers start
    /// at 1 (observed).
    pub fn lua_line_break(&mut self, head: NodeRef, p: &ParParams) -> (NodeRef, LineBreakInfo) {
        if self.nodes.id(self.nodes.tail_of(head)) == id::GLYPH {
            // Observed: LuaTeX's check of the list end.
            self.luatex_fatal("linebreak", "invalid list tail, probably missing glue");
        }
        self.fonts.sync_dense();
        let prev_depth = self.cur_list().prev_depth;
        self.push_nest(crate::maincontrol::Mode::InternalVertical);
        self.cur_list_mut().prev_depth = prev_depth;
        let temp_head = self.nodes.new_temp();
        self.nodes.link(temp_head, head);
        let (looseness, demerits) = self.break_paragraph(temp_head, None, p);
        self.nodes.free(temp_head);
        let list_head = self.cur_list().head;
        let lines = self.nodes.next(list_head);
        self.nodes.set_next(list_head, NodeRef::NULL);
        if !lines.is_null() {
            self.nodes.set_prev(lines, NodeRef::NULL);
        }
        let info = LineBreakInfo {
            prev_depth: self.cur_list().prev_depth,
            prev_graf: self.cur_list().prev_graf,
            looseness,
            demerits,
        };
        self.pop_nest();
        (lines, info)
    }

    /// Breaks the list after `temp_head` into lines with parameters `p`
    /// and appends them to the current vertical list. `last_line_fill`
    /// is the `\parfillskip` glue, for `\lastlinefit`. Returns the actual
    /// looseness and the total demerits of the chosen breaks.
    fn break_paragraph(
        &mut self,
        temp_head: NodeRef,
        last_line_fill: Option<NodeRef>,
        p: &ParParams,
    ) -> (i32, i32) {
        let mut br = Breaker {
            items: vec![Item {
                next: ACTIVE,
                entry: Entry::Sentinel,
            }],
            free: Vec::new(),
            passive: Vec::new(),
            active_width: [0; NW],
            cur_active_width: [0; NW],
            background: [0; NW],
            break_width: [0; NW],
            minimal_demerits: [AWFUL_BAD; 4],
            minimum_demerits: AWFUL_BAD,
            best_place: [None; 4],
            best_pl_line: [0; 4],
            best_pl_short: [0; 4],
            best_pl_glue: [0; 4],
            threshold: 0,
            second_pass: false,
            final_pass: false,
            disc_width: 0,
            disc_fs: Default::default(),
            easy_line: 0,
            last_special_line: 0,
            first_width: 0,
            second_width: 0,
            first_indent: 0,
            second_indent: 0,
            par_shape: p.par_shape.clone(),
            printed_node: temp_head,
            pass_number: 0,
            do_last_line_fit: false,
            fill_width: [0; 4],
            last_line_fit: p.last_line_fit,
            adj_demerits: p.adj_demerits,
            line_penalty: p.line_penalty,
            double_hyphen_demerits: p.double_hyphen_demerits,
            final_hyphen_demerits: p.final_hyphen_demerits,
            tracing: p.tracing_paragraphs > 0,
            no_shrink_error_yet: true,
            protrude: p.protrude_chars > 1,
            first_left_pw: 0,
            head: temp_head,
            expand: p.adjust_spacing > 1,
            expand_kerns: p.adjust_spacing == 2,
        };
        if br.expand && !br.protrude {
            self.fix_back_links(temp_head);
        }
        if br.protrude {
            self.fix_back_links(temp_head);
            let first = self.nodes.next(temp_head);
            br.first_left_pw = self.lb_left_protrusion(None, first);
        }
        let mut ls = p.left_skip;
        let mut rs = p.right_skip;
        if ls.shrink_order != 0 && ls.shrink != 0 {
            ls = self.finite_shrink(&mut br, ls);
        }
        if rs.shrink_order != 0 && rs.shrink != 0 {
            rs = self.finite_shrink(&mut br, rs);
        }
        br.background[0] = ls.width + rs.width;
        br.background[1 + (ls.stretch_order as usize).min(4)] += ls.stretch;
        br.background[1 + (rs.stretch_order as usize).min(4)] += rs.stretch;
        br.background[6] = ls.shrink + rs.shrink;
        // Check for special treatment of the last line (\lastlinefit).
        if let Some(last_line_fill) = last_line_fill
            && br.last_line_fit > 0
        {
            let q = self.nodes.glue_spec(last_line_fill);
            if q.stretch > 0 && q.stretch_order > 0 && br.background[2..6].iter().all(|&v| v == 0) {
                br.do_last_line_fit = true;
                br.fill_width = [0; 4];
                br.fill_width[(q.stretch_order as usize - 1).min(3)] = q.stretch;
            }
        }
        // Line lengths.
        let hsize = p.hsize;
        let hang_indent = p.hang_indent;
        let hang_after = p.hang_after;
        match &br.par_shape {
            None => {
                if hang_indent == 0 {
                    br.last_special_line = 0;
                    br.second_width = hsize;
                    br.second_indent = 0;
                } else {
                    br.last_special_line = hang_after.abs();
                    if hang_after < 0 {
                        br.first_width = hsize - hang_indent.abs();
                        br.first_indent = hang_indent.max(0);
                        br.second_width = hsize;
                        br.second_indent = 0;
                    } else {
                        br.first_width = hsize;
                        br.first_indent = 0;
                        br.second_width = hsize - hang_indent.abs();
                        br.second_indent = hang_indent.max(0);
                    }
                }
            }
            Some(s) => {
                let n = (s.len() / 2) as i32;
                br.last_special_line = n - 1;
                br.second_indent = s[2 * (n as usize - 1)];
                br.second_width = s[2 * (n as usize - 1) + 1];
            }
        }
        br.easy_line = if p.looseness == 0 {
            br.last_special_line
        } else {
            i32::MAX - 1
        };
        // Find optimal breakpoints.
        br.threshold = p.pretolerance;
        let emergency = p.emergency_stretch;
        if br.threshold >= 0 {
            if br.tracing {
                self.begin_diagnostic();
                self.printer.print_nl("@firstpass");
            }
            br.second_pass = false;
            br.final_pass = false;
        } else {
            br.threshold = p.tolerance;
            br.second_pass = true;
            br.final_pass = emergency <= 0;
            if br.tracing {
                self.begin_diagnostic();
            }
        }
        let prev_graf = self.cur_list().prev_graf;
        let looseness = p.looseness;
        let best_bet: usize;
        let best_line: i32;
        let mut actual_looseness = 0;
        loop {
            if br.threshold > INF_BAD {
                br.threshold = INF_BAD;
            }
            // Create an active breakpoint for the beginning.
            let q = br.alloc(
                Entry::Active {
                    passive: None,
                    line_number: prev_graf + 1,
                    fitness: DECENT_FIT,
                    hyphenated: false,
                    total_demerits: 0,
                    short: 0,
                    glue: 0,
                },
                ACTIVE,
            );
            br.items[ACTIVE].next = q;
            br.active_width = br.background;
            br.passive.clear();
            br.printed_node = temp_head;
            br.pass_number = 0;
            self.ts.font_in_short_display = 0;
            let mut cur_p = self.nodes.next(temp_head);
            let mut auto_breaking = true;
            let mut prev_p = cur_p;
            while !cur_p.is_null() && br.items[ACTIVE].next != ACTIVE {
                let t = self.nodes.id(cur_p);
                match t {
                    id::GLYPH => {
                        // Advance past a string of characters.
                        prev_p = cur_p;
                        while !cur_p.is_null() && self.nodes.id(cur_p) == id::GLYPH {
                            self.check_lost_char(cur_p);
                            br.active_width[0] += self.glyph_dimensions(cur_p).0;
                            if br.expand {
                                let f = self.glyph_font_stretch(cur_p);
                                br.active_width[FONT_STRETCH] += f.stretch;
                                br.active_width[FONT_SHRINK] += f.shrink;
                            }
                            cur_p = self.nodes.next(cur_p);
                        }
                        continue;
                    }
                    id::HLIST | id::VLIST | id::RULE => {
                        br.active_width[0] += self.nodes.width(cur_p);
                    }
                    id::GLUE => {
                        if auto_breaking {
                            let pt = self.nodes.id(prev_p);
                            // Observed: not after the paragraph's local_par
                            // node (`\noindent\hskip0pt` makes no empty first
                            // line; soul's syllable analysis relies on it).
                            let legal = pt == id::GLYPH
                                || (crate::page::precedes_break(pt) && pt != id::LOCAL_PAR)
                                || (pt == id::KERN
                                    && !matches!(
                                        self.nodes.subtype(prev_p),
                                        kern_sub::USER | kern_sub::ITALIC
                                    ));
                            if legal {
                                self.try_break(&mut br, cur_p, 0, false);
                            }
                        }
                        let mut g = self.nodes.glue_spec(cur_p);
                        if g.shrink_order != 0 && g.shrink != 0 {
                            g = self.finite_shrink(&mut br, g);
                            if let NodeData::Glue { spec, .. } = self.nodes.data_mut(cur_p) {
                                *spec = g;
                            }
                        }
                        add_glue(&mut br.active_width, &g);
                    }
                    id::KERN => {
                        if matches!(self.nodes.subtype(cur_p), kern_sub::USER | kern_sub::ITALIC) {
                            self.kern_break(&mut br, cur_p, auto_breaking);
                        } else {
                            br.active_width[0] += self.nodes.width(cur_p);
                            if br.expand_kerns {
                                let (pv, nx) = (self.nodes.prev(cur_p), self.nodes.next(cur_p));
                                let f = self.kern_font_stretch(pv, cur_p, nx);
                                br.active_width[FONT_STRETCH] += f.stretch;
                                br.active_width[FONT_SHRINK] += f.shrink;
                            }
                        }
                    }
                    id::DISC => {
                        let (pre, _post, rep) = self.nodes.disc_lists(cur_p);
                        let pen = self.nodes.penalty(cur_p);
                        // LuaTeX hyphenates before breaking lines; its first
                        // pass ignores the discretionaries hyphenation made
                        // (subtypes 3–5), like TeX82's first pass, which
                        // runs before hyphenation.
                        let from_hyphenation = self.nodes.subtype(cur_p) >= 3;
                        if br.second_pass || !from_hyphenation {
                            br.disc_width = self.list_width(pre);
                            br.active_width[0] += br.disc_width;
                            if br.expand {
                                br.disc_fs = self.list_font_stretch(pre, br.expand_kerns);
                                br.active_width[FONT_STRETCH] += br.disc_fs.stretch;
                                br.active_width[FONT_SHRINK] += br.disc_fs.shrink;
                            }
                            self.try_break(&mut br, cur_p, pen, true);
                            br.active_width[0] -= br.disc_width;
                            if br.expand {
                                br.active_width[FONT_STRETCH] -= br.disc_fs.stretch;
                                br.active_width[FONT_SHRINK] -= br.disc_fs.shrink;
                            }
                        }
                        br.active_width[0] += self.list_width(rep);
                        if br.expand {
                            let f = self.list_font_stretch(rep, br.expand_kerns);
                            br.active_width[FONT_STRETCH] += f.stretch;
                            br.active_width[FONT_SHRINK] += f.shrink;
                        }
                    }
                    id::MATH => {
                        auto_breaking = self.nodes.subtype(cur_p) == 1;
                        self.kern_break(&mut br, cur_p, auto_breaking);
                    }
                    id::PENALTY => {
                        let pen = self.nodes.penalty(cur_p);
                        self.try_break(&mut br, cur_p, pen, false);
                    }
                    id::LOCAL_PAR
                    | id::DIR
                    | id::BOUNDARY
                    | id::MARK
                    | id::INS
                    | id::ADJUST
                    | id::WHATSIT => {}
                    id::GLUE_SPEC => {
                        self.luatex_warning("parbuilder", "found a glue_spec in a paragraph")
                    }
                    // Observed: other nodes (margin kerns, math noads,
                    // unset nodes, ...), which Lua code can put in a
                    // paragraph, stop LuaTeX.
                    _ => self.luatex_fatal("parbuilder", &format!("weird node {t} in paragraph")),
                }
                prev_p = cur_p;
                cur_p = self.nodes.next(cur_p);
            }
            if cur_p.is_null() {
                // Try the final line break at the end of the paragraph.
                self.try_break(&mut br, NodeRef::NULL, EJECT_PENALTY, true);
                if br.items[ACTIVE].next != ACTIVE {
                    // Find an active node with fewest demerits.
                    let mut r = br.items[ACTIVE].next;
                    let mut fewest = AWFUL_BAD;
                    let mut bb = r;
                    while r != ACTIVE {
                        if let Entry::Active { total_demerits, .. } = br.items[r].entry
                            && total_demerits < fewest
                        {
                            fewest = total_demerits;
                            bb = r;
                        }
                        r = br.items[r].next;
                    }
                    let mut bl = br.line_number(bb);
                    if looseness == 0 {
                        best_bet = bb;
                        best_line = bl;
                        break;
                    }
                    // Find the best active node for the desired looseness.
                    let mut r = br.items[ACTIVE].next;
                    let mut actual = 0;
                    let mut bb2 = bb;
                    while r != ACTIVE {
                        if let Entry::Active {
                            line_number,
                            total_demerits,
                            ..
                        } = br.items[r].entry
                        {
                            let line_diff = line_number - bl;
                            if (line_diff < actual && looseness <= line_diff)
                                || (line_diff > actual && looseness >= line_diff)
                            {
                                bb2 = r;
                                actual = line_diff;
                                fewest = total_demerits;
                            } else if line_diff == actual && total_demerits < fewest {
                                bb2 = r;
                                fewest = total_demerits;
                            }
                        }
                        r = br.items[r].next;
                    }
                    bl = br.line_number(bb2);
                    if actual == looseness || br.final_pass {
                        actual_looseness = actual;
                        best_bet = bb2;
                        best_line = bl;
                        break;
                    }
                }
            }
            // Clean up and try again.
            br.clean_up();
            if !br.second_pass {
                if br.tracing {
                    self.printer.print_nl("@secondpass");
                }
                br.threshold = p.tolerance;
                br.second_pass = true;
                br.final_pass = emergency <= 0;
            } else {
                if br.tracing {
                    self.printer.print_nl("@emergencypass");
                }
                br.background[1] += emergency;
                br.final_pass = true;
            }
        }
        if br.tracing {
            self.end_diagnostic(true);
            self.normalize_selector();
        }
        let demerits = match br.items[best_bet].entry {
            Entry::Active { total_demerits, .. } => total_demerits,
            _ => 0,
        };
        if let Some(last_line_fill) = last_line_fill
            && br.do_last_line_fit
        {
            // Adjust the final line of the paragraph.
            if let Entry::Active { short, glue, .. } = br.items[best_bet].entry {
                if short == 0 {
                    br.do_last_line_fit = false;
                } else if let NodeData::Glue { spec, .. } = self.nodes.data_mut(last_line_fill) {
                    spec.width += short - glue;
                    spec.stretch = 0;
                }
            }
        }
        // Break the paragraph at the chosen breakpoints.
        self.post_line_break(&mut br, best_bet, best_line, temp_head, p);
        br.clean_up();
        (actual_looseness, demerits)
    }

    fn find_prev_in(&self, head: NodeRef, q: NodeRef) -> NodeRef {
        let mut p = head;
        loop {
            let n = self.nodes.next(p);
            if n == q || n.is_null() {
                return p;
            }
            p = n;
        }
    }

    /// `kern_break`: a kern or math node may be a breakpoint if followed by
    /// glue.
    fn kern_break(&mut self, br: &mut Breaker, cur_p: NodeRef, auto_breaking: bool) {
        let n = self.nodes.next(cur_p);
        if !n.is_null() && auto_breaking && self.nodes.id(n) == id::GLUE {
            self.try_break(br, cur_p, 0, false);
        }
        br.active_width[0] += self.nodes.width(cur_p);
    }

    /// Tests a breakpoint (`try_break`).
    fn try_break(&mut self, br: &mut Breaker, cur_p: NodeRef, pi: i32, hyphenated: bool) {
        let mut pi = pi;
        if pi.abs() >= INF_PENALTY {
            if pi > 0 {
                return;
            }
            pi = EJECT_PENALTY;
        }
        let mut no_break_yet = true;
        let mut prev_r = ACTIVE;
        let mut prev_prev_r = ACTIVE;
        let mut old_l = 0;
        let mut line_width = 0;
        let mut right_pw: Option<i32> = None;
        br.cur_active_width = br.active_width;
        loop {
            let r = br.items[prev_r].next;
            // If node r is a delta node, update cur_active_width.
            if let Entry::Delta(d) = br.items[r].entry {
                for k in 0..NW {
                    br.cur_active_width[k] += d[k];
                }
                prev_prev_r = prev_r;
                prev_r = r;
                continue;
            }
            // If a line number class has ended, create new active nodes for
            // the best feasible breaks in that class.
            let l = br.line_number(r);
            if l > old_l {
                if br.minimum_demerits < AWFUL_BAD && (old_l != br.easy_line || r == ACTIVE) {
                    if no_break_yet {
                        no_break_yet = false;
                        self.compute_break_width(br, cur_p, hyphenated);
                    }
                    // Insert a delta node to prepare for breaks at cur_p.
                    if br.is_delta(prev_r) {
                        let mut d = br.delta(prev_r);
                        for k in 0..NW {
                            d[k] = d[k] - br.cur_active_width[k] + br.break_width[k];
                        }
                        br.items[prev_r].entry = Entry::Delta(d);
                    } else if prev_r == ACTIVE {
                        br.active_width = br.break_width;
                    } else {
                        let mut d = [0; NW];
                        for k in 0..NW {
                            d[k] = br.break_width[k] - br.cur_active_width[k];
                        }
                        let q = br.alloc(Entry::Delta(d), r);
                        br.items[prev_r].next = q;
                        prev_prev_r = prev_r;
                        prev_r = q;
                    }
                    if br.adj_demerits.abs() >= AWFUL_BAD - br.minimum_demerits {
                        br.minimum_demerits = AWFUL_BAD - 1;
                    } else {
                        br.minimum_demerits += br.adj_demerits.abs();
                    }
                    for fit_class in VERY_LOOSE_FIT..=TIGHT_FIT {
                        if br.minimal_demerits[fit_class] <= br.minimum_demerits {
                            // Insert a new active node from best_place to cur_p.
                            br.pass_number += 1;
                            let left_pw = if br.protrude {
                                self.lb_left_protrusion(Some(cur_p), NodeRef::NULL)
                            } else {
                                0
                            };
                            br.passive.push(Passive {
                                cur_break: cur_p,
                                prev_break: br.best_place[fit_class],
                                serial: br.pass_number,
                                left_pw,
                            });
                            let pidx = br.passive.len() - 1;
                            let (short, glue) = if br.do_last_line_fit {
                                (br.best_pl_short[fit_class], br.best_pl_glue[fit_class])
                            } else {
                                (0, 0)
                            };
                            let q = br.alloc(
                                Entry::Active {
                                    passive: Some(pidx),
                                    line_number: br.best_pl_line[fit_class] + 1,
                                    fitness: fit_class,
                                    hyphenated,
                                    total_demerits: br.minimal_demerits[fit_class],
                                    short,
                                    glue,
                                },
                                r,
                            );
                            br.items[prev_r].next = q;
                            prev_r = q;
                            if br.tracing {
                                self.printer.print_nl("@@");
                                self.printer.print_int(i64::from(br.pass_number));
                                self.printer.print_str(": line ");
                                self.printer
                                    .print_int(i64::from(br.best_pl_line[fit_class]));
                                self.printer.print_char('.' as u32);
                                self.printer.print_int(fit_class as i64);
                                if hyphenated {
                                    self.printer.print_char('-' as u32);
                                }
                                self.printer.print_str(" t=");
                                self.printer
                                    .print_int(i64::from(br.minimal_demerits[fit_class]));
                                if br.do_last_line_fit {
                                    self.printer.print_str(" s=");
                                    self.printer.print_scaled(short);
                                    self.printer.print_str(if cur_p.is_null() {
                                        " a="
                                    } else {
                                        " g="
                                    });
                                    self.printer.print_scaled(glue);
                                }
                                self.printer.print_str(" -> @");
                                match br.best_place[fit_class] {
                                    None => self.printer.print_char('0' as u32),
                                    Some(pp) => {
                                        self.printer.print_int(i64::from(br.passive[pp].serial))
                                    }
                                }
                            }
                        }
                        br.minimal_demerits[fit_class] = AWFUL_BAD;
                    }
                    br.minimum_demerits = AWFUL_BAD;
                    // Insert a delta node to prepare for the next active node.
                    if r != ACTIVE {
                        let mut d = [0; NW];
                        for k in 0..NW {
                            d[k] = br.cur_active_width[k] - br.break_width[k];
                        }
                        let q = br.alloc(Entry::Delta(d), r);
                        br.items[prev_r].next = q;
                        prev_prev_r = prev_r;
                        prev_r = q;
                    }
                }
                if r == ACTIVE {
                    return;
                }
                // Compute the new line width.
                if l > br.easy_line {
                    line_width = br.second_width;
                    old_l = i32::MAX - 1;
                } else {
                    old_l = l;
                    line_width = if l > br.last_special_line {
                        br.second_width
                    } else {
                        match &br.par_shape {
                            None => br.first_width,
                            Some(s) => s[2 * (l as usize - 1) + 1],
                        }
                    };
                }
            }
            // Consider the demerits for a line from r to cur_p.
            let (r_passive, r_fitness, r_hyph, r_total, r_short, r_glue) = match br.items[r].entry {
                Entry::Active {
                    passive,
                    fitness,
                    hyphenated,
                    total_demerits,
                    short,
                    glue,
                    ..
                } => (passive, fitness, hyphenated, total_demerits, short, glue),
                _ => (None, DECENT_FIT, false, 0, 0, 0),
            };
            let mut artificial_demerits = false;
            let mut shortfall = line_width - br.cur_active_width[0];
            if br.protrude {
                let rp = *right_pw.get_or_insert_with(|| self.lb_right_protrusion(cur_p, br.head));
                let lp = match r_passive {
                    Some(i) => br.passive[i].left_pw,
                    None => br.first_left_pw,
                };
                shortfall += lp + rp;
            }
            if br.expand {
                // Font expansion takes up the shortfall first.
                let caw = &br.cur_active_width;
                if shortfall > 0 && caw[FONT_STRETCH] > 0 {
                    shortfall = (shortfall - caw[FONT_STRETCH]).max(0);
                } else if shortfall < 0 && caw[FONT_SHRINK] > 0 {
                    shortfall = (shortfall + caw[FONT_SHRINK]).min(0);
                }
            }
            let mut g = 0i32;
            let b: i32;
            let fit_class: usize;
            let caw = br.cur_active_width;
            'found: {
                if shortfall > 0 {
                    if caw[2] != 0 || caw[3] != 0 || caw[4] != 0 || caw[5] != 0 {
                        if br.do_last_line_fit {
                            if cur_p.is_null() {
                                // Perform computations for the last line.
                                'not_found: {
                                    if r_short == 0 || r_glue <= 0 {
                                        break 'not_found;
                                    }
                                    if caw[2] != br.fill_width[0]
                                        || caw[3] != br.fill_width[1]
                                        || caw[4] != br.fill_width[2]
                                        || caw[5] != br.fill_width[3]
                                    {
                                        break 'not_found;
                                    }
                                    g = if r_short > 0 { caw[1] } else { caw[6] };
                                    if g <= 0 {
                                        break 'not_found;
                                    }
                                    let md = retex_arith::MAX_DIMEN;
                                    g = match retex_arith::fract(g, r_short, r_glue, md) {
                                        Ok(v) => v,
                                        Err(_) => {
                                            if r_short > 0 {
                                                md
                                            } else {
                                                -md
                                            }
                                        }
                                    };
                                    if br.last_line_fit < 1000 {
                                        g = retex_arith::fract(g, br.last_line_fit, 1000, md)
                                            .unwrap_or(if r_short > 0 { md } else { -md });
                                    }
                                    if g > 0 {
                                        if g > shortfall {
                                            g = shortfall;
                                        }
                                        if g > 7_230_584 && caw[1] < 1_663_497 {
                                            b = INF_BAD;
                                            fit_class = VERY_LOOSE_FIT;
                                            break 'found;
                                        }
                                        b = retex_arith::badness(g, caw[1]);
                                        fit_class = if b > 12 {
                                            if b > 99 { VERY_LOOSE_FIT } else { LOOSE_FIT }
                                        } else {
                                            DECENT_FIT
                                        };
                                        break 'found;
                                    } else if g < 0 {
                                        if -g > caw[6] {
                                            g = -caw[6];
                                        }
                                        b = retex_arith::badness(-g, caw[6]);
                                        fit_class = if b > 12 { TIGHT_FIT } else { DECENT_FIT };
                                        break 'found;
                                    }
                                }
                            }
                            shortfall = 0;
                        }
                        b = 0;
                        fit_class = DECENT_FIT;
                    } else if shortfall > 7_230_584 && caw[1] < 1_663_497 {
                        b = INF_BAD;
                        fit_class = VERY_LOOSE_FIT;
                    } else {
                        b = retex_arith::badness(shortfall, caw[1]);
                        fit_class = if b > 12 {
                            if b > 99 { VERY_LOOSE_FIT } else { LOOSE_FIT }
                        } else {
                            DECENT_FIT
                        };
                    }
                } else {
                    b = if -shortfall > caw[6] {
                        INF_BAD + 1
                    } else {
                        retex_arith::badness(-shortfall, caw[6])
                    };
                    fit_class = if b > 12 { TIGHT_FIT } else { DECENT_FIT };
                }
                if br.do_last_line_fit {
                    // Adjust the additional data for the last line.
                    if cur_p.is_null() {
                        shortfall = 0;
                    }
                    g = if shortfall > 0 {
                        caw[1]
                    } else if shortfall < 0 {
                        caw[6]
                    } else {
                        0
                    };
                }
            }
            let node_r_stays_active;
            let mut deactivate = false;
            if b > INF_BAD || pi == EJECT_PENALTY {
                if br.final_pass
                    && br.minimum_demerits == AWFUL_BAD
                    && br.items[r].next == ACTIVE
                    && prev_r == ACTIVE
                {
                    artificial_demerits = true;
                } else if b > br.threshold {
                    deactivate = true;
                }
                node_r_stays_active = false;
            } else {
                prev_r = r;
                if b > br.threshold {
                    continue;
                }
                node_r_stays_active = true;
            }
            if !deactivate {
                // Record a new feasible break.
                let mut d: i32;
                if artificial_demerits {
                    d = 0;
                } else {
                    d = br.line_penalty + b;
                    d = if d.abs() >= 10000 { 100_000_000 } else { d * d };
                    if pi != 0 {
                        if pi > 0 {
                            d += pi * pi;
                        } else if pi > EJECT_PENALTY {
                            d -= pi * pi;
                        }
                    }
                    if hyphenated && r_hyph {
                        if !cur_p.is_null() {
                            d += br.double_hyphen_demerits;
                        } else {
                            d += br.final_hyphen_demerits;
                        }
                    }
                    if (fit_class as i32 - r_fitness as i32).abs() > 1 {
                        d += br.adj_demerits;
                    }
                }
                if br.tracing {
                    self.print_feasible_break(br, cur_p, r_passive, b, pi, d, artificial_demerits);
                }
                d += r_total;
                if d <= br.minimal_demerits[fit_class] {
                    br.minimal_demerits[fit_class] = d;
                    br.best_place[fit_class] = r_passive;
                    br.best_pl_line[fit_class] = l;
                    if br.do_last_line_fit {
                        br.best_pl_short[fit_class] = shortfall;
                        br.best_pl_glue[fit_class] = g;
                    }
                    if d < br.minimum_demerits {
                        br.minimum_demerits = d;
                    }
                }
                if node_r_stays_active {
                    continue;
                }
            }
            // Deactivate node r.
            let rn = br.items[r].next;
            br.items[prev_r].next = rn;
            br.release(r);
            if prev_r == ACTIVE {
                // Update the active widths, since the first active node has
                // been deleted.
                let r = br.items[ACTIVE].next;
                if let Entry::Delta(d) = br.items[r].entry {
                    for k in 0..NW {
                        br.active_width[k] += d[k];
                    }
                    br.cur_active_width = br.active_width;
                    let rn = br.items[r].next;
                    br.items[ACTIVE].next = rn;
                    br.release(r);
                }
            } else if br.is_delta(prev_r) {
                let r = br.items[prev_r].next;
                if r == ACTIVE {
                    let d = br.delta(prev_r);
                    for k in 0..NW {
                        br.cur_active_width[k] -= d[k];
                    }
                    br.items[prev_prev_r].next = ACTIVE;
                    br.release(prev_r);
                    prev_r = prev_prev_r;
                } else if let Entry::Delta(dr) = br.items[r].entry {
                    let mut dp_ = br.delta(prev_r);
                    for k in 0..NW {
                        br.cur_active_width[k] += dr[k];
                        dp_[k] += dr[k];
                    }
                    br.items[prev_r].entry = Entry::Delta(dp_);
                    let rn = br.items[r].next;
                    br.items[prev_r].next = rn;
                    br.release(r);
                }
            }
        }
    }

    /// Computes `break_width` for a break at `cur_p`.
    fn compute_break_width(&mut self, br: &mut Breaker, cur_p: NodeRef, hyphenated: bool) {
        br.break_width = br.background;
        let mut s = cur_p;
        if hyphenated && !cur_p.is_null() && self.nodes.id(cur_p) == id::DISC {
            let (_pre, post, rep) = self.nodes.disc_lists(cur_p);
            br.break_width[0] -= self.list_width(rep);
            br.break_width[0] += self.list_width(post);
            br.break_width[0] += br.disc_width;
            if br.expand {
                let r = self.list_font_stretch(rep, br.expand_kerns);
                let p = self.list_font_stretch(post, br.expand_kerns);
                br.break_width[FONT_STRETCH] += p.stretch - r.stretch + br.disc_fs.stretch;
                br.break_width[FONT_SHRINK] += p.shrink - r.shrink + br.disc_fs.shrink;
            }
            s = if post.is_null() {
                self.nodes.next(cur_p)
            } else {
                NodeRef::NULL
            };
        }
        while !s.is_null() {
            match self.nodes.data(s) {
                NodeData::Glue { spec, .. } => {
                    let g = *spec;
                    br.break_width[0] -= g.width;
                    br.break_width[1 + (g.stretch_order as usize).min(4)] -= g.stretch;
                    br.break_width[6] -= g.shrink;
                }
                NodeData::Penalty { .. } => {}
                NodeData::Math { .. } => br.break_width[0] -= self.nodes.width(s),
                NodeData::Kern { kern, .. } => {
                    if !matches!(self.nodes.subtype(s), kern_sub::USER | kern_sub::ITALIC) {
                        break;
                    }
                    br.break_width[0] -= *kern;
                }
                _ => break,
            }
            s = self.nodes.next(s);
        }
    }

    /// Prints a feasible break for `\tracingparagraphs`.
    #[allow(clippy::too_many_arguments)]
    fn print_feasible_break(
        &mut self,
        br: &mut Breaker,
        cur_p: NodeRef,
        r_passive: Option<usize>,
        b: i32,
        pi: i32,
        d: i32,
        artificial: bool,
    ) {
        if br.printed_node != cur_p {
            // Print the list between printed_node and cur_p.
            self.printer.print_nl("");
            let start = self.nodes.next(br.printed_node);
            if cur_p.is_null() {
                self.short_display(start);
            } else {
                let save = self.nodes.next(cur_p);
                self.nodes.set_next(cur_p, NodeRef::NULL);
                self.printer.print_nl("");
                self.short_display(start);
                self.nodes.set_next(cur_p, save);
            }
            br.printed_node = cur_p;
        }
        self.printer.print_nl("@");
        if cur_p.is_null() {
            self.print_esc_str("par");
        } else {
            match self.nodes.id(cur_p) {
                id::GLUE => {}
                id::PENALTY => self.print_esc_str("penalty"),
                id::DISC => self.print_esc_str("discretionary"),
                id::KERN => self.print_esc_str("kern"),
                _ => self.print_esc_str("math"),
            }
        }
        self.printer.print_str(" via @");
        match r_passive {
            None => self.printer.print_char('0' as u32),
            Some(p) => self.printer.print_int(i64::from(br.passive[p].serial)),
        }
        self.printer.print_str(" b=");
        if b > INF_BAD {
            self.printer.print_char('*' as u32);
        } else {
            self.printer.print_int(i64::from(b));
        }
        self.printer.print_str(" p=");
        self.printer.print_int(i64::from(pi));
        self.printer.print_str(" d=");
        if artificial {
            self.printer.print_char('*' as u32);
        } else {
            self.printer.print_int(i64::from(d));
        }
    }

    /// Justifies the lines and appends them to the vertical list
    /// (`post_line_break`).
    fn post_line_break(
        &mut self,
        br: &mut Breaker,
        best_bet: usize,
        best_line: i32,
        temp_head: NodeRef,
        p: &ParParams,
    ) {
        // Reverse the links of the relevant passive nodes.
        let mut breaks: Vec<NodeRef> = Vec::new();
        let mut q = match br.items[best_bet].entry {
            Entry::Active { passive, .. } => passive,
            _ => None,
        };
        while let Some(i) = q {
            breaks.push(br.passive[i].cur_break);
            q = br.passive[i].prev_break;
        }
        breaks.reverse();
        let prev_graf = self.cur_list().prev_graf;
        let mut cur_line = prev_graf + 1;
        let ls = p.left_skip;
        let ls_nonzero = ls.width != 0 || ls.stretch != 0 || ls.shrink != 0;
        // Observed: the lines get the direction of the paragraph's local
        // par node (its \pardir when it began), not the current one.
        let first = self.nodes.next(temp_head);
        let pardir = if first.is_null() {
            p.par_dir
        } else if let NodeData::LocalPar { dir, .. } = self.nodes.data(first) {
            *dir
        } else {
            p.par_dir
        };
        let protrude = p.protrude_chars > 0;
        let adjust_spacing = p.adjust_spacing > 0;
        // The local boxes of the paragraph (from the last local par node
        // seen).
        let mut local_left = NodeRef::NULL;
        let mut local_right = NodeRef::NULL;
        let mut post_disc_break = false;
        // Directions open at the last break (see `dirs`).
        let mut open_dirs: Vec<i8> = Vec::new();
        for (bi, &cb) in breaks.iter().enumerate() {
            // Reopen the directions of the previous line.
            let line_first = self.nodes.next(temp_head);
            if let Some((h, t)) = self.begin_dir_nodes(&open_dirs) {
                self.nodes.link(temp_head, h);
                self.nodes.link(t, line_first);
                if line_first.is_null() {
                    self.nodes.set_next(t, NodeRef::NULL);
                }
            }
            self.track_open_dirs(line_first, cb, &mut open_dirs);
            // Track local par nodes in this line.
            {
                let mut s = self.nodes.next(temp_head);
                while !s.is_null() && s != cb {
                    if let NodeData::LocalPar {
                        box_left,
                        box_right,
                        ..
                    } = self.nodes.data(s)
                    {
                        local_left = *box_left;
                        local_right = *box_right;
                    }
                    s = self.nodes.next(s);
                }
            }
            // Modify the end of the line to reflect the nature of the
            // break and to include \rightskip.
            let mut q = cb;
            let mut disc_break = false;
            post_disc_break = false;
            let mut rightskip_done = false;
            if !q.is_null() {
                match self.nodes.id(q) {
                    id::GLUE => {
                        let rs = p.right_skip;
                        if let NodeData::Glue { spec, leader } = self.nodes.data_mut(q) {
                            *spec = rs;
                            let l = std::mem::take(leader);
                            self.nodes.flush_list(l);
                        }
                        self.nodes.set_subtype(q, glue_sub::RIGHT_SKIP);
                        rightskip_done = true;
                    }
                    id::DISC => {
                        // Change the discretionary to compulsory: LuaTeX
                        // keeps the (emptied) node after the pre-break
                        // text.
                        let (pre, post, rep) = self.nodes.disc_lists(q);
                        self.nodes
                            .set_disc_lists(q, (NodeRef::NULL, NodeRef::NULL, NodeRef::NULL));
                        self.nodes.flush_list(rep);
                        let r = self.nodes.next(q);
                        if !post.is_null() {
                            let t = self.nodes.tail_of(post);
                            self.nodes.link(q, post);
                            self.nodes.link(t, r);
                            if r.is_null() {
                                self.nodes.set_next(t, NodeRef::NULL);
                            }
                            post_disc_break = true;
                        }
                        if !pre.is_null() {
                            let before = self.find_prev_in(temp_head, q);
                            let t = self.nodes.tail_of(pre);
                            self.nodes.link(before, pre);
                            self.nodes.link(t, q);
                        }
                        disc_break = true;
                    }
                    id::KERN | id::MATH => match self.nodes.data_mut(q) {
                        NodeData::Kern { kern, .. } => *kern = 0,
                        NodeData::Math { surround, glue } => {
                            *surround = 0;
                            *glue = Glue::ZERO;
                        }
                        _ => {}
                    },
                    _ => {}
                }
            } else {
                q = self.nodes.tail_of(temp_head);
            }
            let q0 = q;
            if !rightskip_done {
                let r = self.new_glue_node(p.right_skip, glue_sub::RIGHT_SKIP);
                // Observed: with the attributes of the node before it.
                if !q.is_null() && q != temp_head {
                    let a = self.nodes.attr(q).cloned();
                    self.nodes.set_attr(r, a);
                }
                let n = self.nodes.next(q);
                self.nodes.link(q, r);
                self.nodes.link(r, n);
                if n.is_null() {
                    self.nodes.set_next(r, NodeRef::NULL);
                }
                q = r;
            }
            if let Some((h, t)) = self.end_dir_nodes(&open_dirs) {
                // Close the open directions before \rightskip, or on the
                // last line before \parfillskip (after line breaking, so
                // that they make no breakpoint).
                let mut at = q;
                if bi + 1 == breaks.len() {
                    let p = self.find_prev_in(temp_head, q);
                    if self.nodes.id(p) == id::GLUE
                        && self.nodes.subtype(p) == glue_sub::PAR_FILL_SKIP
                    {
                        at = p;
                    }
                }
                let p = self.find_prev_in(temp_head, at);
                self.nodes.link(p, h);
                self.nodes.link(t, at);
            }
            if !local_right.is_null() {
                // The right local box goes before \rightskip (and before
                // \parfillskip on the last line).
                let mut target = q;
                if bi + 1 == breaks.len() {
                    let p = self.find_prev_in(temp_head, q);
                    if self.nodes.id(p) == id::GLUE
                        && self.nodes.subtype(p) == glue_sub::PAR_FILL_SKIP
                    {
                        target = p;
                    }
                }
                let b = self.nodes.copy_node(local_right);
                let p = self.find_prev_in(temp_head, target);
                self.nodes.link(p, b);
                self.nodes.link(b, target);
            }
            if protrude {
                self.insert_right_margin_kern(temp_head, q0);
            }
            // Put the \leftskip glue at the left and detach this line.
            let r = self.nodes.next(q);
            self.nodes.set_next(q, NodeRef::NULL);
            let mut line = self.nodes.next(temp_head);
            self.nodes.set_next(temp_head, r);
            if !r.is_null() {
                self.nodes.set_prev(r, temp_head);
            }
            if !local_left.is_null() {
                let b = self.nodes.copy_node(local_left);
                self.nodes.link(b, line);
                line = b;
            }
            if protrude {
                let k = self.left_margin_kern(line);
                if !k.is_null() {
                    self.nodes.link(k, line);
                    line = k;
                }
            }
            if ls_nonzero {
                let g = self.new_glue_node(ls, glue_sub::LEFT_SKIP);
                // Observed: with the attributes of the line's first node.
                if !line.is_null() {
                    let a = self.nodes.attr(line).cloned();
                    self.nodes.set_attr(g, a);
                }
                self.nodes.link(g, line);
                line = g;
            }
            if !line.is_null() {
                self.nodes.set_prev(line, NodeRef::NULL);
            }
            // Call the packaging subroutine.
            let (cur_width, cur_indent) = if cur_line > br.last_special_line {
                (br.second_width, br.second_indent)
            } else {
                match &br.par_shape {
                    None => (br.first_width, br.first_indent),
                    Some(s) => (
                        s[2 * (cur_line as usize - 1) + 1],
                        s[2 * (cur_line as usize - 1)],
                    ),
                }
            };
            self.start_adjust_lists();
            // A line whose expansion ratio rounds to 0 keeps its natural
            // glue (see `expand_line`).
            let natural = adjust_spacing && self.expand_line(line, cur_width);
            // The line has the paragraph's direction while it is packed
            // (observed in the box shown by an overfull line warning).
            self.pack_dir = pardir;
            let just_box = if natural {
                let b = self.hpack(line, PackSpec::Additional(0));
                if let Some(bd) = self.nodes.box_data_mut(b) {
                    bd.width = cur_width;
                }
                b
            } else {
                self.hpack(line, PackSpec::Exactly(cur_width))
            };
            self.ts.just_box = just_box;
            self.nodes.set_subtype(just_box, 1);
            if let Some(b) = self.nodes.box_data_mut(just_box) {
                b.shift = cur_indent;
                b.dir = pardir;
            }
            // Append the new box to the current vertical list, telling
            // contribute_filter (observed: "box", then "adjust" for
            // \vadjust material).
            let pre_h = self.ts.pre_adjust_head;
            if !pre_h.is_null() && !self.nodes.next(pre_h).is_null() {
                self.notify_callback("contribute_filter", "pre_adjust");
            }
            self.append_adjust_material(pre_h);
            self.notify_callback("contribute_filter", "box");
            self.append_to_vlist(just_box);
            let adj_h = self.ts.adjust_head;
            if !adj_h.is_null() && !self.nodes.next(adj_h).is_null() {
                self.notify_callback("contribute_filter", "adjust");
            }
            self.append_adjust_material(adj_h);
            self.ts.adjust_tail = None;
            self.ts.pre_adjust_tail = None;
            // Append a penalty node, if a nonzero penalty is appropriate.
            if cur_line + 1 != best_line {
                let mut pen = match &p.interline_penalties {
                    Some(a) if !a.is_empty() => {
                        let n = a.len() as i32;
                        a[(cur_line.min(n) - 1).max(0) as usize]
                    }
                    _ => p.interline_penalty,
                };
                match &p.club_penalties {
                    Some(a) if !a.is_empty() => {
                        let n = a.len() as i32;
                        let r = (cur_line - prev_graf).min(n);
                        pen += a[(r - 1).max(0) as usize];
                    }
                    _ => {
                        if cur_line == prev_graf + 1 {
                            pen += p.club_penalty;
                        }
                    }
                }
                match &p.widow_penalties {
                    Some(a) if !a.is_empty() => {
                        let n = a.len() as i32;
                        let r = (best_line - cur_line - 1).min(n);
                        pen += a[(r - 1).max(0) as usize];
                    }
                    _ => {
                        if cur_line + 2 == best_line {
                            pen += p.widow_penalty;
                        }
                    }
                }
                if disc_break {
                    pen += p.broken_penalty;
                }
                if pen != 0 {
                    let r = self.new_penalty_node(pen);
                    // Observed: subtype 1 (`linebreakpenalty`).
                    self.nodes.set_subtype(r, 1);
                    self.tail_append(r);
                }
            }
            cur_line += 1;
            // Prune unwanted nodes at the beginning of the next line.
            if bi + 1 < breaks.len() && !post_disc_break {
                let next_break = breaks[bi + 1];
                let mut r = temp_head;
                loop {
                    let q = self.nodes.next(r);
                    if q.is_null() || q == next_break {
                        break;
                    }
                    let t = self.nodes.id(q);
                    if t == id::GLYPH || crate::page::precedes_break(t) {
                        break;
                    }
                    if t == id::KERN
                        && !matches!(self.nodes.subtype(q), kern_sub::USER | kern_sub::ITALIC)
                    {
                        break;
                    }
                    if !matches!(t, id::GLUE | id::KERN | id::MATH | id::PENALTY) {
                        break;
                    }
                    r = q;
                }
                if r != temp_head {
                    let q = self.nodes.next(r);
                    self.nodes.set_next(r, NodeRef::NULL);
                    let first = self.nodes.next(temp_head);
                    self.nodes.flush_list(first);
                    self.nodes.link(temp_head, q);
                    if q.is_null() {
                        self.nodes.set_next(temp_head, NodeRef::NULL);
                    }
                }
            }
        }
        let _ = post_disc_break;
        if !self.nodes.next(temp_head).is_null() {
            // Should not happen; keep the material rather than abort.
            let rest = self.nodes.next(temp_head);
            self.nodes.set_next(temp_head, NodeRef::NULL);
            self.nodes.flush_list(rest);
        }
        self.cur_list_mut().prev_graf = best_line - 1;
    }

    /// Appends the material collected in an adjustment list.
    fn append_adjust_material(&mut self, head: NodeRef) {
        if head.is_null() {
            return;
        }
        let first = self.nodes.next(head);
        if first.is_null() {
            return;
        }
        let tail = self.cur_list().tail;
        self.nodes.link(tail, first);
        let t = self.nodes.tail_of(first);
        self.cur_list_mut().tail = t;
        self.nodes.set_next(head, NodeRef::NULL);
    }
}