retex-engine 1.3.0-alpha.2

//! Breaking vertical lists into pages: `\vsplit`, the page builder, the
//! output routine and `\shipout` (*TeX: The Program* §967–§1028 and
//! §638, with e-TeX's mark classes and saved discards).
//!
//! `\shipout` calls the backend through [`crate::typeset::ShipoutHook`];
//! without a hook the built-in DVI writer is used, which is what LuaTeX
//! does in IniTeX mode (`\outputmode=0`).

use crate::Engine;
use crate::build::PackSpec;
use crate::eqtb::{Loc, Val};
use crate::glue::Glue;
use crate::input::{Level, TokKind};
use crate::maincontrol::{IGNORE_DEPTH, Mode};
use crate::nodes::{NodeData, NodeRef, glue_sub, id};
use crate::primitives_gen::{assign_dimen as dp, assign_glue as gp, assign_int as ip};
use crate::save::GroupCode;
use crate::typeset::{
    AWFUL_BAD, DEPLORABLE, EJECT_PENALTY, INF_BAD, INF_PENALTY, PageContents, PageIns, mark_code,
};

/// TeX's `precedes_break`: whether a glue node after `p` is a legal
/// breakpoint (LuaTeX node numbering, `type(p) < math_node`).
#[inline]
pub fn precedes_break(t: u8) -> bool {
    t < id::MATH
}

impl Engine {
    // ----- pruning and vertical breaking ---------------------------------

    /// Removes glue, kerns and penalties before the first box or rule and
    /// inserts `\splittopskip` glue (`prune_page_top`). With `save`, the
    /// removed items go to `\splitdiscards`.
    pub fn prune_page_top(&mut self, p: NodeRef, save: bool) -> NodeRef {
        let head = self.nodes.new_temp();
        self.nodes.link(head, p);
        let mut prev_p = head;
        let mut p = p;
        let mut r = NodeRef::NULL;
        while !p.is_null() {
            match self.nodes.id(p) {
                id::HLIST | id::VLIST | id::RULE => {
                    let mut g = self.eqtb.glue(gp::SPLITTOPSKIP);
                    let h = self.node_height(p);
                    g.width = if g.width > h { g.width - h } else { 0 };
                    let q = self.new_glue_node(g, glue_sub::SPLIT_TOP_SKIP);
                    self.nodes.link(prev_p, q);
                    self.nodes.link(q, p);
                    break;
                }
                id::GLUE | id::KERN | id::PENALTY => {
                    let q = p;
                    p = self.nodes.next(q);
                    self.nodes.set_next(q, NodeRef::NULL);
                    self.nodes.set_next(prev_p, p);
                    if !p.is_null() {
                        self.nodes.set_prev(p, prev_p);
                    }
                    if save {
                        if self.ts.disc_ptr[3].is_null() {
                            self.ts.disc_ptr[3] = q;
                        } else {
                            self.nodes.link(r, q);
                        }
                        r = q;
                    } else {
                        self.nodes.flush_list(q);
                    }
                }
                _ => {
                    prev_p = p;
                    p = self.nodes.next(prev_p);
                }
            }
        }
        let first = self.nodes.next(head);
        self.nodes.free(head);
        if !first.is_null() {
            self.nodes.set_prev(first, NodeRef::NULL);
        }
        first
    }

    /// Finds the best place to break a vlist for height `h` and maximum
    /// depth `d` (`vert_break`); returns the break node (null for the end)
    /// and `best_height_plus_depth`.
    pub fn vert_break(&mut self, p: NodeRef, h: i32, d: i32) -> (NodeRef, i32) {
        let mut prev_p = p;
        let mut p = p;
        let mut least_cost = AWFUL_BAD;
        let mut best_place = NodeRef::NULL;
        let mut best_hpd = 0;
        let mut cur_height = 0i32;
        let mut stretch = [0i32; 5];
        let mut shrink = 0i32;
        let mut prev_dp = 0i32;
        loop {
            // Determine whether p is a legal breakpoint and its penalty.
            let mut pi: Option<i32> = None;
            let mut update = false;
            if p.is_null() {
                pi = Some(EJECT_PENALTY);
            } else {
                match self.nodes.id(p) {
                    id::HLIST | id::VLIST | id::RULE => {
                        cur_height += prev_dp + self.node_height(p);
                        prev_dp = self.node_depth(p);
                    }
                    id::GLUE => {
                        if precedes_break(self.nodes.id(prev_p)) {
                            pi = Some(0);
                        } else {
                            update = true;
                        }
                    }
                    id::KERN => {
                        let n = self.nodes.next(p);
                        let t = if n.is_null() {
                            id::PENALTY
                        } else {
                            self.nodes.id(n)
                        };
                        if t == id::GLUE {
                            pi = Some(0);
                        } else {
                            update = true;
                        }
                    }
                    id::PENALTY => pi = Some(self.nodes.penalty(p)),
                    _ => {}
                }
            }
            if let Some(pi) = pi {
                if pi < INF_PENALTY {
                    let b = if cur_height < h {
                        if stretch[1..].iter().any(|&s| s != 0) {
                            0
                        } else {
                            retex_arith::badness(h - cur_height, stretch[0])
                        }
                    } else if cur_height - h > shrink {
                        AWFUL_BAD
                    } else {
                        retex_arith::badness(cur_height - h, shrink)
                    };
                    let b = if b < AWFUL_BAD {
                        if pi <= EJECT_PENALTY {
                            pi
                        } else if b < INF_BAD {
                            b + pi
                        } else {
                            DEPLORABLE
                        }
                    } else {
                        b
                    };
                    if b <= least_cost {
                        best_place = p;
                        least_cost = b;
                        best_hpd = cur_height + prev_dp;
                    }
                    if b == AWFUL_BAD || pi <= EJECT_PENALTY {
                        return (best_place, best_hpd);
                    }
                }
                let t = self.nodes.id(p);
                if t == id::GLUE || t == id::KERN {
                    update = true;
                }
            }
            if update {
                if self.nodes.id(p) == id::KERN {
                    cur_height += prev_dp + self.nodes.width(p);
                } else {
                    let mut q = self.nodes.glue_spec(p);
                    stretch[(q.stretch_order as usize).min(4)] += q.stretch;
                    shrink += q.shrink;
                    if q.shrink_order != 0 && q.shrink != 0 {
                        const MSG: &str = "Infinite glue shrinkage found in box being split";
                        if self.eqtb.int(ip::IGNOREPRIMITIVEERROR) & 1 != 0 {
                            // LuaTeX's \ignoreprimitiveerror bit 1 turns
                            // this error (only) into a log line.
                            self.printer.print_nl("ignored error ");
                            self.printer.print_str(MSG);
                        } else {
                            self.print_err(MSG);
                            self.help(&[
                                "The box you are \\vsplitting contains some infinitely",
                                "shrinkable glue, e.g., `\\vss' or `\\vskip 0pt minus 1fil'.",
                                "Such glue doesn't belong there; but you can safely proceed,",
                                "since the offensive shrinkability has been made finite.",
                            ]);
                            self.error();
                        }
                        q.shrink_order = 0;
                        if let NodeData::Glue { spec, .. } = self.nodes.data_mut(p) {
                            spec.shrink_order = 0;
                        }
                    }
                    cur_height += prev_dp + q.width;
                }
                prev_dp = 0;
            }
            if prev_dp > d {
                cur_height = cur_height + prev_dp - d;
                prev_dp = d;
            }
            prev_p = p;
            p = self.nodes.next(prev_p);
        }
    }

    /// `\vsplit n to h` (`vsplit`).
    pub fn vsplit(&mut self, n: u32, h: i32) -> NodeRef {
        let v = self.eqtb.boxes[n as usize].val;
        let sd = std::mem::take(&mut self.ts.disc_ptr[3]);
        self.nodes.flush_list(sd);
        for m in self.marks.classes.values_mut() {
            m[mark_code::SPLIT_FIRST] = None;
            m[mark_code::SPLIT_BOT] = None;
        }
        if v.is_null() {
            return NodeRef::NULL;
        }
        if self.nodes.id(v) != id::VLIST {
            self.print_err("");
            self.print_esc_str("vsplit");
            self.printer.print_str(" needs a ");
            self.print_esc_str("vbox");
            self.help(&[
                "The box you are trying to split is an \\hbox.",
                "i can't split such a box, so I''ll leave it alone.",
            ]);
            self.error();
            return NodeRef::NULL;
        }
        let smd = self.eqtb.dimen(dp::SPLITMAXDEPTH);
        let list = self.nodes.list_ptr(v);
        let (q, _) = self.vert_break(list, h, smd);
        // Look at the marks before the break and cut the list there.
        let mut p = list;
        if p == q {
            self.nodes.set_list_ptr(v, NodeRef::NULL);
        } else {
            loop {
                if let NodeData::Mark { class, mark } = self.nodes.data(p) {
                    let (c, m) = (*class, mark.clone());
                    let e = self.marks.classes.entry(c).or_default();
                    if e[mark_code::SPLIT_FIRST].is_none() {
                        e[mark_code::SPLIT_FIRST] = Some(m.clone());
                    }
                    e[mark_code::SPLIT_BOT] = Some(m);
                }
                let nx = self.nodes.next(p);
                if nx == q {
                    self.nodes.set_next(p, NodeRef::NULL);
                    break;
                }
                p = nx;
            }
        }
        let save = self.eqtb.int(ip::SAVINGVDISCARDS) > 0;
        let q = self.prune_page_top(q, save);
        let p = self.nodes.list_ptr(v);
        self.nodes.set_list_ptr(v, NodeRef::NULL);
        self.nodes.free(v);
        self.eqtb.boxes[n as usize].val = if q.is_null() {
            NodeRef::NULL
        } else {
            self.vpack(q, PackSpec::NATURAL)
        };
        self.vpackage(p, PackSpec::Exactly(h), smd)
    }

    // ----- the page builder ----------------------------------------------

    /// Prints a box being deleted and voids the register (`box_error`).
    fn box_error(&mut self, n: u32) {
        self.error();
        self.begin_diagnostic();
        self.printer.print_nl("The following box has been deleted:");
        let b = self.eqtb.boxes[n as usize].val;
        self.show_box(b);
        self.end_diagnostic(true);
        self.nodes.flush_list(b);
        self.eqtb.boxes[n as usize].val = NodeRef::NULL;
    }

    /// Makes sure box `n` is not an hbox (`ensure_vbox`).
    fn ensure_vbox(&mut self, n: u32) {
        let p = self.eqtb.boxes[n as usize].val;
        if !p.is_null() && self.nodes.id(p) == id::HLIST {
            self.print_err("Insertions can only be added to a vbox");
            self.help(&[
                "Tut tut: You're trying to \\insert into a",
                "\\box register that now contains an \\hbox.",
                "Proceed, and I'll discard its present contents.",
            ]);
            self.box_error(n);
        }
    }

    /// Freezes `\vsize` and `\maxdepth` for the page (`freeze_page_specs`).
    fn freeze_page_specs(&mut self, s: PageContents) {
        self.page.contents = s;
        self.page.so_far = [0; 8];
        self.page.fi_stretch = 0;
        self.page.so_far[0] = self.eqtb.dimen(dp::VSIZE);
        self.page.max_depth = self.eqtb.dimen(dp::MAXDEPTH);
        self.page.least_cost = AWFUL_BAD;
        if self.eqtb.int(ip::TRACINGPAGES) > 0 {
            self.begin_diagnostic();
            self.printer.print_nl("%% goal height=");
            self.printer.print_scaled(self.page.so_far[0]);
            self.printer.print_str(", max depth=");
            self.printer.print_scaled(self.page.max_depth);
            self.end_diagnostic(false);
        }
    }

    /// Starts a fresh current page.
    fn start_new_page(&mut self) {
        self.page.contents = PageContents::Empty;
        self.page.page_tail = self.page.page_head;
        self.nodes.set_next(self.page.page_head, NodeRef::NULL);
        self.page.last_glue = None;
        self.page.last_penalty = 0;
        self.page.last_kern = 0;
        self.page.last_node_type = -1;
        self.page.so_far[7] = 0;
        self.page.max_depth = 0;
    }

    /// Sets the tail of the contribution list.
    #[inline]
    fn set_contrib_tail(&mut self, t: NodeRef) {
        self.nest[0].tail = t;
    }

    /// Appends contributions to the current page (`build_page`).
    pub fn build_page(&mut self) {
        let ch = self.page.contrib_head;
        if self.nodes.next(ch).is_null() || self.ts.output_active {
            return;
        }
        loop {
            let p = self.nodes.next(ch);
            if p.is_null() {
                break;
            }
            // Update last_glue, last_penalty, last_kern, last_node_type.
            self.page.last_penalty = 0;
            self.page.last_kern = 0;
            let t = self.nodes.id(p);
            self.page.last_node_type = crate::typeset::etex_node_type(t, self.nodes.subtype(p));
            if t == id::GLUE {
                self.page.last_glue = Some(self.nodes.glue_spec(p));
            } else {
                self.page.last_glue = None;
                if t == id::PENALTY {
                    self.page.last_penalty = self.nodes.penalty(p);
                } else if t == id::KERN {
                    self.page.last_kern = self.nodes.width(p);
                }
            }
            // Move node p to the current page.
            enum Act {
                Contribute,
                UpdateHeights,
                Recycle,
                Break(i32),
            }
            let contents = self.page.contents;
            let act = match t {
                id::HLIST | id::VLIST | id::RULE => {
                    if contents < PageContents::BoxThere {
                        // Initialize the page and insert \topskip glue.
                        if contents == PageContents::Empty {
                            self.freeze_page_specs(PageContents::BoxThere);
                        } else {
                            self.page.contents = PageContents::BoxThere;
                        }
                        let mut g = self.eqtb.glue(gp::TOPSKIP);
                        let h = self.node_height(p);
                        g.width = if g.width > h { g.width - h } else { 0 };
                        let q = self.new_glue_node(g, glue_sub::TOP_SKIP);
                        self.nodes.link(q, p);
                        self.nodes.link(ch, q);
                        continue;
                    }
                    self.page.so_far[1] += self.page.so_far[7] + self.node_height(p);
                    self.page.so_far[7] = self.node_depth(p);
                    Act::Contribute
                }
                id::GLUE => {
                    if contents < PageContents::BoxThere {
                        Act::Recycle
                    } else if precedes_break(self.nodes.id(self.page.page_tail)) {
                        Act::Break(0)
                    } else {
                        Act::UpdateHeights
                    }
                }
                id::KERN => {
                    if contents < PageContents::BoxThere {
                        Act::Recycle
                    } else {
                        let n = self.nodes.next(p);
                        if n.is_null() {
                            return;
                        } else if self.nodes.id(n) == id::GLUE {
                            Act::Break(0)
                        } else {
                            Act::UpdateHeights
                        }
                    }
                }
                id::PENALTY => {
                    if contents < PageContents::BoxThere {
                        Act::Recycle
                    } else {
                        Act::Break(self.nodes.penalty(p))
                    }
                }
                id::INS => {
                    self.append_insertion(p);
                    Act::Contribute
                }
                id::MARK | id::WHATSIT | id::BOUNDARY => Act::Contribute,
                // Observed: other nodes (Lua code can put a glyph in a
                // vertical list) end the run.
                _ => self.luatex_fatal(
                    "pagebuilder",
                    &format!("invalid node of type {t} in vertical mode"),
                ),
            };
            let mut update = matches!(act, Act::UpdateHeights);
            match act {
                Act::Recycle => {
                    let n = self.nodes.next(p);
                    self.nodes.set_next(ch, n);
                    self.nodes.set_next(p, NodeRef::NULL);
                    if self.eqtb.int(ip::SAVINGVDISCARDS) > 0 {
                        if self.ts.disc_ptr[2].is_null() {
                            self.ts.disc_ptr[2] = p;
                        } else {
                            let t = self.ts.disc_ptr[1];
                            self.nodes.link(t, p);
                        }
                        self.ts.disc_ptr[1] = p;
                    } else {
                        self.nodes.flush_list(p);
                    }
                    continue;
                }
                Act::Break(pi) => {
                    if pi < INF_PENALTY {
                        let b = self.page_badness();
                        let ip_ = self.insert_penalties;
                        let mut c = if b < AWFUL_BAD {
                            if pi <= EJECT_PENALTY {
                                pi
                            } else if b < INF_BAD {
                                b + pi + ip_
                            } else {
                                DEPLORABLE
                            }
                        } else {
                            b
                        };
                        if ip_ >= 10000 {
                            c = AWFUL_BAD;
                        }
                        if self.eqtb.int(ip::TRACINGPAGES) > 0 {
                            self.begin_diagnostic();
                            self.printer.print_nl("%");
                            self.printer.print_str(" t=");
                            self.print_totals();
                            self.printer.print_str(" g=");
                            self.printer.print_scaled(self.page.so_far[0]);
                            self.printer.print_str(" b=");
                            if b == AWFUL_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(" c=");
                            if c == AWFUL_BAD {
                                self.printer.print_char('*' as u32);
                            } else {
                                self.printer.print_int(i64::from(c));
                            }
                            if c <= self.page.least_cost {
                                self.printer.print_char('#' as u32);
                            }
                            self.end_diagnostic(false);
                        }
                        if c <= self.page.least_cost {
                            self.page.best_break = p;
                            self.page.best_size = self.page.so_far[0];
                            self.page.best_so_far = self.page.so_far;
                            self.page.best_infinite = self.page.fi_stretch != 0
                                || self.page.so_far[3..6].iter().any(|&s| s != 0);
                            self.page.least_cost = c;
                            for r in self.page.ins.iter_mut() {
                                r.best_ins_ptr = r.last_ins_ptr;
                            }
                        }
                        if c == AWFUL_BAD || pi <= EJECT_PENALTY {
                            self.fire_up(p);
                            if self.ts.output_active {
                                return;
                            }
                            // The page has been shipped out by the default
                            // output routine.
                            continue;
                        }
                    }
                    if t == id::GLUE || t == id::KERN {
                        update = true;
                    }
                }
                _ => {}
            }
            if update {
                if t == id::KERN {
                    self.page.so_far[1] += self.page.so_far[7] + self.nodes.width(p);
                } else {
                    let q = self.nodes.glue_spec(p);
                    *self.page.stretch_mut(q.stretch_order) += q.stretch;
                    self.page.so_far[6] += q.shrink;
                    if q.shrink_order != 0 && q.shrink != 0 {
                        self.print_err("Infinite glue shrinkage found on current page");
                        self.help(&[
                            "The page about to be output contains some infinitely",
                            "shrinkable glue, e.g., `\\vss' or `\\vskip 0pt minus 1fil'.",
                            "Such glue doesn't belong there; but you can safely proceed,",
                            "since the offensive shrinkability has been made finite.",
                        ]);
                        self.error();
                        if let NodeData::Glue { spec, .. } = self.nodes.data_mut(p) {
                            spec.shrink_order = 0;
                        }
                    }
                    self.page.so_far[1] += self.page.so_far[7] + q.width;
                }
                self.page.so_far[7] = 0;
            }
            // contribute: make sure page_max_depth is not exceeded.
            if self.page.so_far[7] > self.page.max_depth {
                self.page.so_far[1] += self.page.so_far[7] - self.page.max_depth;
                self.page.so_far[7] = self.page.max_depth;
            }
            // Link node p into the current page.
            let n = self.nodes.next(p);
            let pt = self.page.page_tail;
            self.nodes.link(pt, p);
            self.page.page_tail = p;
            self.nodes.set_next(ch, n);
            if !n.is_null() {
                self.nodes.set_prev(n, ch);
            }
            self.nodes.set_next(p, NodeRef::NULL);
        }
        // Make the contribution list empty.
        self.set_contrib_tail(ch);
    }

    /// The badness of the current page.
    fn page_badness(&self) -> i32 {
        let s = &self.page.so_far;
        let (goal, total) = (s[0], s[1]);
        if total < goal {
            if self.page.fi_stretch != 0 || s[3] != 0 || s[4] != 0 || s[5] != 0 {
                0
            } else {
                retex_arith::badness(goal - total, s[2])
            }
        } else if total - goal > s[6] {
            AWFUL_BAD
        } else {
            retex_arith::badness(total - goal, s[6])
        }
    }

    /// Appends an insertion to the current page (§1008).
    fn append_insertion(&mut self, p: NodeRef) {
        if self.page.contents == PageContents::Empty {
            self.freeze_page_specs(PageContents::InsertsOnly);
        }
        let n = u32::from(self.nodes.subtype(p));
        let (pheight, pdepth, pcost, plist) = match self.nodes.data(p) {
            NodeData::Ins {
                height,
                depth,
                cost,
                head,
                ..
            } => (*height, *depth, *cost, *head),
            _ => return,
        };
        let idx = match self.page.ins.iter().position(|r| r.n >= n) {
            Some(i) if self.page.ins[i].n == n => i,
            pos => {
                // Create a page insertion record.
                let i = pos.unwrap_or(self.page.ins.len());
                self.ensure_vbox(n);
                let b = self.eqtb.boxes[n as usize].val;
                let height = if b.is_null() {
                    0
                } else {
                    self.node_height(b) + self.node_depth(b)
                };
                self.page.ins.insert(
                    i,
                    PageIns {
                        n,
                        split_up: false,
                        height,
                        broken_ptr: NodeRef::NULL,
                        broken_ins: NodeRef::NULL,
                        last_ins_ptr: NodeRef::NULL,
                        best_ins_ptr: NodeRef::NULL,
                    },
                );
                let q = self.eqtb.skip[n as usize].val;
                let c = self.eqtb.count[n as usize].val;
                let h = if c == 1000 {
                    height
                } else {
                    x_over_n(height, 1000).wrapping_mul(c)
                };
                self.page.so_far[0] = self.page.so_far[0] - h - q.width;
                *self.page.stretch_mut(q.stretch_order) += q.stretch;
                self.page.so_far[6] += q.shrink;
                if q.shrink_order != 0 && q.shrink != 0 {
                    self.print_err("Infinite glue shrinkage inserted from ");
                    self.print_esc_str("skip");
                    self.printer.print_int(i64::from(n));
                    self.help(&[
                        "The correction glue for page breaking with insertions",
                        "must have finite shrinkability. But you may proceed,",
                        "since the offensive shrinkability has been made finite.",
                    ]);
                    self.error();
                }
                i
            }
        };
        if self.page.ins[idx].split_up {
            self.insert_penalties += pcost;
            return;
        }
        self.page.ins[idx].last_ins_ptr = p;
        let s = &self.page.so_far;
        let delta = s[0] - s[1] - s[7] + s[6];
        let c = self.eqtb.count[n as usize].val;
        let h = if c == 1000 {
            pheight
        } else {
            x_over_n(pheight, 1000).wrapping_mul(c)
        };
        let dimen_n = self.eqtb.dimen[n as usize].val;
        if (h <= 0 || h <= delta) && pheight + self.page.ins[idx].height <= dimen_n {
            self.page.so_far[0] -= h;
            self.page.ins[idx].height += pheight;
        } else {
            // Find the best way to split the insertion.
            let mut w = if c <= 0 {
                retex_arith::MAX_DIMEN
            } else {
                let mut w = self.page.so_far[0] - self.page.so_far[1] - self.page.so_far[7];
                if c != 1000 {
                    w = x_over_n(w, c).wrapping_mul(1000);
                }
                w
            };
            if w > dimen_n - self.page.ins[idx].height {
                w = dimen_n - self.page.ins[idx].height;
            }
            let (q, mut bhpd) = self.vert_break(plist, w, pdepth);
            self.page.ins[idx].height += bhpd;
            if self.eqtb.int(ip::TRACINGPAGES) > 0 {
                self.begin_diagnostic();
                self.printer.print_nl("% split");
                self.printer.print_int(i64::from(n));
                self.printer.print_str(" to ");
                self.printer.print_scaled(w);
                self.printer.print_char(',' as u32);
                self.printer.print_scaled(bhpd);
                self.printer.print_str(" p=");
                if q.is_null() {
                    self.printer.print_int(i64::from(EJECT_PENALTY));
                } else if self.nodes.id(q) == id::PENALTY {
                    self.printer.print_int(i64::from(self.nodes.penalty(q)));
                } else {
                    self.printer.print_char('0' as u32);
                }
                self.end_diagnostic(false);
            }
            if c != 1000 {
                bhpd = x_over_n(bhpd, 1000).wrapping_mul(c);
            }
            self.page.so_far[0] -= bhpd;
            let r = &mut self.page.ins[idx];
            r.split_up = true;
            r.broken_ptr = q;
            r.broken_ins = p;
            if q.is_null() {
                self.insert_penalties += EJECT_PENALTY;
            } else if self.nodes.id(q) == id::PENALTY {
                self.insert_penalties += self.nodes.penalty(q);
            }
        }
    }

    /// Outputs the current page at the best place (`fire_up`).
    fn fire_up(&mut self, c: NodeRef) {
        let bpb = self.page.best_break;
        if self.diagnostics.is_some() {
            let s = self.page.best_so_far;
            let forced = !bpb.is_null()
                && self.nodes.id(bpb) == id::PENALTY
                && self.nodes.penalty(bpb) <= EJECT_PENALTY;
            self.page.last_break = Some(crate::pagenote::PageBreakInfo {
                page: self.eqtb.count[0].val,
                goal: s[0],
                total: s[1],
                stretch: s[2],
                infinite: self.page.best_infinite,
                forced,
                moved: if forced { None } else { self.first_moved(bpb) },
            });
        }
        // Set the value of \outputpenalty.
        if !bpb.is_null() && self.nodes.id(bpb) == id::PENALTY {
            let pen = self.nodes.penalty(bpb);
            self.geq_define(Loc::IntPar(ip::OUTPUTPENALTY), Val::Int(i64::from(pen)));
            if let NodeData::Penalty { penalty } = self.nodes.data_mut(bpb) {
                *penalty = INF_PENALTY;
            }
        } else {
            self.geq_define(
                Loc::IntPar(ip::OUTPUTPENALTY),
                Val::Int(i64::from(INF_PENALTY)),
            );
        }
        for m in self.marks.classes.values_mut() {
            if m[mark_code::BOT].is_some() {
                m[mark_code::TOP] = m[mark_code::BOT].clone();
                m[mark_code::FIRST] = None;
            }
        }
        if c == self.page.best_break {
            self.page.best_break = NodeRef::NULL;
        }
        let best_break = self.page.best_break;
        // Ensure that box 255 is empty before output.
        let obox = self.output_box_num() as u32;
        if !self.eqtb.boxes[obox as usize].val.is_null() {
            self.print_err("");
            self.print_esc_str("box");
            self.printer.print_int(i64::from(obox));
            self.printer.print_str(" is not void");
            self.help(&[
                "You shouldn't use \\box255 except in \\output routines.",
                "Proceed, and I'll discard its present contents.",
            ]);
            self.box_error(obox);
        }
        self.insert_penalties = 0;
        let save_split_top_skip = self.eqtb.glue_par[gp::SPLITTOPSKIP as usize].val;
        let holding = self.eqtb.int(ip::HOLDINGINSERTS) > 0;
        if !holding {
            // Prepare all the boxes involved in insertions to act as
            // queues.
            for i in 0..self.page.ins.len() {
                if !self.page.ins[i].best_ins_ptr.is_null() {
                    let n = self.page.ins[i].n;
                    self.ensure_vbox(n);
                    if self.eqtb.boxes[n as usize].val.is_null() {
                        let b = self.nodes.new_null_box(false);
                        self.eqtb.boxes[n as usize].val = b;
                    }
                    let b = self.eqtb.boxes[n as usize].val;
                    let l = self.nodes.list_ptr(b);
                    self.page.ins[i].last_ins_ptr = self.nodes.tail_of(l);
                }
            }
        }
        // Held-over insertions are collected after `hold_head`.
        let hold_head = self.nodes.new_temp();
        let mut q = hold_head;
        let mut prev_p = self.page.page_head;
        let mut p = self.nodes.next(prev_p);
        while p != best_break && !p.is_null() {
            let t = self.nodes.id(p);
            if t == id::INS {
                if !holding {
                    let n = u32::from(self.nodes.subtype(p));
                    let Some(ri) = self.page.ins.iter().position(|r| r.n == n) else {
                        prev_p = p;
                        p = self.nodes.next(prev_p);
                        continue;
                    };
                    let mut wait;
                    if self.page.ins[ri].best_ins_ptr.is_null() {
                        wait = true;
                    } else {
                        wait = false;
                        let bx = self.eqtb.boxes[n as usize].val;
                        let start = self.page.ins[ri].last_ins_ptr;
                        let il = self.nodes.list_ptr(p);
                        if start.is_null() {
                            self.nodes.set_list_ptr(bx, il);
                        } else {
                            self.nodes.link(start, il);
                        }
                        if self.page.ins[ri].best_ins_ptr == p {
                            // Wrap up the box, splitting node p if called
                            // for.
                            let r = self.page.ins[ri];
                            if r.split_up && r.broken_ins == p && !r.broken_ptr.is_null() {
                                if start.is_null() && self.nodes.list_ptr(bx) == r.broken_ptr {
                                    self.nodes.set_list_ptr(bx, NodeRef::NULL);
                                } else {
                                    let mut s = if start.is_null() {
                                        self.nodes.list_ptr(bx)
                                    } else {
                                        start
                                    };
                                    while !s.is_null() && self.nodes.next(s) != r.broken_ptr {
                                        s = self.nodes.next(s);
                                    }
                                    if !s.is_null() {
                                        self.nodes.set_next(s, NodeRef::NULL);
                                    }
                                }
                                let sts = match self.nodes.data(p) {
                                    NodeData::Ins { spec, .. } => *spec,
                                    _ => Glue::ZERO,
                                };
                                self.eqtb.glue_par[gp::SPLITTOPSKIP as usize].val = sts;
                                let rest = self.prune_page_top(r.broken_ptr, false);
                                self.nodes.set_list_ptr(p, rest);
                                if !rest.is_null() {
                                    let tmp = self.vpack(rest, PackSpec::NATURAL);
                                    let hh = self.node_height(tmp) + self.node_depth(tmp);
                                    self.nodes.set_list_ptr(tmp, NodeRef::NULL);
                                    self.nodes.free(tmp);
                                    if let NodeData::Ins { height, .. } = self.nodes.data_mut(p) {
                                        *height = hh;
                                    }
                                    wait = true;
                                }
                            }
                            self.page.ins[ri].best_ins_ptr = NodeRef::NULL;
                            let l = self.nodes.list_ptr(bx);
                            self.nodes.set_list_ptr(bx, NodeRef::NULL);
                            self.nodes.free(bx);
                            let nb = self.vpack(l, PackSpec::NATURAL);
                            self.eqtb.boxes[n as usize].val = nb;
                        } else {
                            let l = self.nodes.list_ptr(bx);
                            self.page.ins[ri].last_ins_ptr = self.nodes.tail_of(l);
                        }
                    }
                    // Either append the insertion node p after node q, or
                    // delete it.
                    let nx = self.nodes.next(p);
                    self.nodes.set_next(prev_p, nx);
                    if !nx.is_null() {
                        self.nodes.set_prev(nx, prev_p);
                    }
                    self.nodes.set_next(p, NodeRef::NULL);
                    if wait {
                        self.nodes.link(q, p);
                        q = p;
                        self.insert_penalties += 1;
                    } else {
                        self.nodes.set_list_ptr(p, NodeRef::NULL);
                        self.nodes.free(p);
                    }
                    p = prev_p;
                }
            } else if let NodeData::Mark { class, mark } = self.nodes.data(p) {
                let (cl, m) = (*class, mark.clone());
                let e = self.marks.classes.entry(cl).or_default();
                if e[mark_code::FIRST].is_none() {
                    e[mark_code::FIRST] = Some(m.clone());
                }
                e[mark_code::BOT] = Some(m);
            }
            prev_p = p;
            p = self.nodes.next(prev_p);
        }
        self.eqtb.glue_par[gp::SPLITTOPSKIP as usize].val = save_split_top_skip;
        // Break the current page at node p, put it in box 255, and put the
        // remaining nodes on the contribution list.
        let ch = self.page.contrib_head;
        if !p.is_null() {
            if self.nodes.next(ch).is_null() {
                let pt = self.page.page_tail;
                self.set_contrib_tail(pt);
            }
            let pt = self.page.page_tail;
            let cn = self.nodes.next(ch);
            self.nodes.set_next(pt, cn);
            if !cn.is_null() {
                self.nodes.set_prev(cn, pt);
            }
            self.nodes.link(ch, p);
            self.nodes.set_next(prev_p, NodeRef::NULL);
        }
        let save_vbadness = self.eqtb.int_par[ip::VBADNESS as usize].val;
        let save_vfuzz = self.eqtb.dimen_par[dp::VFUZZ as usize].val;
        self.eqtb.int_par[ip::VBADNESS as usize].val = INF_BAD;
        self.eqtb.dimen_par[dp::VFUZZ as usize].val = retex_arith::MAX_DIMEN;
        let first = self.nodes.next(self.page.page_head);
        let b = self.vpackage(
            first,
            PackSpec::Exactly(self.page.best_size),
            self.page.max_depth,
        );
        self.eqtb.boxes[obox as usize].val = b;
        self.eqtb.int_par[ip::VBADNESS as usize].val = save_vbadness;
        self.eqtb.dimen_par[dp::VFUZZ as usize].val = save_vfuzz;
        self.start_new_page();
        if q != hold_head {
            let h = self.nodes.next(hold_head);
            self.nodes.link(self.page.page_head, h);
            self.page.page_tail = q;
        }
        self.nodes.free(hold_head);
        self.page.ins.clear();
        for m in self.marks.classes.values_mut() {
            if m[mark_code::TOP].is_some() && m[mark_code::FIRST].is_none() {
                m[mark_code::FIRST] = m[mark_code::TOP].clone();
            }
        }
        let output = self
            .eqtb
            .toks_param(crate::primitives_gen::assign_toks::OUTPUT)
            .clone();
        if !output.is_empty() {
            if self.dead_cycles >= self.eqtb.int(ip::MAXDEADCYCLES) {
                self.print_err("Output loop---");
                self.printer.print_int(i64::from(self.dead_cycles));
                self.printer.print_str(" consecutive dead cycles");
                self.help(&[
                    "I've concluded that your \\output is awry; it never does a",
                    "\\shipout, so I'm shipping \\box255 out myself. Next time",
                    "increase \\maxdeadcycles if you want me to be more patient!",
                ]);
                self.error();
            } else {
                // Fire up the user's output routine.
                self.ts.output_active = true;
                self.dead_cycles += 1;
                self.push_nest(Mode::InternalVertical);
                self.cur_list_mut().prev_depth = IGNORE_DEPTH;
                let line = self.input.line();
                self.cur_list_mut().mode_line = -line;
                self.begin_token_list(output, TokKind::OutputText);
                self.new_save_level(GroupCode::Output);
                self.normal_paragraph();
                self.scan_left_brace();
                return;
            }
        }
        // Perform the default output routine.
        let ph = self.page.page_head;
        let first = self.nodes.next(ph);
        if !first.is_null() {
            if self.nodes.next(ch).is_null() {
                let pt = self.page.page_tail;
                self.set_contrib_tail(pt);
            } else {
                let pt = self.page.page_tail;
                let cn = self.nodes.next(ch);
                self.nodes.link(pt, cn);
            }
            self.nodes.link(ch, first);
            self.nodes.set_next(ph, NodeRef::NULL);
            self.page.page_tail = ph;
        }
        let pd = std::mem::take(&mut self.ts.disc_ptr[2]);
        self.nodes.flush_list(pd);
        let b = self.eqtb.boxes[obox as usize].val;
        self.eqtb.boxes[obox as usize].val = NodeRef::NULL;
        if !b.is_null() {
            self.ship_out(b);
        }
    }

    /// Resumes the page builder after the output routine (§1026).
    pub fn resume_output(&mut self) {
        let ok = matches!(
            self.input.stack.last(),
            Some(Level::Tokens(t)) if t.loc >= t.list.len()
                && (t.kind == TokKind::OutputText || t.kind == TokKind::BackedUp)
        );
        if !ok {
            self.print_err("Unbalanced output routine");
            self.help(&[
                "Your sneaky output routine has problematic {'s and/or }'s.",
                "I can't handle that very well; good luck.",
            ]);
            self.error();
            let mut guard = 0;
            loop {
                self.get_token();
                guard += 1;
                let done = matches!(
                    self.input.stack.last(),
                    Some(Level::Tokens(t)) if t.loc >= t.list.len()
                );
                if done || guard > 1_000_000 {
                    break;
                }
            }
        }
        self.end_token_list();
        self.end_graf();
        self.unsave();
        self.ts.output_active = false;
        self.insert_penalties = 0;
        // Ensure that box 255 is empty after output.
        let obox = self.output_box_num() as u32;
        if !self.eqtb.boxes[obox as usize].val.is_null() {
            self.print_err("Output routine didn't use all of ");
            self.print_esc_str("box");
            self.printer.print_int(i64::from(obox));
            self.help(&[
                "Your \\output commands should empty \\box255,",
                "e.g., by saying `\\shipout\\box255'.",
                "Proceed; I'll discard its present contents.",
            ]);
            self.box_error(obox);
        }
        let (head, tail) = (self.cur_list().head, self.cur_list().tail);
        if tail != head {
            let pt = self.page.page_tail;
            let first = self.nodes.next(head);
            self.nodes.link(pt, first);
            self.page.page_tail = tail;
            self.nodes.set_next(head, NodeRef::NULL);
        }
        let ph = self.page.page_head;
        let ch = self.page.contrib_head;
        let first = self.nodes.next(ph);
        if !first.is_null() {
            if self.nodes.next(ch).is_null() {
                let pt = self.page.page_tail;
                self.set_contrib_tail(pt);
            }
            let pt = self.page.page_tail;
            let cn = self.nodes.next(ch);
            self.nodes.set_next(pt, cn);
            if !cn.is_null() {
                self.nodes.set_prev(cn, pt);
            }
            self.nodes.link(ch, first);
            self.nodes.set_next(ph, NodeRef::NULL);
            self.page.page_tail = ph;
        }
        let pd = std::mem::take(&mut self.ts.disc_ptr[2]);
        self.nodes.flush_list(pd);
        self.pop_nest();
        self.build_page_from("after_output");
    }
}

/// `x_over_n` returning only the quotient (0 on overflow).
fn x_over_n(x: i32, n: i32) -> i32 {
    retex_arith::x_over_n(x, n).map_or(0, |d| d.quotient)
}