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::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);
    /// 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);
    }

    /// 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,
    ) {
    }

    /// 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,
    /// Font files embedded, printed as `<path>` (LuaTeX order).
    pub embedded: Vec<String>,
    /// Objects written into object streams, and the number of streams.
    pub objstm: (u32, u32),
}

/// The glue-rounding state of a box being shipped (`cur_g`, `cur_glue`).
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.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 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,
        };
        let cur_h = 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);
            for n in std::mem::take(&mut self.pdf.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);
        }
    }

    /// 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(&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(
        &self,
        w: &mut Walker,
        font: u32,
        chr: u32,
        h: i32,
        v: i32,
        ef: i32,
        depth: u32,
    ) {
        if let Some(vf) = &self.font(font).vf
            && let Some(cmds) = vf.packets.get(&chr)
        {
            if depth < 8 {
                self.out_packet(w, vf, cmds, h, v, ef, depth);
            }
            return;
        }
        let (x, y) = w.pos(h, v);
        if let Some(be) = w.backend.as_deref_mut() {
            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 the packet of a virtual character whose reference point is at
    /// (`h`, `v`): 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). Specials in
    /// packets are dropped, as LuaTeX does.
    #[allow(clippy::too_many_arguments)]
    fn out_packet(
        &self,
        w: &mut Walker,
        vf: &crate::fonts::VirtualFont,
        cmds: &[retex_font::vf::Command],
        mut h: i32,
        mut v: i32,
        ef: i32,
        depth: u32,
    ) {
        use retex_font::vf::Command;
        let mut f = vf.fonts.first().copied().unwrap_or(0);
        let mut stack: Vec<(i32, i32)> = Vec::new();
        for c in cmds {
            match c {
                Command::Font(i) => f = vf.fonts.get(*i).copied().unwrap_or(0),
                Command::Char(c) => {
                    if f != 0 && self.font(f).chars.contains_key(c) {
                        self.out_glyph_at_depth(w, f, *c, h, v, ef, depth + 1);
                        h = h.wrapping_add(crate::expansion::expanded_width(
                            self.font_char_dimen(f, *c, 0),
                            ef,
                        ));
                    }
                }
                Command::Rule { height, width } => {
                    if *height > 0 && *width > 0 {
                        Self::out_rule(w, h, v, *width, *height);
                    }
                    h = h.wrapping_add(*width);
                }
                Command::Right(x) => h = h.wrapping_add(*x),
                Command::Down(y) => v = v.wrapping_add(*y),
                Command::Push => stack.push((h, v)),
                Command::Pop => {
                    if let Some((sh, sv)) = stack.pop() {
                        (h, v) = (sh, sv);
                    }
                }
                Command::Special(_) => {}
            }
        }
    }

    /// 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,
        };
        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);
        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]);
        }
        let mut p = b.head;
        while !p.is_null() {
            let next = self.nodes.next(p);
            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.pdf.map_note_done
                        && w.backend.is_some()
                        && self.fonts.char_metrics(font, chr).is_some()
                    {
                        // Observed: LuaTeX reads the map file when the
                        // first character is output; a character missing
                        // from its font (in \nullfont, say) is not.
                        self.pdf.map_note_done = true;
                        self.print_map_file_note("pdftex.map");
                    }
                    self.check_lost_char(p);
                    self.out_glyph(w, font, chr, cur_h + xo, 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),
                NodeData::Disc { replace, .. } => {
                    // A discretionary that was not broken shows its
                    // replacement text.
                    let r = *replace;
                    let mut q = r;
                    while !q.is_null() {
                        if let NodeData::Glyph(g) = &self.nodes.get(q).data {
                            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,
                            );
                        } else if let NodeData::Kern {
                            kern,
                            expansion_factor,
                        } = &self.nodes.get(q).data
                        {
                            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;
                        }
                        q = self.nodes.next(q);
                    }
                }
                _ => {}
            }
            p = next;
        }
        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);
    }

    /// 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),
                _ => {}
            }
            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 } => {
                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!");
                    }
                }
            }
            Whatsit::PdfLiteral { mode, data, .. } => {
                let bytes = match data {
                    crate::nodes::LateData::Bytes(b)
                    | crate::nodes::LateData::Lua { data: b, .. } => b,
                    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, .. } => b,
                    crate::nodes::LateData::Tokens(t) => {
                        let toks = self.expand_late_tokens(&t);
                        self.lua_code(&toks)
                    }
                };
                // `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());
                self.run_lua(&code);
                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.literal(*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 => {
                if let Some(be) = w.backend.as_deref_mut() {
                    be.save(x, y);
                }
            }
            Whatsit::PdfRestore => {
                if let Some(be) = w.backend.as_deref_mut() {
                    be.restore(x, y);
                }
            }
            Whatsit::PdfSetmatrix { 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);
                }
            }
            _ => {}
        }
    }

    /// 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 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 {
                let mut text = b"<".to_vec();
                text.extend_from_slice(f.as_bytes());
                text.push(b'>');
                self.printer.print_lua_bytes(&text);
            }
            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.
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,
}

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))
    }
}