retex_engine/

nodes.rs

//! Node memory: an arena of typesetting nodes addressed by [`NodeRef`].
//!
//! The node model mirrors LuaTeX's. Node type ids, subtypes and field sets
//! are those that LuaTeX's `node` library reports (see
//! `data/luatex-node-types.txt`). Lists are doubly linked through `next` and
//! `prev`. List heads in the semantic nest are `temp` nodes, as in TeX.

use std::rc::Rc;

use crate::glue::Glue;
use crate::token::TokenList;

/// LuaTeX's node types, fields and subtypes, as `node.types()`,
/// `node.fields()` and `node.subtypes()` report them
/// (`data/luatex-node-types.txt`, see `data/README.md`).
pub const LUATEX_NODE_TYPES: &str = include_str!("../data/luatex-node-types.txt");

/// A reference to a node in the node arena; `NodeRef::NULL` is the empty
/// list.
#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, Default, PartialOrd, Ord)]
pub struct NodeRef(pub u32);

impl NodeRef {
    /// The null pointer.
    pub const NULL: NodeRef = NodeRef(0);

    /// Whether this is the null pointer.
    #[inline]
    pub const fn is_null(self) -> bool {
        self.0 == 0
    }
}

/// A "running" rule dimension (TeX's `null_flag`, −2³⁰).
pub const RUNNING: i32 = -0o10000000000;

/// Node type ids, numbered as LuaTeX's `node.types()`.
#[allow(missing_docs)]
pub mod id {
    pub const HLIST: u8 = 0;
    pub const VLIST: u8 = 1;
    pub const RULE: u8 = 2;
    pub const INS: u8 = 3;
    pub const MARK: u8 = 4;
    pub const ADJUST: u8 = 5;
    pub const BOUNDARY: u8 = 6;
    pub const DISC: u8 = 7;
    pub const WHATSIT: u8 = 8;
    pub const LOCAL_PAR: u8 = 9;
    pub const DIR: u8 = 10;
    pub const MATH: u8 = 11;
    pub const GLUE: u8 = 12;
    pub const KERN: u8 = 13;
    pub const PENALTY: u8 = 14;
    pub const UNSET: u8 = 15;
    pub const STYLE: u8 = 16;
    pub const CHOICE: u8 = 17;
    pub const NOAD: u8 = 18;
    pub const RADICAL: u8 = 19;
    pub const FRACTION: u8 = 20;
    pub const ACCENT: u8 = 21;
    pub const FENCE: u8 = 22;
    pub const MATH_CHAR: u8 = 23;
    pub const SUB_BOX: u8 = 24;
    pub const SUB_MLIST: u8 = 25;
    pub const MATH_TEXT_CHAR: u8 = 26;
    pub const DELIM: u8 = 27;
    pub const MARGIN_KERN: u8 = 28;
    pub const GLYPH: u8 = 29;
    pub const ALIGN_RECORD: u8 = 30;
    pub const PAGE_INSERT: u8 = 33;
    pub const SPLIT_INSERT: u8 = 34;
    pub const TEMP: u8 = 41;
}

/// Glue subtypes (LuaTeX numbering).
#[allow(missing_docs)]
pub mod glue_sub {
    pub const USER: u16 = 0;
    pub const LINE_SKIP: u16 = 1;
    pub const BASELINE_SKIP: u16 = 2;
    pub const PAR_SKIP: u16 = 3;
    pub const ABOVE_DISPLAY: u16 = 4;
    pub const BELOW_DISPLAY: u16 = 5;
    pub const ABOVE_DISPLAY_SHORT: u16 = 6;
    pub const BELOW_DISPLAY_SHORT: u16 = 7;
    pub const LEFT_SKIP: u16 = 8;
    pub const RIGHT_SKIP: u16 = 9;
    pub const TOP_SKIP: u16 = 10;
    pub const SPLIT_TOP_SKIP: u16 = 11;
    pub const TAB_SKIP: u16 = 12;
    pub const SPACE_SKIP: u16 = 13;
    pub const XSPACE_SKIP: u16 = 14;
    pub const PAR_FILL_SKIP: u16 = 15;
    pub const MATH_SKIP: u16 = 16;
    pub const THIN_MU_SKIP: u16 = 17;
    pub const MED_MU_SKIP: u16 = 18;
    pub const THICK_MU_SKIP: u16 = 19;
    pub const COND_MATH_GLUE: u16 = 98;
    pub const MU_GLUE: u16 = 99;
    pub const A_LEADERS: u16 = 100;
    pub const C_LEADERS: u16 = 101;
    pub const X_LEADERS: u16 = 102;
    pub const G_LEADERS: u16 = 103;
}

/// Kern subtypes.
#[allow(missing_docs)]
pub mod kern_sub {
    pub const FONT: u16 = 0;
    pub const USER: u16 = 1;
    pub const ACCENT: u16 = 2;
    pub const ITALIC: u16 = 3;
}

/// Glyph subtypes (bit flags).
#[allow(missing_docs)]
pub mod glyph_sub {
    pub const CHARACTER: u16 = 1;
    pub const LIGATURE: u16 = 2;
    pub const GHOST: u16 = 4;
    pub const LEFT: u16 = 8;
    pub const RIGHT: u16 = 16;
}

/// Whatsit subtypes.
#[allow(missing_docs)]
pub mod whatsit_sub {
    pub const OPEN: u16 = 0;
    pub const WRITE: u16 = 1;
    pub const CLOSE: u16 = 2;
    pub const SPECIAL: u16 = 3;
    pub const LATE_SPECIAL: u16 = 4;
    pub const SAVE_POS: u16 = 7;
    pub const LATE_LUA: u16 = 8;
    pub const USER_DEFINED: u16 = 9;
    pub const PDF_LITERAL: u16 = 16;
    pub const PDF_LATE_LITERAL: u16 = 17;
    pub const PDF_REFOBJ: u16 = 18;
    pub const PDF_ANNOT: u16 = 19;
    pub const PDF_START_LINK: u16 = 20;
    pub const PDF_END_LINK: u16 = 21;
    pub const PDF_DEST: u16 = 22;
    pub const PDF_ACTION: u16 = 23;
    pub const PDF_THREAD: u16 = 24;
    pub const PDF_START_THREAD: u16 = 25;
    pub const PDF_END_THREAD: u16 = 26;
    pub const PDF_COLORSTACK: u16 = 29;
    pub const PDF_SETMATRIX: u16 = 30;
    pub const PDF_SAVE: u16 = 31;
    pub const PDF_RESTORE: u16 = 32;
    pub const PDF_LINK_STATE: u16 = 33;
}

/// A list of attribute (number, value) pairs, sorted by number.
pub type AttrList = Rc<[(u32, i32)]>;

/// Box fields shared by hlist and vlist nodes.
#[derive(Clone, Debug, Default, PartialEq)]
pub struct BoxData {
    /// Width.
    pub width: i32,
    /// Depth.
    pub depth: i32,
    /// Height.
    pub height: i32,
    /// Direction (0 = TLT).
    pub dir: i8,
    /// Shift amount.
    pub shift: i32,
    /// Glue order of the setting.
    pub glue_order: u8,
    /// Glue sign: 0 normal, 1 stretching, 2 shrinking.
    pub glue_sign: u8,
    /// Glue set ratio. LuaTeX keeps it in single precision, so computed
    /// ratios are rounded to `f32` (see [`glue_ratio`]).
    pub glue_set: f64,
    /// The list.
    pub head: NodeRef,
}

/// Fields of a glyph node.
#[derive(Clone, Debug, Default, PartialEq)]
pub struct GlyphData {
    /// The character.
    pub chr: u32,
    /// The font.
    pub font: u32,
    /// The language.
    pub lang: u16,
    /// `\lefthyphenmin` for this glyph.
    pub left: u8,
    /// `\righthyphenmin` for this glyph.
    pub right: u8,
    /// `\uchyph`.
    pub uchyph: bool,
    /// Ligature components.
    pub components: NodeRef,
    /// Horizontal offset.
    pub xoffset: i32,
    /// Vertical offset.
    pub yoffset: i32,
    /// Font expansion factor.
    pub expansion_factor: i32,
    /// User data.
    pub data: i32,
}

/// Type-specific node data.
#[derive(Clone, Debug, PartialEq)]
pub enum NodeData {
    /// A list head or other temporary node.
    Temp,
    /// An hlist or vlist (`id` tells which).
    Box(Box<BoxData>),
    /// A rule.
    Rule {
        /// Width (or "running").
        width: i32,
        /// Depth.
        depth: i32,
        /// Height.
        height: i32,
        /// Direction.
        dir: i8,
        /// Resource index (box/image rules).
        index: i32,
        /// Left offset.
        left: i32,
        /// Right offset.
        right: i32,
    },
    /// An insertion.
    Ins {
        /// `\floatingpenalty`.
        cost: i32,
        /// Depth.
        depth: i32,
        /// Natural height plus depth.
        height: i32,
        /// `\splittopskip`.
        spec: Glue,
        /// The vertical list.
        head: NodeRef,
    },
    /// A mark.
    Mark {
        /// The marks class.
        class: u32,
        /// The token list.
        mark: TokenList,
    },
    /// A `\vadjust`.
    Adjust {
        /// The vertical list.
        head: NodeRef,
    },
    /// A boundary.
    Boundary {
        /// The value.
        value: i32,
    },
    /// A discretionary.
    Disc {
        /// Pre-break list.
        pre: NodeRef,
        /// Post-break list.
        post: NodeRef,
        /// Replacement list.
        replace: NodeRef,
        /// Penalty.
        penalty: i32,
    },
    /// A whatsit.
    Whatsit(Box<Whatsit>),
    /// A local paragraph node.
    LocalPar {
        /// `\localinterlinepenalty`.
        pen_inter: i32,
        /// `\localbrokenpenalty`.
        pen_broken: i32,
        /// Paragraph direction.
        dir: i8,
        /// `\localleftbox`.
        box_left: NodeRef,
        /// Its width.
        box_left_width: i32,
        /// `\localrightbox`.
        box_right: NodeRef,
        /// Its width.
        box_right_width: i32,
    },
    /// A direction change.
    Dir {
        /// The direction.
        dir: i8,
        /// The group level.
        level: i32,
    },
    /// Math on/off.
    Math {
        /// `\mathsurround`.
        surround: i32,
        /// `\mathsurroundskip` as glue.
        glue: Glue,
    },
    /// Glue.
    Glue {
        /// The specification.
        spec: Glue,
        /// Leader box or rule.
        leader: NodeRef,
    },
    /// A kern.
    Kern {
        /// The amount.
        kern: i32,
        /// Font expansion factor.
        expansion_factor: i32,
    },
    /// A penalty.
    Penalty {
        /// The penalty.
        penalty: i32,
    },
    /// An unset box in an alignment.
    Unset {
        /// Box fields (glue_set unused).
        b: Box<BoxData>,
        /// Number of spanned columns minus one.
        span_count: u16,
        /// Total stretch.
        stretch: i32,
        /// Total shrink.
        shrink: i32,
        /// Stretch order.
        stretch_order: u8,
        /// Shrink order.
        shrink_order: u8,
    },
    /// A glyph (stored inline: glyphs are the most frequent nodes).
    Glyph(GlyphData),
    /// A margin kern.
    MarginKern {
        /// Width.
        width: i32,
        /// The glyph it belongs to.
        glyph: NodeRef,
    },
    /// A noad (`noad`, `radical` and `accent` ids).
    Noad(Box<NoadData>),
    /// A generalized fraction noad.
    Fraction(Box<FractionData>),
    /// A `\left`, `\middle` or `\right` noad.
    Fence(Box<FenceData>),
    /// A style node (`\displaystyle` …); the style is 0–7 as in TeX.
    Style {
        /// The style.
        style: u8,
    },
    /// A `\mathchoice` node: display, text, script and scriptscript lists.
    Choice(Box<[NodeRef; 4]>),
    /// A `math_char` or `math_text_char` kernel.
    MathChar {
        /// The family.
        fam: u32,
        /// The character.
        chr: u32,
    },
    /// A `sub_box` or `sub_mlist` kernel.
    SubList {
        /// The box (sub_box) or the mlist (sub_mlist).
        head: NodeRef,
    },
    /// A delimiter specification (`delim` node).
    Delim {
        /// Family of the small variant.
        small_fam: u32,
        /// Character of the small variant.
        small_char: u32,
        /// Family of the large variant.
        large_fam: u32,
        /// Character of the large variant.
        large_char: u32,
    },
    /// Nodes not modelled in detail.
    Other(Vec<i64>),
}

/// Fields of a noad (LuaTeX's `noad`, `radical` and `accent` nodes). The
/// nucleus and the scripts are kernel nodes (`math_char`,
/// `math_text_char`, `sub_box`, `sub_mlist`), or null when empty.
#[derive(Clone, Debug, Default, PartialEq)]
pub struct NoadData {
    /// The nucleus.
    pub nucleus: NodeRef,
    /// The subscript.
    pub sub: NodeRef,
    /// The superscript.
    pub sup: NodeRef,
    /// Rendering options (LuaTeX's option bits).
    pub options: u32,
    /// Radicals: the delimiter (a `delim` node).
    pub left: NodeRef,
    /// Radicals: the degree of `\Uroot`.
    pub degree: NodeRef,
    /// Radicals: the requested width (`\Uhextensible`, `width` keyword).
    pub width: i32,
    /// Accents: the top accent (a `math_char` kernel).
    pub accent: NodeRef,
    /// Accents: the bottom accent.
    pub bot_accent: NodeRef,
    /// Accents: the `fraction` criterion (0 when not given).
    pub fraction: i32,
    /// The translation into an hlist (`new_hlist`), during
    /// `mlist_to_hlist`.
    pub new_hlist: NodeRef,
}

/// Fields of a generalized fraction noad.
#[derive(Clone, Debug, PartialEq)]
pub struct FractionData {
    /// Rule thickness, or [`DEFAULT_CODE`].
    pub thickness: i32,
    /// The numerator (a `sub_mlist` kernel).
    pub num: NodeRef,
    /// The denominator (a `sub_mlist` kernel).
    pub denom: NodeRef,
    /// Left delimiter (`delim` node) or null.
    pub left: NodeRef,
    /// Right delimiter or null.
    pub right: NodeRef,
    /// Middle delimiter (`\Uskewed`) or null.
    pub middle: NodeRef,
    /// Rendering options.
    pub options: u32,
    /// The translation (`new_hlist`).
    pub new_hlist: NodeRef,
}

/// Fields of a fence noad (`\left`, `\middle`, `\right`).
#[derive(Clone, Debug, Default, PartialEq)]
pub struct FenceData {
    /// The delimiter (a `delim` node).
    pub delim: NodeRef,
    /// Italic correction.
    pub italic: i32,
    /// Requested height (0 when not given).
    pub height: i32,
    /// Requested depth.
    pub depth: i32,
    /// Rendering options.
    pub options: u32,
    /// Spacing class (−1 when not given).
    pub class: i32,
    /// The translation (`new_hlist`).
    pub new_hlist: NodeRef,
}

/// The fraction thickness meaning "the default rule thickness"
/// (`default_code`).
pub const DEFAULT_CODE: i32 = 0o10000000000;

/// Noad subtypes (LuaTeX numbering).
#[allow(missing_docs)]
pub mod noad_sub {
    pub const ORD: u16 = 0;
    pub const OP_DISPLAY_LIMITS: u16 = 1;
    pub const OP_LIMITS: u16 = 2;
    pub const OP_NO_LIMITS: u16 = 3;
    pub const BIN: u16 = 4;
    pub const REL: u16 = 5;
    pub const OPEN: u16 = 6;
    pub const CLOSE: u16 = 7;
    pub const PUNCT: u16 = 8;
    pub const INNER: u16 = 9;
    pub const UNDER: u16 = 10;
    pub const OVER: u16 = 11;
    pub const VCENTER: u16 = 12;
}

/// Radical subtypes.
#[allow(missing_docs)]
pub mod radical_sub {
    pub const RADICAL: u16 = 0;
    pub const URADICAL: u16 = 1;
    pub const UROOT: u16 = 2;
    pub const UUNDERDELIMITER: u16 = 3;
    pub const UOVERDELIMITER: u16 = 4;
    pub const UDELIMITERUNDER: u16 = 5;
    pub const UDELIMITEROVER: u16 = 6;
    pub const UHEXTENSIBLE: u16 = 7;
}

/// Fence subtypes.
#[allow(missing_docs)]
pub mod fence_sub {
    pub const UNSET: u16 = 0;
    pub const LEFT: u16 = 1;
    pub const MIDDLE: u16 = 2;
    pub const RIGHT: u16 = 3;
    pub const NO: u16 = 4;
}

/// Accent subtypes.
#[allow(missing_docs)]
pub mod accent_sub {
    pub const BOTH_FLEXIBLE: u16 = 0;
    pub const FIXED_TOP: u16 = 1;
    pub const FIXED_BOTTOM: u16 = 2;
    pub const FIXED_BOTH: u16 = 3;
}

/// Noad option bits (LuaTeX manual, "Math core nodes").
#[allow(missing_docs)]
pub mod noad_opt {
    pub const SET: u32 = 0x08;
    pub const AXIS: u32 = 0x02 | SET;
    pub const NO_AXIS: u32 = 0x04 | SET;
    pub const EXACT: u32 = 0x10 | SET;
    pub const LEFT: u32 = 0x11 | SET;
    pub const MIDDLE: u32 = 0x12 | SET;
    pub const RIGHT: u32 = 0x14 | SET;
    pub const NO_SUB_SCRIPT: u32 = 0x21 | SET;
    pub const NO_SUPER_SCRIPT: u32 = 0x22 | SET;
    /// retex: an overlay accent (`\Umathaccent overlay`).
    pub const OVERLAY: u32 = 0x100;
}

/// Whatsit payloads.
#[derive(Clone, Debug, PartialEq)]
pub enum Whatsit {
    /// `\openout`.
    Open {
        /// Stream number.
        stream: u32,
        /// File name.
        name: Vec<u8>,
    },
    /// `\write`.
    Write {
        /// Stream number.
        stream: i32,
        /// Unexpanded token list.
        data: TokenList,
    },
    /// `\closeout`.
    Close {
        /// Stream number.
        stream: u32,
    },
    /// `\special`.
    Special {
        /// The text.
        data: Vec<u8>,
    },
    /// `\latelua`.
    LateLua {
        /// Token list or string.
        data: LateData,
        /// Chunk name.
        name: Vec<u8>,
    },
    /// `\pdfextension literal` and friends.
    PdfLiteral {
        /// Mode (0 origin, 1 page, 2 direct, …).
        mode: u8,
        /// Data.
        data: LateData,
        /// Whether this is a late literal.
        late: bool,
    },
    /// `\savepos`.
    SavePos,
    /// `\pdfextension colorstack`.
    PdfColorstack {
        /// Stack number.
        stack: i32,
        /// Command (set, push, pop, current).
        cmd: u8,
        /// Data.
        data: Vec<u8>,
    },
    /// `\pdfextension setmatrix`.
    PdfSetmatrix {
        /// The matrix text.
        data: Vec<u8>,
    },
    /// `\pdfextension save`.
    PdfSave,
    /// `\pdfextension restore`.
    PdfRestore,
    /// `\pdfextension annot`.
    PdfAnnot {
        /// `width`, `height`, `depth` ([`RUNNING`] when not given).
        dims: [i32; 3],
        /// The annotation's object number.
        objnum: i32,
        /// The annotation's text.
        data: Vec<u8>,
    },
    /// `\pdfextension startlink`.
    PdfStartLink {
        /// `width`, `height`, `depth` ([`RUNNING`] when not given).
        dims: [i32; 3],
        /// The object number of the link's first annotation.
        objnum: i32,
        /// `attr {…}`.
        attr: Vec<u8>,
        /// The action.
        action: crate::pdfext::PdfAction,
    },
    /// `\pdfextension endlink`.
    PdfEndLink,
    /// `\pdfextension dest`.
    PdfDest {
        /// The destination's identifier.
        id: crate::pdfext::DestId,
        /// The view.
        view: crate::pdfext::DestView,
    },
    /// `\pdfextension refobj`.
    PdfRefobj {
        /// The object number.
        objnum: i32,
    },
    /// Other whatsits, kept opaque for now.
    Other {
        /// Raw fields.
        fields: Vec<i64>,
        /// Raw data.
        data: Vec<u8>,
    },
}

/// Data of late whatsits: an unexpanded token list or a string.
#[derive(Clone, Debug, PartialEq)]
pub enum LateData {
    /// Tokens, expanded at shipout.
    Tokens(TokenList),
    /// An already expanded string.
    Bytes(Vec<u8>),
}

/// A node.
#[derive(Clone, Debug, PartialEq)]
pub struct Node {
    /// The type id.
    pub id: u8,
    /// The subtype.
    pub subtype: u16,
    /// Next node in the list.
    pub next: NodeRef,
    /// Previous node in the list.
    pub prev: NodeRef,
    /// Attributes.
    pub attr: Option<AttrList>,
    /// Type-specific data.
    pub data: NodeData,
}

/// The node arena.
#[derive(Debug, Clone)]
pub struct Nodes {
    nodes: Vec<Node>,
    free: Vec<u32>,
    /// Number of nodes in use.
    pub in_use: usize,
}

impl Default for Nodes {
    fn default() -> Self {
        Self::new()
    }
}

impl Nodes {
    /// An arena with only the null node.
    pub fn new() -> Self {
        Nodes {
            nodes: vec![Node {
                id: id::TEMP,
                subtype: 0,
                next: NodeRef::NULL,
                prev: NodeRef::NULL,
                attr: None,
                data: NodeData::Temp,
            }],
            free: Vec::new(),
            in_use: 0,
        }
    }

    /// The number of node slots in the arena.
    pub fn capacity(&self) -> usize {
        self.nodes.len()
    }

    /// Allocates a node.
    pub fn alloc(&mut self, id: u8, subtype: u16, data: NodeData) -> NodeRef {
        let node = Node {
            id,
            subtype,
            next: NodeRef::NULL,
            prev: NodeRef::NULL,
            attr: None,
            data,
        };
        self.in_use += 1;
        if let Some(i) = self.free.pop() {
            self.nodes[i as usize] = node;
            NodeRef(i)
        } else {
            self.nodes.push(node);
            NodeRef(self.nodes.len() as u32 - 1)
        }
    }

    /// Frees a single node (not its sublists).
    pub fn free(&mut self, p: NodeRef) {
        if p.is_null() {
            return;
        }
        self.nodes[p.0 as usize].data = NodeData::Temp;
        self.nodes[p.0 as usize].attr = None;
        self.free.push(p.0);
        self.in_use -= 1;
    }

    /// The node at `p`.
    #[inline]
    pub fn get(&self, p: NodeRef) -> &Node {
        &self.nodes[p.0 as usize]
    }

    /// The node at `p`, mutably.
    #[inline]
    pub fn get_mut(&mut self, p: NodeRef) -> &mut Node {
        &mut self.nodes[p.0 as usize]
    }

    /// The type id of `p`.
    #[inline]
    pub fn id(&self, p: NodeRef) -> u8 {
        self.nodes[p.0 as usize].id
    }

    /// The `next` link of `p`.
    #[inline]
    pub fn next(&self, p: NodeRef) -> NodeRef {
        self.nodes[p.0 as usize].next
    }

    /// Links `q` after `p` (sets `p.next` and `q.prev`).
    #[inline]
    pub fn link(&mut self, p: NodeRef, q: NodeRef) {
        self.nodes[p.0 as usize].next = q;
        if !q.is_null() {
            self.nodes[q.0 as usize].prev = p;
        }
    }

    /// The box data of an hlist/vlist node.
    pub fn box_data(&self, p: NodeRef) -> Option<&BoxData> {
        match &self.nodes[p.0 as usize].data {
            NodeData::Box(b) => Some(b),
            NodeData::Unset { b, .. } => Some(b),
            _ => None,
        }
    }

    /// The box data of an hlist/vlist node, mutably.
    pub fn box_data_mut(&mut self, p: NodeRef) -> Option<&mut BoxData> {
        match &mut self.nodes[p.0 as usize].data {
            NodeData::Box(b) => Some(b),
            NodeData::Unset { b, .. } => Some(b),
            _ => None,
        }
    }

    /// The last node of the list starting at `p`.
    pub fn tail_of(&self, mut p: NodeRef) -> NodeRef {
        if p.is_null() {
            return p;
        }
        loop {
            let n = self.next(p);
            if n.is_null() {
                return p;
            }
            p = n;
        }
    }

    /// Frees a whole node list, including sublists (`flush_node_list`).
    pub fn flush_list(&mut self, p: NodeRef) {
        let mut stack: Vec<NodeRef> = Vec::new();
        let mut p = p;
        loop {
            while !p.is_null() {
                let next = self.next(p);
                match &self.nodes[p.0 as usize].data {
                    NodeData::Box(b) => stack.push(b.head),
                    NodeData::Unset { b, .. } => stack.push(b.head),
                    NodeData::Ins { head, .. } | NodeData::Adjust { head } => stack.push(*head),
                    NodeData::Disc {
                        pre, post, replace, ..
                    } => {
                        stack.push(*pre);
                        stack.push(*post);
                        stack.push(*replace);
                    }
                    NodeData::Glue { leader, .. } => stack.push(*leader),
                    NodeData::Glyph(g) => {
                        if !g.components.is_null() {
                            stack.push(g.components);
                        }
                    }
                    NodeData::LocalPar {
                        box_left,
                        box_right,
                        ..
                    } => {
                        stack.push(*box_left);
                        stack.push(*box_right);
                    }
                    NodeData::Noad(n) => stack.extend([
                        n.nucleus,
                        n.sub,
                        n.sup,
                        n.left,
                        n.degree,
                        n.accent,
                        n.bot_accent,
                        n.new_hlist,
                    ]),
                    NodeData::Fraction(f) => {
                        stack.extend([f.num, f.denom, f.left, f.right, f.middle, f.new_hlist])
                    }
                    NodeData::Fence(f) => stack.extend([f.delim, f.new_hlist]),
                    NodeData::Choice(c) => stack.extend(c.iter().copied()),
                    NodeData::SubList { head } => stack.push(*head),
                    _ => {}
                }
                self.free(p);
                p = next;
            }
            match stack.pop() {
                Some(q) => p = q,
                None => return,
            }
        }
    }

    /// Copies a whole node list, including sublists (`copy_node_list`).
    pub fn copy_list(&mut self, mut p: NodeRef) -> NodeRef {
        let mut head = NodeRef::NULL;
        let mut tail = NodeRef::NULL;
        while !p.is_null() {
            let q = self.copy_node(p);
            if head.is_null() {
                head = q;
            } else {
                self.link(tail, q);
            }
            tail = q;
            p = self.next(p);
        }
        head
    }

    /// Copies one node with its sublists; the copy's links are null.
    pub fn copy_node(&mut self, p: NodeRef) -> NodeRef {
        let mut node = self.nodes[p.0 as usize].clone();
        node.next = NodeRef::NULL;
        node.prev = NodeRef::NULL;
        match &mut node.data {
            NodeData::Box(b) => b.head = self.copy_list(b.head),
            NodeData::Unset { b, .. } => b.head = self.copy_list(b.head),
            NodeData::Ins { head, .. } | NodeData::Adjust { head } => *head = self.copy_list(*head),
            NodeData::Disc {
                pre, post, replace, ..
            } => {
                *pre = self.copy_list(*pre);
                *post = self.copy_list(*post);
                *replace = self.copy_list(*replace);
            }
            NodeData::Glue { leader, .. } => *leader = self.copy_list(*leader),
            NodeData::Glyph(g) => g.components = self.copy_list(g.components),
            NodeData::LocalPar {
                box_left,
                box_right,
                ..
            } => {
                *box_left = self.copy_list(*box_left);
                *box_right = self.copy_list(*box_right);
            }
            NodeData::Noad(n) => {
                for f in [
                    &mut n.nucleus,
                    &mut n.sub,
                    &mut n.sup,
                    &mut n.left,
                    &mut n.degree,
                    &mut n.accent,
                    &mut n.bot_accent,
                    &mut n.new_hlist,
                ] {
                    *f = self.copy_list(*f);
                }
            }
            NodeData::Fraction(fr) => {
                for f in [
                    &mut fr.num,
                    &mut fr.denom,
                    &mut fr.left,
                    &mut fr.right,
                    &mut fr.middle,
                    &mut fr.new_hlist,
                ] {
                    *f = self.copy_list(*f);
                }
            }
            NodeData::Fence(fe) => {
                fe.delim = self.copy_list(fe.delim);
                fe.new_hlist = self.copy_list(fe.new_hlist);
            }
            NodeData::Choice(c) => {
                for f in c.iter_mut() {
                    *f = self.copy_list(*f);
                }
            }
            NodeData::SubList { head } => *head = self.copy_list(*head),
            _ => {}
        }
        self.in_use += 1;
        if let Some(i) = self.free.pop() {
            self.nodes[i as usize] = node;
            NodeRef(i)
        } else {
            self.nodes.push(node);
            NodeRef(self.nodes.len() as u32 - 1)
        }
    }

    /// A new empty box of the given type (`new_null_box`).
    pub fn new_null_box(&mut self, hlist: bool) -> NodeRef {
        self.alloc(
            if hlist { id::HLIST } else { id::VLIST },
            0,
            NodeData::Box(Box::default()),
        )
    }

    /// A new glue node.
    pub fn new_glue(&mut self, spec: Glue, subtype: u16) -> NodeRef {
        self.alloc(
            id::GLUE,
            subtype,
            NodeData::Glue {
                spec,
                leader: NodeRef::NULL,
            },
        )
    }

    /// A new kern node.
    pub fn new_kern(&mut self, w: i32, subtype: u16) -> NodeRef {
        self.alloc(
            id::KERN,
            subtype,
            NodeData::Kern {
                kern: w,
                expansion_factor: 0,
            },
        )
    }

    /// A new penalty node.
    pub fn new_penalty(&mut self, m: i32, subtype: u16) -> NodeRef {
        self.alloc(id::PENALTY, subtype, NodeData::Penalty { penalty: m })
    }

    /// A new temporary list head.
    pub fn new_temp(&mut self) -> NodeRef {
        self.alloc(id::TEMP, 0, NodeData::Temp)
    }

    /// A new glyph node.
    pub fn new_glyph(&mut self, font: u32, chr: u32) -> NodeRef {
        self.alloc(
            id::GLYPH,
            0,
            NodeData::Glyph(GlyphData {
                chr,
                font,
                ..GlyphData::default()
            }),
        )
    }

    /// A new rule node with the given dimensions.
    pub fn new_rule(&mut self, width: i32, height: i32, depth: i32) -> NodeRef {
        self.alloc(
            id::RULE,
            0,
            NodeData::Rule {
                width,
                depth,
                height,
                dir: 0,
                index: 0,
                left: 0,
                right: 0,
            },
        )
    }

    /// A new empty discretionary node.
    pub fn new_disc(&mut self, subtype: u16, penalty: i32) -> NodeRef {
        self.alloc(
            id::DISC,
            subtype,
            NodeData::Disc {
                pre: NodeRef::NULL,
                post: NodeRef::NULL,
                replace: NodeRef::NULL,
                penalty,
            },
        )
    }

    /// A new math node.
    pub fn new_math(&mut self, surround: i32, subtype: u16) -> NodeRef {
        self.alloc(
            id::MATH,
            subtype,
            NodeData::Math {
                surround,
                glue: Glue::ZERO,
            },
        )
    }

    /// The type-specific data of `p`.
    #[inline]
    pub fn data(&self, p: NodeRef) -> &NodeData {
        &self.nodes[p.0 as usize].data
    }

    /// The type-specific data of `p`, mutably.
    #[inline]
    pub fn data_mut(&mut self, p: NodeRef) -> &mut NodeData {
        &mut self.nodes[p.0 as usize].data
    }

    /// The subtype of `p`.
    #[inline]
    pub fn subtype(&self, p: NodeRef) -> u16 {
        self.nodes[p.0 as usize].subtype
    }

    /// Sets the subtype of `p`.
    #[inline]
    pub fn set_subtype(&mut self, p: NodeRef, s: u16) {
        self.nodes[p.0 as usize].subtype = s;
    }

    /// The `prev` link of `p`.
    #[inline]
    pub fn prev(&self, p: NodeRef) -> NodeRef {
        self.nodes[p.0 as usize].prev
    }

    /// Sets only the `next` link of `p`.
    #[inline]
    pub fn set_next(&mut self, p: NodeRef, q: NodeRef) {
        self.nodes[p.0 as usize].next = q;
    }

    /// Sets only the `prev` link of `p`.
    #[inline]
    pub fn set_prev(&mut self, p: NodeRef, q: NodeRef) {
        self.nodes[p.0 as usize].prev = q;
    }

    /// Whether `p` is a glyph node.
    #[inline]
    pub fn is_glyph(&self, p: NodeRef) -> bool {
        self.nodes[p.0 as usize].id == id::GLYPH
    }

    /// The glyph data of a glyph node.
    #[inline]
    pub fn glyph(&self, p: NodeRef) -> Option<&GlyphData> {
        match &self.nodes[p.0 as usize].data {
            NodeData::Glyph(g) => Some(g),
            _ => None,
        }
    }

    /// The glyph data of a glyph node, mutably.
    #[inline]
    pub fn glyph_mut(&mut self, p: NodeRef) -> Option<&mut GlyphData> {
        match &mut self.nodes[p.0 as usize].data {
            NodeData::Glyph(g) => Some(g),
            _ => None,
        }
    }

    /// The glue specification of a glue node.
    #[inline]
    pub fn glue_spec(&self, p: NodeRef) -> Glue {
        match &self.nodes[p.0 as usize].data {
            NodeData::Glue { spec, .. } => *spec,
            NodeData::Math { glue, .. } => *glue,
            _ => Glue::ZERO,
        }
    }

    /// The width of a node that has one (boxes, rules, glue, kerns, math,
    /// margin kerns, unset nodes); zero otherwise. Glyph widths need the
    /// font and are not handled here.
    pub fn width(&self, p: NodeRef) -> i32 {
        match &self.nodes[p.0 as usize].data {
            NodeData::Box(b) => b.width,
            NodeData::Unset { b, .. } => b.width,
            NodeData::Rule { width, .. } => *width,
            NodeData::Glue { spec, .. } => spec.width,
            NodeData::Kern {
                kern,
                expansion_factor,
            } => *kern + *expansion_factor,
            NodeData::Math { surround, glue } => {
                if glue.width != 0 || glue.stretch != 0 || glue.shrink != 0 {
                    glue.width
                } else {
                    *surround
                }
            }
            NodeData::MarginKern { width, .. } => *width,
            _ => 0,
        }
    }

    /// The penalty of a penalty node (0 for other nodes).
    pub fn penalty(&self, p: NodeRef) -> i32 {
        match &self.nodes[p.0 as usize].data {
            NodeData::Penalty { penalty } => *penalty,
            NodeData::Disc { penalty, .. } => *penalty,
            _ => 0,
        }
    }

    /// The (pre, post, replace) lists of a discretionary.
    pub fn disc_lists(&self, p: NodeRef) -> (NodeRef, NodeRef, NodeRef) {
        match &self.nodes[p.0 as usize].data {
            NodeData::Disc {
                pre, post, replace, ..
            } => (*pre, *post, *replace),
            _ => (NodeRef::NULL, NodeRef::NULL, NodeRef::NULL),
        }
    }

    /// Sets the lists of a discretionary.
    pub fn set_disc_lists(&mut self, p: NodeRef, l: (NodeRef, NodeRef, NodeRef)) {
        if let NodeData::Disc {
            pre, post, replace, ..
        } = &mut self.nodes[p.0 as usize].data
        {
            *pre = l.0;
            *post = l.1;
            *replace = l.2;
        }
        for q in [l.0, l.1, l.2] {
            if !q.is_null() {
                self.nodes[q.0 as usize].prev = NodeRef::NULL;
            }
        }
    }

    /// The list of a box, unset node, insertion or adjust node.
    pub fn list_ptr(&self, p: NodeRef) -> NodeRef {
        match &self.nodes[p.0 as usize].data {
            NodeData::Box(b) => b.head,
            NodeData::Unset { b, .. } => b.head,
            NodeData::Ins { head, .. } | NodeData::Adjust { head } => *head,
            _ => NodeRef::NULL,
        }
    }

    /// Sets the list of a box, unset node, insertion or adjust node.
    pub fn set_list_ptr(&mut self, p: NodeRef, l: NodeRef) {
        match &mut self.nodes[p.0 as usize].data {
            NodeData::Box(b) => b.head = l,
            NodeData::Unset { b, .. } => b.head = l,
            NodeData::Ins { head, .. } | NodeData::Adjust { head } => *head = l,
            _ => {}
        }
    }

    /// The attribute list of `p`.
    #[inline]
    pub fn attr(&self, p: NodeRef) -> Option<&AttrList> {
        self.nodes[p.0 as usize].attr.as_ref()
    }

    /// Sets the attribute list of `p`.
    #[inline]
    pub fn set_attr(&mut self, p: NodeRef, a: Option<AttrList>) {
        self.nodes[p.0 as usize].attr = a;
    }

    /// The noad fields of a noad, radical or accent node.
    #[inline]
    pub fn noad(&self, p: NodeRef) -> Option<&NoadData> {
        match &self.nodes[p.0 as usize].data {
            NodeData::Noad(n) => Some(n),
            _ => None,
        }
    }

    /// The noad fields of a noad, radical or accent node, mutably.
    #[inline]
    pub fn noad_mut(&mut self, p: NodeRef) -> Option<&mut NoadData> {
        match &mut self.nodes[p.0 as usize].data {
            NodeData::Noad(n) => Some(n),
            _ => None,
        }
    }

    /// The list of a `sub_box` or `sub_mlist` kernel (null otherwise).
    pub fn list_ptr_kernel(&self, p: NodeRef) -> NodeRef {
        if p.is_null() {
            return NodeRef::NULL;
        }
        match &self.nodes[p.0 as usize].data {
            NodeData::SubList { head } => *head,
            _ => NodeRef::NULL,
        }
    }

    /// Sets the list of a `sub_box` or `sub_mlist` kernel.
    pub fn set_kernel_list(&mut self, p: NodeRef, l: NodeRef) {
        if p.is_null() {
            return;
        }
        if let NodeData::SubList { head } = &mut self.nodes[p.0 as usize].data {
            *head = l;
        }
    }

    /// Whether `p` is a noad that can carry scripts (`scripts_allowed`).
    pub fn scripts_allowed(&self, p: NodeRef) -> bool {
        matches!(self.nodes[p.0 as usize].data, NodeData::Noad(_))
            && matches!(self.id(p), id::NOAD | id::RADICAL | id::ACCENT)
    }

    /// The number of nodes in the list starting at `p`.
    pub fn list_len(&self, mut p: NodeRef) -> usize {
        let mut n = 0;
        while !p.is_null() {
            n += 1;
            p = self.next(p);
        }
        n
    }
}

/// The glue set ratio `num / den` as LuaTeX stores it: the quotient is
/// computed in double precision and kept as a C `float` (observed through
/// `tex.box[n].glue_set`). The rounding shows at shipout, where the ratio
/// multiplies the accumulated stretch or shrink (§625).
pub fn glue_ratio(num: i32, den: i32) -> f64 {
    f64::from((f64::from(num) / f64::from(den)) as f32)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn glue_ratio_is_single_precision() {
        // `\hbox to 1021537sp{\hskip 0pt plus 873808sp}` in LuaTeX.
        assert_eq!(glue_ratio(1021537, 873808), 1.1690634489059448);
    }

    #[test]
    fn alloc_link_copy_flush() {
        let mut n = Nodes::new();
        let b = n.new_null_box(true);
        let k = n.new_kern(5, kern_sub::USER);
        let g = n.new_glue(Glue::fixed(7), glue_sub::USER);
        n.link(k, g);
        n.box_data_mut(b).unwrap().head = k;
        assert_eq!(n.in_use, 3);
        let c = n.copy_node(b);
        assert_eq!(n.in_use, 6);
        let ch = n.box_data(c).unwrap().head;
        assert_ne!(ch, k);
        assert_eq!(n.get(n.next(ch)).data, n.get(g).data);
        n.flush_list(c);
        n.flush_list(b);
        assert_eq!(n.in_use, 0);
    }
}