retex_engine/

shipout.rs

//! Shipping pages out (*TeX: The Program* §592–§640, LuaTeX's PDF
//! backend positions).
//!
//! `ship_out` prints the `[n]` progress report, walks the box exactly as
//! TeX's `hlist_out`/`vlist_out` do (including the cumulative glue
//! rounding and leaders, §619–§637), executes `\openout`/`\write`/
//! `\closeout` whatsits, and hands glyphs, rules and literals either to a
//! [`Backend`] in page coordinates (`\outputmode>0`) or to the
//! [`crate::dvi`] writer in DVI coordinates (`\outputmode=0`).

use crate::Engine;
use crate::fonts::PacketCommand;
use crate::glue::Glue;
use crate::nodes::{NodeData, NodeRef, RUNNING, Whatsit, glue_sub, id};
use crate::primitives_gen::{assign_dimen as dp, assign_int as ip};

/// A destination for shipped pages (the PDF writer). Coordinates are in
/// scaled points from the lower-left corner of the page, y upwards.
pub trait Backend {
    /// Starts a page of the given size.
    fn begin_page(&mut self, engine: &Engine, width: i32, height: i32);
    /// Draws character `chr` of font `font` with its origin at (x, y).
    fn glyph(&mut self, engine: &Engine, font: u32, chr: u32, x: i32, y: i32);
    /// Draws a glyph expanded horizontally by `ef` millionths of its width
    /// (font expansion; `ef` is never 0).
    fn glyph_expanded(&mut self, engine: &Engine, font: u32, chr: u32, x: i32, y: i32, ef: i32) {
        let _ = ef;
        self.glyph(engine, font, chr, x, y);
    }
    /// Draws a filled rule with its lower-left corner at (x, y).
    fn rule(&mut self, x: i32, y: i32, width: i32, height: i32);
    /// Emits a literal (`\pdfextension literal`) at (x, y).
    fn literal(&mut self, mode: u8, data: &[u8], x: i32, y: i32);
    /// Emits text written by `pdf.print` at (x, y): a literal without
    /// the newline after it (observed).
    fn print(&mut self, mode: u8, data: &[u8], x: i32, y: i32) {
        self.literal(mode, data, x, y);
    }
    /// Finishes the page.
    fn end_page(&mut self, engine: &Engine);
    /// Finishes the document.
    fn finish(&mut self, engine: &mut Engine) -> Option<Finished>;

    /// `\pdfextension save` at (x, y).
    fn save(&mut self, x: i32, y: i32) {
        self.literal(0, b"q", x, y);
    }

    /// `\pdfextension restore` at (x, y).
    fn restore(&mut self, x: i32, y: i32) {
        self.literal(0, b"Q", x, y);
    }

    /// `\pdfextension setmatrix` at (x, y).
    fn set_matrix(&mut self, x: i32, y: i32, matrix: &[u8]) {
        let mut d = matrix.to_vec();
        d.extend_from_slice(b" 0 0 cm");
        self.literal(0, &d, x, y);
    }

    /// Before the process forks for a preamble snapshot: writes out what
    /// is buffered (see [`resume`](Self::resume)).
    fn suspend(&mut self) -> std::io::Result<()> {
        Ok(())
    }

    /// Whether a pass can resume from the snapshot taken at
    /// [`suspend`](Self::suspend): the output file is still there, at least
    /// as long as then (a failed build may have removed it).
    fn resumable(&self) -> bool {
        true
    }

    /// A fingerprint of the state that decides what the backend writes
    /// from now on (see [`crate::fingerprint`]): not what it wrote.
    fn fingerprint(&mut self) -> u64 {
        0
    }

    /// For `--watch` (see `docs/design/incremental-rebuilds.md`): what the
    /// output holds so far, flushed to the file, as an encoded
    /// `retex_pdf::Prefix`; `None` if there is no output file.
    fn prefix(&mut self) -> Option<Vec<u8>> {
        None
    }

    /// The output file, and where it was first opened (it keeps that name
    /// once the run is over).
    fn output_file(&self) -> Option<(std::path::PathBuf, std::path::PathBuf)> {
        None
    }

    /// Gives the output file the second name `to`, under which it goes on
    /// (its first name may then be given to another file).
    fn divert(&mut self, _to: &std::path::Path) -> std::io::Result<()> {
        Err(std::io::Error::other("not supported"))
    }

    /// Goes on in file `to` with another run's `prefix` (see
    /// [`prefix`](Self::prefix)), read from that run's file `from`,
    /// followed by `saved` from `cut` on: this backend's output up to the
    /// end (taken from its file before the other run changed it), the two
    /// runs being in the same state at that point.
    fn splice(
        &mut self,
        _prefix: &[u8],
        _from: &std::path::Path,
        _saved: &[u8],
        _cut: u64,
        _to: &std::path::Path,
    ) -> std::io::Result<()> {
        Err(std::io::Error::other("not supported"))
    }

    /// In a process resumed from a preamble snapshot: reopens the output
    /// file opened before the snapshot, cut back to its length then (the
    /// forked processes share the file's position otherwise).
    fn resume(&mut self) -> std::io::Result<()> {
        Ok(())
    }

    /// Gives up the output file: with `remove`, it is deleted (after a
    /// fatal error), otherwise left empty (no pages), as LuaTeX does.
    fn abandon(&mut self, _remove: bool) {}

    /// Prepares for writing an object whose text is still to be made
    /// (allocates the object stream it will go into, as LuaTeX does).
    fn begin_object(&mut self, _engine: &Engine) {}

    /// The object number of the page begun last.
    fn current_page_object(&self) -> Option<i32> {
        None
    }

    /// Writes the page's contents and dictionary: the page attributes and
    /// resources of `items` are final, and whether there are annotations.
    fn close_page_contents(&mut self, _engine: &Engine, _items: &crate::pdfext::PageItems) {}

    /// Hands over the page's annotations, links, destinations and
    /// referenced objects, just before [`end_page`](Self::end_page).
    fn page_items(&mut self, _engine: &Engine, _items: &crate::pdfext::PageItems) {}

    /// Starts writing box resource `index` (natural size `size` = width,
    /// height, depth) as a form XObject; drawing goes into the form until
    /// [`end_box_form`](Self::end_box_form).
    fn begin_box_form(
        &mut self,
        _engine: &Engine,
        _index: u32,
        _size: (i32, i32, i32),
        _attr: &[u8],
        _resources: &[u8],
    ) {
    }

    /// Finishes the box resource being written (its content stream).
    fn end_box_form(&mut self, _engine: &Engine) {}

    /// Writes the resources of the box resource finished last, after the
    /// forms it uses.
    fn close_box_form_resources(&mut self, _engine: &Engine) {}

    /// Writes the resources of the page ended last, after the forms it
    /// uses.
    fn close_page_resources(&mut self, _engine: &Engine) {}

    /// Draws box resource `index` with its lower-left corner at (x, y),
    /// scaled to `width` × `height` (height + depth).
    fn box_form(
        &mut self,
        _engine: &Engine,
        _index: u32,
        _x: i32,
        _y: i32,
        _width: i32,
        _height: i32,
    ) {
    }

    /// Writes image resource `index` (its object number) now (`\immediate`).
    fn write_image(&mut self, _engine: &Engine, _index: u32) {}

    /// Draws image resource `index` with its lower-left corner at (x, y),
    /// `width` wide and `height` (height + depth) tall.
    fn image(
        &mut self,
        _engine: &Engine,
        _index: u32,
        _x: i32,
        _y: i32,
        _width: i32,
        _height: i32,
    ) {
    }

    /// The images written (when the pages and forms using them were
    /// closed) since the last call, if the backend writes them that way;
    /// `None` to have them announced at the end of the page using them.
    fn written_images(&mut self) -> Option<Vec<u32>> {
        None
    }

    /// Writes an object created with `\pdfextension obj`.
    fn write_object(&mut self, _engine: &Engine, _obj: &crate::pdfext::PdfObject) {}
}

/// What the backend reports when the document is finished.
#[derive(Clone, Debug, Default)]
pub struct Finished {
    /// The output file name as printed in "Output written on …".
    pub file: String,
    /// Its size in bytes.
    pub size: u64,
    /// Files embedded, as printed: `<font file>`, `{encoding file}`
    /// (LuaTeX order).
    pub embedded: Vec<String>,
    /// Objects written into object streams, and the number of streams.
    pub objstm: (u32, u32),
}

/// The width of the replacement nodes before `q` (from `head`).
fn items_before_width(e: &Engine, head: NodeRef, q: NodeRef) -> i32 {
    let mut w = 0;
    let mut r = head;
    while !r.is_null() && r != q {
        w += e.replace_item_width(r);
        r = e.nodes.next(r);
    }
    w
}

/// The glue-rounding state of a box being shipped (`cur_g`, `cur_glue`).
#[derive(Clone)]
struct GlueState {
    cur_g: i32,
    cur_glue: f64,
    order: u8,
    sign: u8,
    set: f64,
}

impl GlueState {
    /// TeX's glue computation for one glue node: returns its width.
    fn advance(&mut self, g: &Glue) -> i32 {
        let mut w = g.width - self.cur_g;
        if self.sign != 0 {
            let applies = if self.sign == 1 {
                g.stretch_order == self.order
            } else {
                g.shrink_order == self.order
            };
            if applies {
                if self.sign == 1 {
                    self.cur_glue += f64::from(g.stretch);
                } else {
                    self.cur_glue -= f64::from(g.shrink);
                }
                let t = (self.set * self.cur_glue).clamp(-1_000_000_000.0, 1_000_000_000.0);
                self.cur_g = t.round() as i32;
            }
        }
        w += self.cur_g;
        w
    }
}

impl Engine {
    /// Calls the page-number callback `name` if one is registered; whether
    /// it was.
    fn page_number_callback(&mut self, name: &str) -> bool {
        let Some(lua) = self.lua.clone() else {
            return false;
        };
        if !lua.has_callback(name) {
            return false;
        }
        if let Err(e) = lua.call_simple(self, name) {
            self.lua_error(&e);
        }
        true
    }

    /// Ships box `p` out (`ship_out`).
    pub fn ship_out(&mut self, p: NodeRef) {
        self.work_begin(crate::profile::Work::Shipout);
        self.ship_out_inner(p);
        self.work_end();
    }

    fn ship_out_inner(&mut self, p: NodeRef) {
        self.pdf.page_annots.clear();
        let tracing = self.eqtb.int(ip::TRACINGOUTPUT) > 0;
        if tracing {
            self.printer.print_nl("");
            self.printer.print_ln();
            self.printer.print_str("Completed box being shipped out");
        }
        // The `start_page_number` callback replaces ` [` and the page
        // numbers, `stop_page_number` the closing `]` (observed).
        if !self.page_number_callback("start_page_number") {
            if self.printer.term_offset > self.printer.max_print_line.saturating_sub(9) {
                self.printer.print_ln();
            } else if self.printer.term_offset > 0 || self.printer.file_offset > 0 {
                self.printer.print_char(' ' as u32);
            }
            self.printer.print_char('[' as u32);
            let mut j = 9;
            while j > 0 && self.eqtb.count[j].val == 0 {
                j -= 1;
            }
            for k in 0..=j {
                self.printer.print_int(self.eqtb.count[k].val.into());
                if k < j {
                    self.printer.print_char('.' as u32);
                }
            }
        }
        self.printer.update_terminal();
        if p.is_null() {
            // `tex.shipout` of a void box (observed).
            self.luatex_warning(
                "backend",
                "pagedir differs from bodydir, the output may be placed wrongly on the page",
            );
            let msg = "no vlist or hlist in (xform) shipout";
            if self.eqtb.int(ip::OUTPUTMODE) > 0 {
                self.pdf_fatal(msg);
            }
            self.luatex_fatal("pdf backend", msg);
        }
        if tracing {
            if !self.page_number_callback("stop_page_number") {
                self.printer.print_char(']' as u32);
            }
            self.begin_diagnostic();
            self.show_box(p);
            self.end_diagnostic(true);
        }
        self.ship_box(p);
        if !tracing && !self.page_number_callback("stop_page_number") {
            self.printer.print_char(']' as u32);
        }
        self.dead_cycles = 0;
        self.printer.update_terminal();
        self.nodes.flush_list(p);
    }

    /// Ships the contents of box `p`.
    fn ship_box(&mut self, p: NodeRef) {
        let Some(b) = self.nodes.box_data(p).cloned() else {
            return;
        };
        let pdf = self.eqtb.int(ip::OUTPUTMODE) > 0;
        // Page size and origin.
        let h_origin = self.eqtb.dimen(crate::backend::H_ORIGIN);
        let v_origin = self.eqtb.dimen(crate::backend::V_ORIGIN);
        let h_off = self.eqtb.dimen(dp::HOFFSET);
        let v_off = self.eqtb.dimen(dp::VOFFSET);
        let mut width = self.eqtb.dimen(dp::PAGEWIDTH);
        let mut height = self.eqtb.dimen(dp::PAGEHEIGHT);
        // Observed: without \pagewidth (\pageheight), the page is the box
        // plus 1in and the offset on each side, whatever the origin.
        const ONE_INCH: i32 = 4_736_286;
        if width <= 0 {
            width = b.width + 2 * (ONE_INCH + h_off);
        }
        if height <= 0 {
            height = b.height + b.depth + 2 * (ONE_INCH + v_off);
        }
        let mut backend = if pdf { self.backend.take() } else { None };
        let forms_depth = self.pending_forms.len();
        self.pending_forms.push(Vec::new());
        if let Some(be) = backend.as_mut() {
            self.pdf.page = Default::default();
            be.begin_page(self, width, height);
            if let Some(n) = be.current_page_object() {
                let page = self.total_pages as i32 + 1;
                self.pdf.page_refs.insert(page, n);
                self.pdf.kinds.insert(n, crate::pdfext::ObjKind::Page);
            }
            // Observed: written at the page box's reference point.
            let (x, y) = (h_origin + h_off, height - (v_origin + v_off + b.height));
            for (mode, lit) in self.page_colorstack_literals() {
                be.literal(mode, &lit, x, y);
            }
        }
        let dvi = if pdf {
            None
        } else {
            let mut d = std::mem::take(&mut self.dvi);
            d.begin_page(self, (b.width, b.height, b.depth), (h_off, v_off));
            Some(d)
        };
        let sync = self.synctex_recording();
        if sync {
            self.synctex_begin_page((h_origin + h_off, v_origin + v_off));
        }
        let mut walker = Walker {
            backend,
            dvi,
            h_origin: h_origin + h_off,
            v_origin: v_origin + v_off,
            page_height: height,
            dvi_h: h_off,
            dvi_v: v_off,
            cur_s: -1,
            doing_leaders: false,
            page: true,
            sync,
            matrix: None,
            matrix_stack: Vec::new(),
        };
        // Observed: a right-to-left hbox shipped out as the page has its
        // right edge at the origin.
        let cur_h = if self.nodes.id(p) == id::HLIST && b.dir == 1 {
            -b.width
        } else {
            0
        };
        let cur_v = b.height;
        if self.nodes.id(p) == id::VLIST {
            self.vlist_out(&mut walker, p, cur_h, cur_v);
        } else {
            self.hlist_out(&mut walker, p, cur_h, cur_v);
        }
        if let Some(mut be) = walker.backend.take() {
            self.flush_pending_objects(be.as_mut());
            self.collect_page_texts();
            let items = std::mem::take(&mut self.pdf.page);
            be.close_page_contents(self, &items);
            self.pdf.page = items;
            self.resolve_link_actions();
            let items = std::mem::take(&mut self.pdf.page);
            be.page_items(self, &items);
            // Observed order: the page's own objects, the forms it uses,
            // its resources.
            be.end_page(self);
            let mut be = self.write_pending_forms(be);
            be.close_page_resources(self);
            self.flush_pending_objects(be.as_mut());
            self.backend = Some(be);
            let page_images = std::mem::take(&mut self.pdf.page_images);
            let written = self.backend.as_mut().and_then(|b| b.written_images());
            for n in written.unwrap_or(page_images) {
                self.print_image_name(n);
            }
        }
        self.pending_forms.truncate(forms_depth);
        if let Some(mut d) = walker.dvi.take() {
            d.end_page();
            self.dvi = d;
        }
        if sync {
            self.synctex_end_page();
        }
        self.total_pages += 1;
        if let Some(f) = self.progress_hook {
            f(self);
        }
        if let Some(f) = self.page_hook {
            f(self);
        }
    }

    /// Finishes the PDF file and nothing else, quietly: for `--watch`,
    /// in a process that writes a PDF spliced from two runs (see
    /// [`Backend::splice`]). Returns whether it was written.
    pub fn finish_pdf_only(&mut self) -> bool {
        let Some(mut be) = self.backend.take() else {
            return false;
        };
        self.pdf_finish_document();
        self.flush_pending_objects(be.as_mut());
        let done = be.finish(self).is_some();
        self.backend = Some(be);
        done
    }

    /// Writes the objects queued while the backend was busy.
    fn flush_pending_objects(&mut self, be: &mut dyn Backend) {
        for obj in std::mem::take(&mut self.pdf.pending) {
            be.write_object(self, &obj);
        }
    }

    /// Prints LuaTeX's note about reading font map file `name`
    /// (`{/path/pdftex.map}`), when it exists.
    pub(crate) fn print_map_file_note(&mut self, name: &str) {
        let path = self
            .kpse
            .as_ref()
            .and_then(|k| k.borrow_mut().find_file(name, retex_kpath::FileFormat::Map));
        if let Some(path) = path {
            // Printed like a C string (log lines up to 80 characters).
            let mut text = b"{".to_vec();
            text.extend_from_slice(path.to_string_lossy().as_bytes());
            text.push(b'}');
            self.printer.print_lua_bytes(&text);
        }
    }

    /// Outputs a glyph with its reference point at TeX position (`h`,
    /// `v`).
    fn out_glyph(&mut self, w: &mut Walker, font: u32, chr: u32, h: i32, v: i32, ef: i32) {
        self.out_glyph_at_depth(w, font, chr, h, v, ef, 0);
    }

    /// [`out_glyph`](Self::out_glyph) inside `depth` virtual characters.
    #[allow(clippy::too_many_arguments)]
    fn out_glyph_at_depth(
        &mut self,
        w: &mut Walker,
        font: u32,
        chr: u32,
        h: i32,
        v: i32,
        ef: i32,
        depth: u32,
    ) {
        if let Some(vf) = &self.font(font).vf
            && vf.packets.contains_key(&chr)
        {
            if depth < 8 {
                let mut st = PacketState {
                    h,
                    v,
                    font: 0,
                    stack: Vec::new(),
                    ef,
                    depth,
                    vf: vf.clone(),
                    vfont: font,
                    chr,
                };
                let vf = vf.clone();
                for c in &vf.packets[&chr] {
                    self.packet_command(w, &mut st, c);
                }
            }
            return;
        }
        if !self.pdf.map_note_done
            && w.backend.is_some()
            && self.font(font).chars.contains_key(&chr)
        {
            // Observed: LuaTeX reads the map file when the first character
            // is output (not a virtual one, nor one missing from its font,
            // in \nullfont, say).
            self.pdf.map_note_done = true;
            self.print_map_file_note("pdftex.map");
        }
        let (x, y) = w.pos(h, v);
        // Observed: a character missing from its font is not output.
        if let Some(be) = w.backend.as_deref_mut()
            && self.font(font).chars.contains_key(&chr)
        {
            if ef == 0 {
                be.glyph(self, font, chr, x, y);
            } else {
                be.glyph_expanded(self, font, chr, x, y, ef);
            }
        }
        if let Some(d) = w.dvi.as_mut()
            && self.font(font).chars.contains_key(&chr)
        {
            let wd = crate::expansion::expanded_width(self.font_char_dimen(font, chr, 0), ef);
            d.glyph(self, font, chr, w.dvi_h + h, w.dvi_v + v, wd);
        }
    }

    /// Runs one command of a virtual character's packet: characters of
    /// the local fonts and rules are output at the positions the packet
    /// moves to (in DVI as in PDF, LuaTeX writes the local fonts'
    /// characters, not the virtual one).
    fn packet_command(&mut self, w: &mut Walker, st: &mut PacketState, c: &PacketCommand) {
        match c {
            PacketCommand::Font(i) => st.font = st.vf.fonts.get(*i).copied().unwrap_or(0),
            PacketCommand::FontId(f) => st.font = *f,
            PacketCommand::Char(c) => {
                // The first local font until one is selected.
                if st.font == 0 {
                    st.font = st.vf.fonts.first().copied().unwrap_or(0);
                }
                let f = st.font;
                if f != 0 && self.font(f).chars.contains_key(c) {
                    self.out_glyph_at_depth(w, f, *c, st.h, st.v, st.ef, st.depth + 1);
                    st.h = st.h.wrapping_add(crate::expansion::expanded_width(
                        self.font_char_dimen(f, *c, 0),
                        st.ef,
                    ));
                }
            }
            PacketCommand::Rule { height, width } => {
                if *height > 0 && *width > 0 {
                    Self::out_rule(w, st.h, st.v, *width, *height);
                }
                st.h = st.h.wrapping_add(*width);
            }
            // Observed: font expansion stretches the packet's moves like
            // its characters (the kern of a Times `ff` made of two `f`s).
            PacketCommand::Right(x) => {
                st.h =
                    st.h.wrapping_add(crate::expansion::expanded_width(*x, st.ef))
            }
            PacketCommand::Down(y) => st.v = st.v.wrapping_add(*y),
            PacketCommand::Push => st.stack.push((st.h, st.v)),
            PacketCommand::Pop => {
                if let Some((h, v)) = st.stack.pop() {
                    (st.h, st.v) = (h, v);
                }
            }
            PacketCommand::Special(data) => self.out_special(w, st.h, st.v, data),
            PacketCommand::Pdf(mode, data) => {
                let (x, y) = w.pos(st.h, st.v);
                if let Some(be) = w.backend.as_deref_mut() {
                    be.literal(*mode, data, x, y);
                }
            }
            PacketCommand::Lua(r) => self.packet_lua(w, st, *r),
            // Observed: only a box is output, with its reference point at
            // the current point (its shift is ignored), and the position
            // stays.
            PacketCommand::Node(p) => {
                if matches!(self.nodes.id(*p), id::HLIST | id::VLIST) {
                    self.out_box(w, *p, st.h, st.v);
                }
            }
        }
    }

    /// Runs the `lua` command of a packet, kept under reference `r`.
    /// While it runs, the `vf` library draws into the packet (from its
    /// current state, which it leaves for the commands after) and
    /// `pdf.getpos` gives the packet's current point.
    fn packet_lua(&mut self, w: &mut Walker, st: &mut PacketState, r: i32) {
        let Some(host) = self.lua.clone() else {
            return;
        };
        let walker = std::mem::take(w);
        let saved_pos = self.pdf.pos;
        self.pdf.pos = walker.pos(st.h, st.v);
        let args = crate::ReferenceArgs::Glyph(st.vfont, st.chr);
        self.vf_frames.push(VfFrame {
            walker,
            state: st.clone(),
        });
        let result = host.call_reference(self, r, args);
        if let Some(frame) = self.vf_frames.pop() {
            *w = frame.walker;
            // Observed: the font `vf.fontid` selects is not kept for the
            // commands after.
            let font = st.font;
            *st = frame.state;
            st.font = font;
        }
        self.pdf.pos = saved_pos;
        if let Err(e) = result {
            self.lua_error(&e);
        }
    }

    /// Runs `cmd` in the packet whose `lua` command is running (the `vf`
    /// library); false outside one.
    pub fn vf_command(&mut self, cmd: &PacketCommand) -> bool {
        let Some(mut frame) = self.vf_frames.pop() else {
            return false;
        };
        // Observed: `vf.char` outputs nothing until the packet's commands
        // or `vf.fontid` selected a font (no first local font by
        // default).
        if matches!(cmd, PacketCommand::Char(_)) && frame.state.font == 0 {
            self.vf_frames.push(frame);
            return true;
        }
        self.packet_command(&mut frame.walker, &mut frame.state, cmd);
        self.pdf.pos = frame.walker.pos(frame.state.h, frame.state.v);
        self.vf_frames.push(frame);
        true
    }

    /// A dimension given to the `vf` library (`vf.right(x)`) in the
    /// packet whose `lua` command is running: observed, `x` is a
    /// fix_word scaled by the size of the virtual font, as dimensions in
    /// VF files are, and one beyond 16 times the size is a fatal error.
    /// `None` outside a packet.
    pub fn vf_scaled(&mut self, x: i64) -> Option<i32> {
        let f = self.vf_frames.last()?.state.vfont;
        if !(-(1 << 24)..1 << 24).contains(&x) {
            self.pdf_fatal_in("vf", "vf scaling");
        }
        let size = self.font(f).size;
        Some(retex_font::tfm::FixScaler::new(size).scale(x as i32))
    }

    /// Outputs a rule with its lower left corner at TeX position (`h`,
    /// `v`).
    fn out_rule(w: &mut Walker, h: i32, v: i32, width: i32, height: i32) {
        let (x, y) = w.pos(h, v);
        if let Some(be) = w.backend.as_deref_mut() {
            be.rule(x, y, width, height);
        }
        if let Some(d) = w.dvi.as_mut() {
            d.rule(w.dvi_h + h, w.dvi_v + v, width, height);
        }
    }

    /// Draws box resource `index` with its lower-left corner at (`h`, `v`).
    /// A form not written yet is written after the page or form being
    /// written (observed object numbering of LuaTeX).
    fn out_box_resource(
        &mut self,
        w: &mut Walker,
        index: i32,
        h: i32,
        v: i32,
        width: i32,
        height: i32,
    ) {
        let n = index as u32;
        let (x, y) = w.pos(h, v);
        let Some(mut be) = w.backend.take() else {
            return;
        };
        if self
            .box_resource_slot(n)
            .is_some_and(|i| !self.box_resources[i].written)
        {
            match self.pending_forms.last_mut() {
                Some(p) => {
                    if !p.contains(&n) {
                        p.push(n);
                    }
                }
                None => be = self.write_box_resource(be, n),
            }
        }
        be.box_form(self, n, x, y, width, height);
        w.backend = Some(be);
    }

    /// Writes box resource `n` as a form: ships its box into the form with
    /// the box's reference point at (0, depth), then the forms it uses that
    /// are not written yet, then its resources.
    pub fn write_box_resource(&mut self, be: Box<dyn Backend>, n: u32) -> Box<dyn Backend> {
        let Some(slot) = self.box_resource_slot(n) else {
            return be;
        };
        let r = self.box_resources[slot].clone();
        if r.written {
            return be;
        }
        // Observed: a form is shipped out like a page, so with
        // \tracingoutput positive the line is shown (but neither the
        // page number nor the box).
        if self.eqtb.int(ip::TRACINGOUTPUT) > 0 {
            self.printer.print_nl("");
            self.printer.print_ln();
            self.printer.print_str("Completed box being shipped out");
        }
        let mut be = be;
        let (bw, bh, bd) = r.size;
        self.pending_forms.push(Vec::new());
        self.form_objects.push(Vec::new());
        be.begin_box_form(self, n, (bw, bh, bd), &r.attr, &r.resources);
        let sync = self.synctex_recording();
        if sync {
            self.synctex_begin_form(bh + bd);
        }
        let mut walker = Walker {
            backend: Some(be),
            dvi: None,
            h_origin: 0,
            v_origin: 0,
            page_height: bh + bd,
            dvi_h: 0,
            dvi_v: 0,
            cur_s: -1,
            doing_leaders: false,
            page: false,
            sync,
            matrix: None,
            matrix_stack: Vec::new(),
        };
        if self.nodes.id(r.list) == id::VLIST {
            self.vlist_out(&mut walker, r.list, 0, bh);
        } else {
            self.hlist_out(&mut walker, r.list, 0, bh);
        }
        let mut be = walker.backend.take().expect("the walker keeps the backend");
        be.end_box_form(self);
        self.box_resources[slot].written = true;
        for obj in self.form_objects.pop().unwrap_or_default() {
            be.write_object(self, &obj);
        }
        be = self.write_pending_forms(be);
        // Observed: the forms this one uses are written inside its sheet.
        if sync {
            self.synctex_end_form();
        }
        be.close_box_form_resources(self);
        // Observed: an image is announced when it is written, after the
        // first form or page using it.
        for n in be.written_images().unwrap_or_default() {
            self.print_image_name(n);
        }
        be
    }

    /// Writes the forms used by the page or form just finished that are
    /// not written yet.
    fn write_pending_forms(&mut self, mut be: Box<dyn Backend>) -> Box<dyn Backend> {
        for n in self.pending_forms.pop().unwrap_or_default() {
            be = self.write_box_resource(be, n);
        }
        be
    }

    /// Draws image `index` with its lower-left corner at (`h`, `v`).
    fn out_image(&mut self, w: &mut Walker, index: i32, h: i32, v: i32, width: i32, height: i32) {
        let (x, y) = w.pos(h, v);
        if let Some(be) = w.backend.as_deref_mut() {
            be.image(self, index as u32, x, y, width, height);
            if self.mark_image_written(index as u32) {
                self.pdf.page_images.push(index as u32);
            }
        }
    }

    /// Outputs box `p` (`hlist_out` or `vlist_out`) with its reference
    /// point at (`h`, `v`).
    fn out_box(&mut self, w: &mut Walker, p: NodeRef, h: i32, v: i32) {
        // A box that contains itself (made by Lua code) is not followed
        // forever (LuaTeX crashes).
        if w.cur_s >= crate::nodes::MAX_NESTING as i32 {
            return;
        }
        if self.nodes.id(p) == id::VLIST {
            self.vlist_out(w, p, h, v);
        } else {
            self.hlist_out(w, p, h, v);
        }
    }

    /// Enters a box: `cur_s` goes up and nested boxes get a DVI `push`.
    fn enter_box(w: &mut Walker) {
        w.cur_s += 1;
        if let Some(d) = w.dvi.as_mut() {
            if w.cur_s > 0 {
                d.push(w.cur_s);
            } else {
                d.note_depth(w.cur_s);
            }
        }
    }

    /// Leaves a box (`dvi_pop`).
    fn leave_box(w: &mut Walker) {
        if w.cur_s > 0
            && let Some(d) = w.dvi.as_mut()
        {
            d.pop();
        }
        w.cur_s -= 1;
    }

    /// Outputs an hlist box (`hlist_out`); (`cur_h`, `cur_v`) is the box's
    /// reference point in TeX coordinates (v downwards).
    fn hlist_out(&mut self, w: &mut Walker, this_box: NodeRef, mut cur_h: i32, cur_v: i32) {
        let Some(b) = self.nodes.box_data(this_box).cloned() else {
            return;
        };
        let mut gs = GlueState {
            cur_g: 0,
            cur_glue: 0.0,
            order: b.glue_order,
            sign: b.glue_sign,
            set: b.glue_set,
        };
        Self::enter_box(w);
        let base_line = cur_v;
        let left_edge = cur_h;
        let ctx = crate::pdfship::BoxCtx {
            left: left_edge,
            base: base_line,
            width: b.width,
            height: b.height,
            depth: b.depth,
        };
        if !w.doing_leaders {
            self.ship_continue_links(w, &ctx);
        }
        if w.sync {
            let f = self.sync_of(this_box);
            self.synctex
                .box_open(true, f, cur_h, cur_v, [b.width, b.height, b.depth]);
        }
        // Right-to-left boxes and direction nodes: where each node goes
        // (the nodes are still output in list order).
        let places = self.rtl_places(b.head, b.dir == 1, &gs);
        let mut i = 0;
        let mut p = b.head;
        while !p.is_null() {
            let next = self.nodes.next(p);
            // (Nodes a `\latelua` function inserted have no place.)
            let rtl = match places.as_ref().and_then(|pl| pl.get(i)) {
                Some(&(x, rtl)) => {
                    cur_h = left_edge + x;
                    i += 1;
                    rtl
                }
                None => false,
            };
            if w.sync {
                self.sync_hlist_node(p, cur_h, base_line);
            }
            let n = self.nodes.get(p);
            let n_id = n.id;
            match &n.data {
                NodeData::Glyph(g) => {
                    let (font, chr, xo, yo, ef) =
                        (g.font, g.chr, g.xoffset, g.yoffset, g.expansion_factor);
                    if self.fonts.char_metrics(font, chr).is_none() {
                        self.shipout_lost_char(font, chr);
                    }
                    // In right-to-left text the offset goes leftwards.
                    let x = if rtl { cur_h - xo } else { cur_h + xo };
                    self.out_glyph(w, font, chr, x, base_line - yo, ef);
                    cur_h +=
                        crate::expansion::expanded_width(self.font_char_dimen(font, chr, 0), ef);
                }
                NodeData::Box(inner) => {
                    let (iw, shift, head) = (inner.width, inner.shift, inner.head);
                    if !head.is_null() {
                        self.out_box(w, p, cur_h, base_line + shift);
                    } else if w.sync {
                        let size = [iw, inner.height, inner.depth];
                        let f = self.sync_of(p);
                        self.synctex
                            .void_box(n_id == id::HLIST, f, cur_h, base_line, size);
                    }
                    cur_h += iw;
                }
                NodeData::Rule {
                    width,
                    depth,
                    height,
                    index,
                    ..
                } => {
                    let (wd, ht, dpt, idx) = (*width, *height, *depth, *index);
                    if n.subtype == crate::image::IMAGE_RULE {
                        self.out_image(w, idx, cur_h, base_line + dpt, wd, ht + dpt);
                    } else if n.subtype == crate::image::BOX_RESOURCE_RULE {
                        self.out_box_resource(w, idx, cur_h, base_line + dpt, wd, ht + dpt);
                    } else {
                        Self::hlist_rule(w, cur_h, base_line, wd, ht, dpt, &b);
                    }
                    cur_h += wd;
                    if w.sync {
                        let f = self.sync_of(p);
                        self.synctex.rule(f, cur_h, base_line, [wd, ht, dpt]);
                    }
                }
                NodeData::Glue { spec, leader } => {
                    let (spec, leader, sub) = (*spec, *leader, n.subtype);
                    let wd = gs.advance(&spec);
                    let box_leaders = sub >= glue_sub::A_LEADERS
                        && !leader.is_null()
                        && self.nodes.id(leader) != id::RULE;
                    if sub >= glue_sub::A_LEADERS && !leader.is_null() {
                        self.hlist_leaders(w, leader, sub, cur_h, left_edge, base_line, wd, &b);
                    }
                    cur_h += wd;
                    if w.sync && !box_leaders {
                        let f = self.sync_of(p);
                        self.synctex.glue(f, cur_h, base_line);
                    }
                }
                NodeData::Kern {
                    kern,
                    expansion_factor,
                } => {
                    let wd = kern + expansion_factor;
                    if w.sync {
                        // Observed: the width recorded is the kern's,
                        // without font expansion.
                        let f = self.sync_of(p);
                        self.synctex.kern(f, *kern);
                    }
                    cur_h += wd;
                }
                NodeData::Math { surround, glue } => {
                    let g = *glue;
                    if w.sync {
                        let f = self.sync_of(p);
                        self.synctex.math(f, cur_h, base_line);
                    }
                    cur_h += surround;
                    if g != Glue::ZERO {
                        cur_h += gs.advance(&g);
                    }
                }
                NodeData::MarginKern { width, .. } => cur_h += width,
                NodeData::Whatsit(_) => {
                    self.out_what(w, p, cur_h, base_line, &ctx);
                    // A `\latelua` function can insert nodes after it.
                    p = self.nodes.next(p);
                    continue;
                }
                NodeData::Disc { replace, .. } => {
                    let replace = *replace;
                    // A discretionary that was not broken shows its
                    // replacement text (from its right end in
                    // right-to-left text, as other nodes there).
                    let mut items = Vec::new();
                    let mut q = replace;
                    while !q.is_null() {
                        items.push(q);
                        q = self.nodes.next(q);
                    }
                    let start = cur_h;
                    let total: i32 = items.iter().map(|&q| self.replace_item_width(q)).sum();
                    for q in items {
                        if rtl {
                            // Placed at its left edge, from the right end.
                            cur_h = start + total
                                - items_before_width(self, replace, q)
                                - self.replace_item_width(q);
                        }
                        match &self.nodes.get(q).data {
                            NodeData::Glyph(g) => {
                                let (font, chr, ef) = (g.font, g.chr, g.expansion_factor);
                                self.out_glyph(w, font, chr, cur_h, base_line, ef);
                                if w.sync {
                                    self.synctex.glyph();
                                }
                                cur_h += crate::expansion::expanded_width(
                                    self.font_char_dimen(font, chr, 0),
                                    ef,
                                );
                            }
                            NodeData::Kern {
                                kern,
                                expansion_factor,
                            } => {
                                let wd = kern + expansion_factor;
                                if w.sync {
                                    self.synctex.end_run(cur_h, base_line);
                                    let f = self.sync_of(q);
                                    self.synctex.kern(f, *kern);
                                }
                                cur_h += wd;
                            }
                            // Boxes and rules, as in the list (crop's
                            // `\discretionary{}{}{\hbox{---}}`).
                            NodeData::Box(inner) => {
                                let (iw, shift, head) = (inner.width, inner.shift, inner.head);
                                if !head.is_null() {
                                    self.out_box(w, q, cur_h, base_line + shift);
                                }
                                cur_h += iw;
                            }
                            NodeData::Rule {
                                width,
                                depth,
                                height,
                                ..
                            } => {
                                let (wd, ht, dpt) = (*width, *height, *depth);
                                Self::hlist_rule(w, cur_h, base_line, wd, ht, dpt, &b);
                                cur_h += wd;
                            }
                            _ => {}
                        }
                    }
                }
                _ => {}
            }
            p = next;
        }
        if places.is_some() {
            cur_h = left_edge + b.width;
        }
        if !w.doing_leaders {
            self.ship_end_box_links(w, &ctx);
        }
        if w.sync {
            self.synctex.end_run(cur_h, base_line);
            let f = self.sync_of(this_box);
            self.synctex.box_close(true, f, cur_h, base_line);
        }
        Self::leave_box(w);
    }

    /// The width a node of an unbroken discretionary's replacement adds.
    fn replace_item_width(&self, q: NodeRef) -> i32 {
        match &self.nodes.get(q).data {
            NodeData::Glyph(g) => crate::expansion::expanded_width(
                self.font_char_dimen(g.font, g.chr, 0),
                g.expansion_factor,
            ),
            NodeData::Kern {
                kern,
                expansion_factor,
            } => kern + expansion_factor,
            NodeData::Box(b) => b.width,
            NodeData::Rule { width, .. } => *width,
            _ => 0,
        }
    }

    /// The horizontal room each node of an hlist takes when output, in
    /// list order (glue as set, with TeX's rounding in that order).
    fn hlist_widths(&self, head: NodeRef, gs: &GlueState) -> Vec<i32> {
        let mut gs = gs.clone();
        let mut out = Vec::new();
        let mut p = head;
        while !p.is_null() {
            let n = self.nodes.get(p);
            let w = match &n.data {
                NodeData::Glyph(g) => crate::expansion::expanded_width(
                    self.font_char_dimen(g.font, g.chr, 0),
                    g.expansion_factor,
                ),
                NodeData::Box(inner) => inner.width,
                NodeData::Rule { width, .. } => *width,
                NodeData::Glue { spec, .. } => gs.advance(spec),
                NodeData::Kern {
                    kern,
                    expansion_factor,
                } => kern + expansion_factor,
                NodeData::Math { surround, glue } => {
                    surround
                        + if *glue != Glue::ZERO {
                            gs.advance(glue)
                        } else {
                            0
                        }
                }
                NodeData::MarginKern { width, .. } => *width,
                NodeData::Disc { replace, .. } => {
                    let mut q = *replace;
                    let mut w = 0;
                    while !q.is_null() {
                        w += self.replace_item_width(q);
                        q = self.nodes.next(q);
                    }
                    w
                }
                _ => 0,
            };
            out.push(w);
            p = n.next;
        }
        out
    }

    /// Where the nodes of an hlist go, in list order: (left edge from the
    /// box's left edge, whether in right-to-left text), or `None` for a
    /// left-to-right box without direction nodes. As LuaTeX (observed in
    /// its PDF output): direction nodes delimit segments; a left-to-right
    /// segment places its nodes from its left end rightwards, a
    /// right-to-left one (a `TRT` box, or text after `\begindir TRT`) from
    /// its right end leftwards, both in list order, a nested segment
    /// taking the room of its width.
    fn rtl_places(&self, head: NodeRef, box_rtl: bool, gs: &GlueState) -> Option<Vec<(i32, bool)>> {
        let mut has_dirs = false;
        let mut p = head;
        while !p.is_null() {
            if self.nodes.id(p) == id::DIR {
                has_dirs = true;
                break;
            }
            p = self.nodes.next(p);
        }
        if !box_rtl && !has_dirs {
            return None;
        }
        let widths = self.hlist_widths(head, gs);
        enum Item {
            Node(usize),
            Seg(bool, Vec<Item>),
        }
        let mut stack: Vec<(bool, Vec<Item>)> = vec![(box_rtl, Vec::new())];
        let close = |stack: &mut Vec<(bool, Vec<Item>)>| {
            let (rtl, items) = stack.pop().expect("open segment");
            stack
                .last_mut()
                .expect("outer segment")
                .1
                .push(Item::Seg(rtl, items));
        };
        let mut p = head;
        let mut k = 0;
        while !p.is_null() {
            if let NodeData::Dir { dir, .. } = self.nodes.data(p) {
                let begin = self.nodes.subtype(p) != crate::dirs::dir_sub::END;
                if !begin && stack.len() > 1 {
                    // The direction node belongs to the segment it ends.
                    stack.last_mut().expect("segment").1.push(Item::Node(k));
                    close(&mut stack);
                } else if begin {
                    stack.push((*dir == 1, vec![Item::Node(k)]));
                } else {
                    stack.last_mut().expect("segment").1.push(Item::Node(k));
                }
            } else {
                stack.last_mut().expect("segment").1.push(Item::Node(k));
            }
            k += 1;
            p = self.nodes.next(p);
        }
        while stack.len() > 1 {
            close(&mut stack);
        }
        fn width(items: &[Item], widths: &[i32]) -> i32 {
            items
                .iter()
                .map(|it| match it {
                    Item::Node(i) => widths[*i],
                    Item::Seg(_, sub) => width(sub, widths),
                })
                .sum()
        }
        fn place(rtl: bool, items: &[Item], left: i32, widths: &[i32], out: &mut [(i32, bool)]) {
            let mut x = if rtl {
                left + width(items, widths)
            } else {
                left
            };
            for it in items {
                match it {
                    Item::Node(i) => {
                        if rtl {
                            x -= widths[*i];
                            out[*i] = (x, true);
                        } else {
                            out[*i] = (x, false);
                            x += widths[*i];
                        }
                    }
                    Item::Seg(r, sub) => {
                        let w = width(sub, widths);
                        if rtl {
                            x -= w;
                            place(*r, sub, x, widths, out);
                        } else {
                            place(*r, sub, x, widths, out);
                            x += w;
                        }
                    }
                }
            }
        }
        let (rtl, items) = stack.pop().expect("box segment");
        let mut out = vec![(0, false); widths.len()];
        place(rtl, &items, 0, &widths, &mut out);
        Some(out)
    }

    /// SyncTeX before node `p` of an hlist: a glyph continues a run of
    /// glyphs, the nodes that do not end one leave it, others end it.
    #[inline]
    fn sync_hlist_node(&mut self, p: NodeRef, cur_h: i32, base_line: i32) {
        match self.nodes.id(p) {
            id::GLYPH => self.synctex.glyph(),
            id::MARK | id::INS | id::ADJUST | id::BOUNDARY | id::LOCAL_PAR => {}
            _ => self.synctex.end_run(cur_h, base_line),
        }
    }

    /// A rule in an hlist whose left end is at `cur_h` (TeX's `fin_rule`
    /// in §624); running dimensions come from the enclosing box.
    fn hlist_rule(
        w: &mut Walker,
        cur_h: i32,
        base_line: i32,
        wd: i32,
        ht: i32,
        dpt: i32,
        this_box: &crate::nodes::BoxData,
    ) {
        let ht = if ht == RUNNING { this_box.height } else { ht };
        let dpt = if dpt == RUNNING { this_box.depth } else { dpt };
        let total = ht + dpt;
        if total > 0 && wd > 0 {
            Self::out_rule(w, cur_h, base_line + dpt, wd, total);
        }
    }

    /// Outputs a vlist box (`vlist_out`).
    fn vlist_out(&mut self, w: &mut Walker, this_box: NodeRef, cur_h: i32, cur_v: i32) {
        let Some(b) = self.nodes.box_data(this_box).cloned() else {
            return;
        };
        let mut gs = GlueState {
            cur_g: 0,
            cur_glue: 0.0,
            order: b.glue_order,
            sign: b.glue_sign,
            set: b.glue_set,
        };
        Self::enter_box(w);
        let left_edge = cur_h;
        let ctx = crate::pdfship::BoxCtx {
            left: left_edge,
            base: cur_v,
            width: b.width,
            height: b.height,
            depth: b.depth,
        };
        let mut cur_v = cur_v - b.height;
        let top_edge = cur_v;
        if w.sync {
            let f = self.sync_of(this_box);
            self.synctex
                .box_open(false, f, cur_h, cur_v, [b.width, b.height, b.depth]);
        }
        let mut p = b.head;
        while !p.is_null() {
            let next = self.nodes.next(p);
            let n = self.nodes.get(p);
            match &n.data {
                NodeData::Box(inner) => {
                    let (ih, idp, shift, head) =
                        (inner.height, inner.depth, inner.shift, inner.head);
                    if head.is_null() {
                        cur_v += ih + idp;
                        if w.sync {
                            let size = [inner.width, ih, idp];
                            let hlist = n.id == id::HLIST;
                            let f = self.sync_of(p);
                            self.synctex.void_box(hlist, f, left_edge, cur_v, size);
                        }
                    } else {
                        cur_v += ih;
                        self.out_box(w, p, left_edge + shift, cur_v);
                        cur_v += idp;
                    }
                }
                NodeData::Rule {
                    width,
                    depth,
                    height,
                    index,
                    ..
                } => {
                    let wd = if *width == RUNNING { b.width } else { *width };
                    let total = height + depth;
                    let idx = *index;
                    cur_v += total;
                    if n.subtype == crate::image::IMAGE_RULE {
                        self.out_image(w, idx, left_edge, cur_v, wd, total);
                    } else if n.subtype == crate::image::BOX_RESOURCE_RULE {
                        self.out_box_resource(w, idx, left_edge, cur_v, wd, total);
                    } else if total > 0 && wd > 0 {
                        Self::out_rule(w, left_edge, cur_v, wd, total);
                    }
                }
                NodeData::Glue { spec, leader } => {
                    let (spec, leader, sub) = (*spec, *leader, n.subtype);
                    let ht = gs.advance(&spec);
                    if sub >= glue_sub::A_LEADERS && !leader.is_null() {
                        cur_v =
                            self.vlist_leaders(w, leader, sub, cur_v, left_edge, top_edge, ht, &b);
                    } else {
                        cur_v += ht;
                    }
                }
                NodeData::Kern { kern, .. } => cur_v += kern,
                NodeData::Whatsit(_) => {
                    self.out_what(w, p, left_edge, cur_v, &ctx);
                    // A `\latelua` function can insert nodes after it.
                    p = self.nodes.next(p);
                    continue;
                }
                _ => {}
            }
            p = next;
        }
        if w.sync {
            let f = self.sync_of(this_box);
            self.synctex.box_close(false, f, left_edge, cur_v);
        }
        Self::leave_box(w);
    }

    /// Where leaders of the given kind start and how much space follows
    /// each copy (§626, §635): returns (start, gap) for a space of size
    /// `size` at `cur` filled with boxes of size `step`.
    fn leader_start(sub: u16, cur: i32, edge0: i32, size: i32, step: i32) -> (i32, i32) {
        if sub == glue_sub::C_LEADERS || sub == glue_sub::X_LEADERS {
            let lq = size / step;
            let lr = size % step;
            if sub == glue_sub::C_LEADERS {
                (cur + lr / 2, 0)
            } else {
                let lx = lr / (lq + 1);
                (cur + (lr - (lq - 1) * lx) / 2, lx)
            }
        } else {
            let mut c = edge0 + step * ((cur - edge0) / step);
            if c < cur {
                c += step;
            }
            (c, 0)
        }
    }

    /// Leaders in an hlist (§625–§628) filling `wd` from `cur_h`.
    #[allow(clippy::too_many_arguments)]
    fn hlist_leaders(
        &mut self,
        w: &mut Walker,
        leader: NodeRef,
        sub: u16,
        cur_h: i32,
        left_edge: i32,
        base_line: i32,
        wd: i32,
        this_box: &crate::nodes::BoxData,
    ) {
        let lb = match &self.nodes.get(leader).data {
            NodeData::Rule { height, depth, .. } => {
                let (ht, dpt) = (*height, *depth);
                Self::hlist_rule(w, cur_h, base_line, wd, ht, dpt, this_box);
                return;
            }
            NodeData::Box(lb) => lb.clone(),
            _ => return,
        };
        let leader_wd = lb.width;
        if leader_wd <= 0 || wd <= 0 {
            return;
        }
        let rule_wd = wd + 10; // compensates for floating-point rounding
        let edge = cur_h + rule_wd;
        let (mut h, lx) = Self::leader_start(sub, cur_h, left_edge, rule_wd, leader_wd);
        // The box is output even if it is empty, which counts towards the
        // DVI stack depth (§628).
        while h + leader_wd <= edge {
            let outer = w.doing_leaders;
            w.doing_leaders = true;
            self.out_box(w, leader, h, base_line + lb.shift);
            w.doing_leaders = outer;
            h += leader_wd + lx;
        }
    }

    /// Leaders in a vlist (§634–§637) filling `ht` below `cur_v`; returns
    /// the new `cur_v`.
    #[allow(clippy::too_many_arguments)]
    fn vlist_leaders(
        &mut self,
        w: &mut Walker,
        leader: NodeRef,
        sub: u16,
        cur_v: i32,
        left_edge: i32,
        top_edge: i32,
        ht: i32,
        this_box: &crate::nodes::BoxData,
    ) -> i32 {
        let lb = match &self.nodes.get(leader).data {
            NodeData::Rule { width, .. } => {
                let wd = if *width == RUNNING {
                    this_box.width
                } else {
                    *width
                };
                if ht > 0 && wd > 0 {
                    Self::out_rule(w, left_edge, cur_v + ht, wd, ht);
                }
                return cur_v + ht;
            }
            NodeData::Box(lb) => lb.clone(),
            _ => return cur_v + ht,
        };
        let leader_ht = lb.height + lb.depth;
        if leader_ht <= 0 || ht <= 0 {
            return cur_v + ht;
        }
        let rule_ht = ht + 10; // compensates for floating-point rounding
        let edge = cur_v + rule_ht;
        let (mut v, lx) = Self::leader_start(sub, cur_v, top_edge, rule_ht, leader_ht);
        while v + leader_ht <= edge {
            let outer = w.doing_leaders;
            w.doing_leaders = true;
            self.out_box(w, leader, left_edge + lb.shift, v + lb.height);
            w.doing_leaders = outer;
            v += leader_ht + lx;
        }
        edge - 10
    }

    /// Executes a whatsit at TeX position (`h`, `v`) (`out_what`).
    fn out_what(
        &mut self,
        w: &mut Walker,
        p: NodeRef,
        h: i32,
        v: i32,
        ctx: &crate::pdfship::BoxCtx,
    ) {
        let NodeData::Whatsit(wh) = &self.nodes.get(p).data else {
            return;
        };
        let (x, y) = w.pos(h, v);
        match (**wh).clone() {
            Whatsit::Open { stream, name } if !w.doing_leaders => {
                self.open_write_stream(stream as i32, &name)
            }
            Whatsit::Write { stream, data } if !w.doing_leaders => self.write_out(stream, &data),
            Whatsit::Close { stream } if !w.doing_leaders => self.close_write_stream(stream as i32),
            Whatsit::Special { data } => self.out_special(w, h, v, &data),
            Whatsit::PdfLiteral { mode, data, .. } => {
                let bytes = match data {
                    crate::nodes::LateData::Bytes(b)
                    | crate::nodes::LateData::Lua { data: b, .. } => b,
                    crate::nodes::LateData::Function { .. } => Vec::new(),
                    crate::nodes::LateData::Tokens(t) => {
                        let toks = self.expand_late_tokens(&t);
                        self.print_to_string(|e| e.show_token_list(&toks, 0, toks.len(), i64::MAX))
                    }
                };
                if let Some(be) = w.backend.as_deref_mut() {
                    be.literal(mode, &bytes, x, y);
                }
            }
            Whatsit::LateLua { data, .. } => {
                let code = match data {
                    crate::nodes::LateData::Bytes(b)
                    | crate::nodes::LateData::Lua { data: b, .. } => Ok(b),
                    crate::nodes::LateData::Tokens(t) => {
                        let toks = self.expand_late_tokens(&t);
                        Ok(self.lua_code(&toks))
                    }
                    crate::nodes::LateData::Function { reference } => Err(reference),
                };
                // `pdf.getpos`, `pdf.print` and `pdf.registerannot` work on
                // this context while the code runs.
                self.pdf.pos = (x, y);
                let outer = self.pdf.late.replace(Default::default());
                match code {
                    Ok(code) => self.run_lua(&code),
                    // Observed: a function is called with the whatsit;
                    // the nodes it inserts after it are output next.
                    Err(r) => {
                        if let Some(host) = self.lua.clone()
                            && let Err(e) =
                                host.call_reference(self, r, crate::ReferenceArgs::Node(p))
                        {
                            self.lua_error(&e);
                        }
                    }
                }
                let ctx = std::mem::replace(&mut self.pdf.late, outer).unwrap_or_default();
                if let Some(be) = w.backend.as_deref_mut() {
                    for (mode, text) in &ctx.prints {
                        be.print(*mode, text, x, y);
                    }
                }
                self.pdf
                    .page
                    .annots
                    .extend(ctx.annots.into_iter().map(|a| (a, None)));
            }
            Whatsit::PdfRefobj { objnum } if !w.doing_leaders => self.ship_refobj(w, objnum),
            Whatsit::PdfAnnot { dims, objnum, data } if !w.doing_leaders => {
                self.ship_annot(w, ctx, h, v, dims, objnum, &data)
            }
            Whatsit::PdfStartLink {
                dims,
                objnum,
                attr,
                action,
            } if !w.doing_leaders => {
                self.ship_start_link(w, ctx, h, v, dims, objnum, &attr, &action)
            }
            Whatsit::PdfEndLink if !w.doing_leaders => self.ship_end_link(w, h, v),
            Whatsit::PdfDest {
                id,
                view,
                structure,
            } if !w.doing_leaders => self.ship_dest(w, ctx, h, v, &id, &view, structure),
            Whatsit::SavePos => {
                self.last_x_pos = x;
                self.last_y_pos = y;
            }
            Whatsit::PdfSave => {
                w.matrix_stack.push(w.matrix);
                if let Some(be) = w.backend.as_deref_mut() {
                    be.save(x, y);
                }
            }
            Whatsit::PdfRestore => {
                if let Some(m) = w.matrix_stack.pop() {
                    w.matrix = m;
                }
                if let Some(be) = w.backend.as_deref_mut() {
                    be.restore(x, y);
                }
            }
            Whatsit::PdfSetmatrix { data } => {
                w.set_matrix(x, y, &data);
                if let Some(be) = w.backend.as_deref_mut() {
                    be.set_matrix(x, y, &data);
                }
            }
            Whatsit::PdfColorstack { stack, cmd, data } => {
                let out = self.colorstack_op(stack, cmd, data);
                if let (Some((mode, lit)), Some(be)) = (out, w.backend.as_deref_mut()) {
                    be.literal(mode, &lit, x, y);
                }
            }
            _ => {}
        }
    }

    /// Outputs a `\special` at TeX position (`h`, `v`).
    fn out_special(&mut self, w: &mut Walker, h: i32, v: i32, data: &[u8]) {
        let (x, y) = w.pos(h, v);
        if let Some(d) = w.dvi.as_mut() {
            d.special(w.dvi_h + h, w.dvi_v + v, data);
        } else if let Some(be) = w.backend.as_deref_mut() {
            // Observed in PDF mode: `pdf:` specials (any case) are
            // literals, with an optional mode keyword; every other
            // special is dropped with a warning.
            if data.len() >= 4 && data[..4].eq_ignore_ascii_case(b"pdf:") {
                let rest = &data[4..];
                let (mode, text) = [
                    (&b"direct:"[..], 2),
                    (b"page:", 1),
                    (b"raw:", 3),
                    (b"text:", 4),
                    (b"origin:", 0),
                ]
                .iter()
                .find_map(|(k, m)| rest.strip_prefix(*k).map(|t| (*m, t)))
                .unwrap_or((crate::pdfext::literal_mode::ORIGIN, rest));
                be.literal(mode, text, x, y);
            } else {
                self.printer.print_nl("Non-PDF special ignored!");
            }
        }
    }

    /// Applies a colour-stack command; returns the literal to emit.
    fn colorstack_op(&mut self, stack: i32, cmd: u8, data: Vec<u8>) -> Option<(u8, Vec<u8>)> {
        use crate::pdfext::colorstack_cmd as c;
        self.pdf_ensure_colorstacks();
        let def = self.pdf.colorstacks.get(stack.max(0) as usize).cloned()?;
        let st = self
            .colorstack_values
            .entry(stack)
            .or_insert_with(|| vec![def.init.clone()]);
        match cmd {
            c::SET => {
                if let Some(top) = st.last_mut() {
                    *top = data;
                } else {
                    st.push(data);
                }
            }
            c::PUSH => st.push(data),
            c::POP => {
                if st.len() > 1 {
                    st.pop();
                }
            }
            _ => {}
        }
        let lit = st.last().cloned().unwrap_or_default();
        Some((def.mode, lit))
    }

    /// Expands a late token list (as `\write` does) and returns the
    /// expanded tokens.
    fn expand_late_tokens(&mut self, list: &crate::token::TokenList) -> Vec<crate::token::Token> {
        use crate::token::Token;
        use std::rc::Rc;
        self.ins_list(Rc::from(vec![
            Token::RIGHT_BRACE,
            Token::cs(self.cs.end_write),
        ]));
        self.begin_token_list(list.clone(), crate::input::TokKind::WriteText);
        self.ins_list(Rc::from(vec![Token::LEFT_BRACE]));
        let toks = self.scan_toks(false, true);
        self.get_token();
        toks
    }

    /// Finishes the output file at the end of the run and reports it.
    pub fn finish_backend(&mut self) {
        if let Some(f) = self.final_hook {
            f(self);
        }
        if self.dvi.pages() > 0 {
            self.finish_dvi();
        } else if self.pdf.output_opened && self.eqtb.int(ip::OUTPUTMODE) <= 0 {
            // LuaTeX opened the DVI file for `pdf.obj` and leaves it empty.
            let _ = std::fs::write(self.output_path("dvi"), b"");
        }
        let Some(mut be) = self.backend.take() else {
            return;
        };
        if self.pdf.fatal || self.total_pages == 0 {
            be.abandon(self.pdf.fatal);
            self.backend = Some(be);
            return;
        }
        if self.eqtb.int(ip::DRAFTMODE) > 0 && self.eqtb.int(ip::OUTPUTMODE) > 0 {
            // `-draftmode`: the document is typeset but no PDF is written
            // (the backend wrote to a scratch file, removed here). LuaTeX
            // prints this warning; unlike LuaTeX, which empties an
            // existing PDF file, retex leaves it as it is.
            be.abandon(true);
            self.backend = Some(be);
            self.printer
                .print_nl("warning  (pdf backend): draftmode enabled, not changing output pdf");
            self.printer.print_ln();
            return;
        }
        if self.total_pages > 0 {
            self.pdf_finish_document();
            self.flush_pending_objects(be.as_mut());
        }
        if self.total_pages > 0
            && let Some(fin) = be.finish(self)
        {
            // Observed: printed one after the other like C strings (log
            // lines up to 80 characters), right after what came before.
            for f in &fin.embedded {
                self.printer.print_lua_bytes(f.as_bytes());
            }
            self.pdf.objstm_stats = fin.objstm;
            self.print_output_written(&fin.file, self.total_pages, fin.size);
        }
        self.backend = Some(be);
    }

    /// The path of output file `<jobname>.<ext>` (in `-output-directory`).
    pub(crate) fn output_path(&self, ext: &str) -> std::path::PathBuf {
        let job =
            String::from_utf8_lossy(self.job_name.as_deref().unwrap_or(b"texput")).into_owned();
        let name = format!("{job}.{ext}");
        match &self.files.output_dir {
            Some(d) => d.join(&name),
            None => std::path::PathBuf::from(&name),
        }
    }

    /// Writes the postamble and the DVI file `<jobname>.dvi` (§642).
    fn finish_dvi(&mut self) {
        let mut dvi = std::mem::take(&mut self.dvi);
        let pages = dvi.pages();
        let data = dvi.finish(self);
        let path = self.output_path("dvi");
        let name = path
            .file_name()
            .map(|n| n.to_string_lossy().into_owned())
            .unwrap_or_default();
        if std::fs::write(&path, &data).is_err() {
            self.printer.print_nl("! I can't write on file `");
            self.printer.print_bytes(name.as_bytes());
            self.printer.print_str("'.");
            return;
        }
        self.print_output_written(&name, pages, data.len() as u64);
    }

    /// Prints `Output written on NAME (N pages, B bytes).`.
    fn print_output_written(&mut self, name: &str, pages: u32, size: u64) {
        self.output_written = Some((name.to_owned(), pages, size));
        self.printer.print_nl("Output written on ");
        self.printer.print_bytes(name.as_bytes());
        self.printer.print_str(" (");
        self.printer.print_int(i64::from(pages));
        self.printer
            .print_str(if pages == 1 { " page" } else { " pages" });
        self.printer.print_str(", ");
        self.printer.print_int(size as i64);
        self.printer.print_str(" bytes).");
    }
}

/// The state of a page being shipped: the outputs and the coordinate
/// systems they use.
#[derive(Default)]
pub(crate) struct Walker {
    /// The PDF backend (PDF mode).
    backend: Option<Box<dyn Backend>>,
    /// The DVI writer (DVI mode).
    dvi: Option<crate::dvi::DviWriter>,
    h_origin: i32,
    v_origin: i32,
    page_height: i32,
    /// The DVI position of TeX's origin (`\hoffset`, `\voffset`).
    dvi_h: i32,
    dvi_v: i32,
    /// Box nesting depth (`cur_s`): -1 outside the page box.
    pub(crate) cur_s: i32,
    /// Whether a leader box is being output (`doing_leaders`).
    doing_leaders: bool,
    /// Whether this is a page (not a box resource): annotations, links
    /// and destinations belong to pages.
    pub(crate) page: bool,
    /// Whether SyncTeX records this sheet.
    sync: bool,
    /// The transformation `\pdfextension setmatrix` set up, in page
    /// coordinates (sp): `[a, b, c, d, e, f]` maps (x, y) to
    /// (ax + cy + e, bx + dy + f); `None` is the identity.
    pub(crate) matrix: Option<[f64; 6]>,
    /// The transformations `\pdfextension save` keeps for `restore`.
    matrix_stack: Vec<Option<[f64; 6]>>,
}

impl Walker {
    /// Page coordinates (from the lower left, y up) of TeX point
    /// (`h`, `v`) measured from the origin, v downwards.
    pub(crate) fn pos(&self, h: i32, v: i32) -> (i32, i32) {
        (self.h_origin + h, self.page_height - (self.v_origin + v))
    }

    /// `\pdfextension setmatrix{a b c d}` at page point (`x`, `y`): the
    /// matrix applies around that point, after the current one.
    fn set_matrix(&mut self, x: i32, y: i32, data: &[u8]) {
        let text = String::from_utf8_lossy(data);
        let v: Vec<f64> = text
            .split_ascii_whitespace()
            .filter_map(|t| t.parse::<f64>().ok())
            .collect();
        let [a, b, c, d] = match v.as_slice() {
            [a, b, c, d, ..] => [*a, *b, *c, *d],
            _ => return,
        };
        let (x, y) = (f64::from(x), f64::from(y));
        // p -> (x, y) + M (p - (x, y)), then the current matrix.
        let m = [a, b, c, d, x - a * x - c * y, y - b * x - d * y];
        self.matrix = Some(match self.matrix {
            None => m,
            Some(o) => [
                o[0] * m[0] + o[2] * m[1],
                o[1] * m[0] + o[3] * m[1],
                o[0] * m[2] + o[2] * m[3],
                o[1] * m[2] + o[3] * m[3],
                o[0] * m[4] + o[2] * m[5] + o[4],
                o[1] * m[4] + o[3] * m[5] + o[5],
            ],
        });
    }
}

/// The bounding box of rectangle `r` (`[x1, y1, x2, y2]`, page
/// coordinates) under transformation `m` (observed: LuaTeX transforms
/// the rectangles of links and annotations, before adding the margin).
pub(crate) fn transform_rect(m: Option<[f64; 6]>, r: [i32; 4]) -> [i32; 4] {
    let Some(m) = m else { return r };
    let corners = [(r[0], r[1]), (r[2], r[1]), (r[0], r[3]), (r[2], r[3])];
    let (mut lo_x, mut lo_y, mut hi_x, mut hi_y) = (f64::MAX, f64::MAX, f64::MIN, f64::MIN);
    for (x, y) in corners {
        let (x, y) = (f64::from(x), f64::from(y));
        let tx = m[0] * x + m[2] * y + m[4];
        let ty = m[1] * x + m[3] * y + m[5];
        lo_x = lo_x.min(tx);
        lo_y = lo_y.min(ty);
        hi_x = hi_x.max(tx);
        hi_y = hi_y.max(ty);
    }
    let r = |v: f64| v.round().clamp(f64::from(i32::MIN), f64::from(i32::MAX)) as i32;
    [r(lo_x), r(lo_y), r(hi_x), r(hi_y)]
}

/// The state of a virtual character's packet being run.
#[derive(Clone)]
pub(crate) struct PacketState {
    /// The current point.
    h: i32,
    v: i32,
    /// The current font.
    font: u32,
    /// The points saved by `push`.
    stack: Vec<(i32, i32)>,
    /// The expansion factor of the virtual character.
    ef: i32,
    /// How deeply virtual characters are nested.
    depth: u32,
    /// The virtual font, its id and the character.
    vf: std::rc::Rc<crate::fonts::VirtualFont>,
    vfont: u32,
    chr: u32,
}

/// A packet whose `lua` command is running, with the output it draws
/// into.
pub(crate) struct VfFrame {
    walker: Walker,
    state: PacketState,
}