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");

/// The Lua name of node type `t` (`glue`), from [`LUATEX_NODE_TYPES`].
pub fn type_name(t: u8) -> String {
    LUATEX_NODE_TYPES
        .lines()
        .filter_map(|l| l.strip_prefix("type "))
        .find_map(|l| {
            let mut it = l.split_whitespace();
            let n: u8 = it.next()?.parse().ok()?;
            (n == t).then(|| it.next().unwrap_or("").to_owned())
        })
        .unwrap_or_default()
}

/// 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;
    /// A glue specification made by Lua code (`node.new("glue_spec")`);
    /// its data is that of a glue node.
    pub const GLUE_SPEC: u8 = 39;
    pub const TEMP: u8 = 41;
    /// A freed node (in the arena's free list).
    pub const FREE: u8 = 255;
}

/// The deepest nesting of boxes that is copied and shipped out (TeX
/// builds at most 1000 levels at a time, LuaTeX ships out 20000 boxes
/// nested in each other, and Lua code can make a box contain itself).
pub const MAX_NESTING: u32 = 50_000;

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

/// Subtypes of hlist and vlist nodes that math typesetting gives the boxes
/// it builds (LuaTeX's `mathchar`, `vextensible`, `vdelimiter`).
pub mod list_sub {
    /// A box holding one math character.
    pub const MATH_CHAR: u16 = 9;
    /// A horizontal extensible delimiter.
    pub const H_EXTENSIBLE: u16 = 10;
    /// A vertical extensible delimiter.
    pub const V_EXTENSIBLE: u16 = 11;
    /// A null (empty) delimiter.
    pub const V_DELIMITER: u16 = 13;
    /// A delimiter above its nucleus (`\Uoverdelimiter`, `\Udelimiterover`).
    pub const OVER_DELIMITER: u16 = 14;
    /// A delimiter below its nucleus.
    pub const UNDER_DELIMITER: u16 = 15;
    /// The numerator of a fraction.
    pub const NUMERATOR: u16 = 16;
    /// The denominator of a fraction.
    pub const DENOMINATOR: u16 = 17;
    /// An operator with limits.
    pub const LIMITS: u16 = 18;
    /// A fraction.
    pub const FRACTION: u16 = 19;
    /// The nucleus of a noad.
    pub const NUCLEUS: u16 = 20;
    /// A superscript.
    pub const SUP: u16 = 21;
    /// A subscript.
    pub const SUB: u16 = 22;
    /// The degree of a radical.
    pub const DEGREE: u16 = 23;
    /// A superscript and a subscript.
    pub const SCRIPTS: u16 = 24;
    /// An overline.
    pub const OVER: u16 = 25;
    /// An underline.
    pub const UNDER: u16 = 26;
    /// An accented nucleus.
    pub const ACCENT: u16 = 27;
    /// A radical.
    pub const RADICAL: u16 = 28;
}

/// 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,
        /// `struct n`: a structure destination for structure element
        /// object `n`.
        structure: Option<i32>,
    },
    /// `\pdfextension refobj`.
    PdfRefobj {
        /// The object number.
        objnum: i32,
    },
    /// `\pdfextension linkstate`.
    PdfLinkState {
        /// The state (0 links on, 1 links off).
        state: i32,
    },
    /// A `user_defined` whatsit (made from Lua).
    UserDefined {
        /// `user_id`.
        user_id: i32,
        /// The value, by type.
        value: UserValue,
    },
    /// 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 string set from Lua outside IniTeX, which LuaTeX keeps as a Lua
    /// reference (observed: shown as `<lua data reference N>`).
    Lua {
        /// The string.
        data: Vec<u8>,
        /// The reference number shown.
        reference: i32,
    },
}

impl LateData {
    /// The string of a [`LateData::Bytes`] or [`LateData::Lua`] value.
    pub fn bytes(&self) -> Option<&[u8]> {
        match self {
            LateData::Bytes(b) | LateData::Lua { data: b, .. } => Some(b),
            LateData::Tokens(_) => None,
        }
    }
}

/// The value of a `user_defined` whatsit, by its type (LuaTeX manual:
/// `a`, `d`, `l`, `n`, `s`, `t`).
#[derive(Clone, Debug, PartialEq)]
pub enum UserValue {
    /// `d`: a number.
    Int(i32),
    /// `s`: a string.
    Str(Vec<u8>),
    /// `t`: a token list.
    Tokens(TokenList),
    /// `n`: a node list.
    Nodes(NodeRef),
    /// `l`: a Lua value, by its reference number.
    Lua(i32),
    /// `a`: an attribute list (not modelled).
    Attr,
}

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

impl Node {
    /// A temporary node, like the null node.
    fn temp() -> Node {
        Node {
            id: id::TEMP,
            subtype: 0,
            next: NodeRef::NULL,
            prev: NodeRef::NULL,
            attr: None,
            data: NodeData::Temp,
        }
    }
}

/// What happened to a node with a Lua property (`node.setproperty`),
/// for the Lua side to update its property table.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum PropEvent {
    /// The node was freed: its property goes.
    Flush(u32),
    /// The node (first) was copied (second).
    Copy(u32, u32),
}

/// LuaTeX's node properties as the engine tracks them: which nodes have
/// one, the mode set by `node.set_properties_mode(flush, copy)`, and the
/// frees and copies of such nodes since the Lua side last looked.
#[derive(Debug, Clone, Default)]
pub struct Properties {
    /// Nodes with a property (only tracked when `flush` or `copy` is on).
    pub nodes: std::collections::HashSet<u32>,
    /// Properties go when their node is freed.
    pub flush: bool,
    /// Copies of a node get a property that inherits from the original.
    pub copy: bool,
    /// Pending events, oldest first.
    pub events: Vec<PropEvent>,
}

/// The node arena.
#[derive(Debug, Clone)]
pub struct Nodes {
    nodes: Vec<Node>,
    /// The nesting depth of [`Nodes::copy_list`].
    copy_depth: u32,
    /// Where writes to nodes outside the arena go: Lua code can name any
    /// number as a direct node.
    sink: Node,
    free: Vec<u32>,
    /// Number of nodes in use.
    pub in_use: usize,
    /// Lua node properties.
    pub props: Properties,
    /// SyncTeX fields of the nodes, while SyncTeX is on (see
    /// [`SyncFields`]).
    pub sync: Option<Box<SyncFields>>,
    /// The first node freed twice, with its type before the first free:
    /// a fatal error in LuaTeX, reported by the engine (see
    /// `Engine::check_double_free`).
    pub double_free: Option<(u8, u32)>,
    /// The temporary head of a paragraph during its node processing
    /// callbacks: LuaTeX's is not a node that can be freed.
    pub par_temp: NodeRef,
    /// The numbers of the Lua values nodes keep by reference.
    pub lua_refs: LuaRefs,
}

/// The numbers LuaTeX gives the Lua values it keeps by reference (shown
/// as `<lua data reference N>`), modelled as observed: a new reference
/// takes the most recently released number, else the next one; freeing
/// or overwriting a node's value releases its number, copying the node
/// takes a new one. Fonts made from Lua tables and luaotfload's set-up
/// hold references too.
#[derive(Debug, Clone, Default)]
pub struct LuaRefs {
    /// The next number never used (780 at the start of a plain run).
    pub next: i32,
    /// The released numbers, the last released last.
    pub free: Vec<i32>,
    /// References made by copying nodes: (copy, original), for the Lua
    /// side to duplicate the value.
    pub copies: Vec<(i32, i32)>,
}

impl LuaRefs {
    /// A new reference number.
    pub fn take(&mut self) -> i32 {
        if let Some(r) = self.free.pop() {
            return r;
        }
        if self.next == 0 {
            self.next = 780;
        }
        let r = self.next;
        self.next += 1;
        r
    }

    /// Releases reference `r` (none if it is not positive).
    pub fn release(&mut self, r: i32) {
        if r > 0 {
            self.free.push(r);
        }
    }

    /// The references held by a font that luaotfload defines: one while
    /// it is made, released after, and one kept (observed).
    pub fn font_defined(&mut self, temporary: bool) {
        if temporary {
            let t = self.take();
            self.take();
            self.release(t);
        } else {
            self.take();
        }
    }
}

/// The reference number of the Lua value node data keeps, if any.
fn lua_ref_mut(data: &mut NodeData) -> Option<&mut i32> {
    match data {
        NodeData::Whatsit(w) => match &mut **w {
            Whatsit::LateLua {
                data: LateData::Lua { reference, .. },
                ..
            }
            | Whatsit::PdfLiteral {
                data: LateData::Lua { reference, .. },
                ..
            } => Some(reference),
            Whatsit::UserDefined {
                value: UserValue::Lua(r),
                ..
            } if *r > 0 => Some(r),
            _ => None,
        },
        _ => None,
    }
}

/// The SyncTeX fields (input tag and line) of the nodes, kept beside the
/// arena while SyncTeX is on, so that runs without it pay nothing.
///
/// As LuaTeX's `node.direct.get_synctex_fields` shows, a node gets the
/// current tag and line when it is made, except glyphs and kerns, which get
/// none; a copy keeps the fields of its original, except kerns and math
/// nodes, which get the current ones (observed).
#[derive(Debug, Clone, Default)]
pub struct SyncFields {
    /// The tag and line of the input being read.
    pub cur: (u32, i32),
    fields: Vec<(u32, i32)>,
}

impl SyncFields {
    #[inline]
    fn set(&mut self, i: u32, f: (u32, i32)) {
        let i = i as usize;
        if i >= self.fields.len() {
            self.fields.resize(i + 1, (0, 0));
        }
        self.fields[i] = f;
    }
}

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::temp()],
            copy_depth: 0,
            sink: Node::temp(),
            free: Vec::new(),
            in_use: 0,
            props: Properties::default(),
            sync: None,
            lua_refs: LuaRefs::default(),
            double_free: None,
            par_temp: NodeRef::NULL,
        }
    }

    /// Starts keeping SyncTeX fields (for nodes made from now on).
    pub fn enable_sync(&mut self) {
        if self.sync.is_none() {
            self.sync = Some(Box::default());
        }
    }

    /// The SyncTeX tag and line of `p`, (0, 0) if it has none.
    #[inline]
    pub fn sync_fields(&self, p: NodeRef) -> (u32, i32) {
        self.sync
            .as_ref()
            .and_then(|s| s.fields.get(p.0 as usize).copied())
            .unwrap_or((0, 0))
    }

    /// Sets the SyncTeX tag and line of `p` (when SyncTeX is on).
    pub fn set_sync_fields(&mut self, p: NodeRef, f: (u32, i32)) {
        if p.0 as usize >= self.nodes.len() {
            return;
        }
        if let Some(s) = self.sync.as_deref_mut() {
            s.set(p.0, f);
        }
    }

    /// Sets the SyncTeX fields of `p`, a node just made by font
    /// processing that LuaTeX's Lua code makes by copying (kerns from
    /// OpenType positioning): the current tag and line.
    pub fn sync_as_copied(&mut self, p: NodeRef) {
        if let Some(s) = self.sync.as_deref_mut() {
            let cur = s.cur;
            s.set(p.0, cur);
        }
    }

    /// The node at `p`; the null node if `p` is outside the arena.
    #[inline]
    fn at(&self, p: NodeRef) -> &Node {
        self.nodes.get(p.0 as usize).unwrap_or(&self.nodes[0])
    }

    /// The node at `p`, mutably; a scratch node if `p` is outside the
    /// arena.
    #[inline]
    fn at_mut(&mut self, p: NodeRef) -> &mut Node {
        match self.nodes.get_mut(p.0 as usize) {
            Some(n) => n,
            None => {
                self.sink = Node::temp();
                &mut self.sink
            }
        }
    }

    /// 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;
        let p = 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)
        };
        if let Some(s) = self.sync.as_deref_mut() {
            let f = if id == id::KERN || id == id::GLYPH {
                (0, 0)
            } else {
                s.cur
            };
            s.set(p.0, f);
        }
        p
    }

    /// Frees a single node (not its sublists).
    pub fn free(&mut self, p: NodeRef) {
        // Lua code can free a node twice (LuaTeX corrupts its memory);
        // a node in the free list twice would be allocated twice.
        if p.is_null() || p.0 as usize >= self.nodes.len() {
            return;
        }
        if self.is_free(p) {
            if self.double_free.is_none() {
                self.double_free = Some((self.at(p).subtype as u8, p.0));
            }
            return;
        }
        // The subtype of a free node keeps its type, for the message.
        let t = self.at(p).id;
        self.at_mut(p).subtype = u16::from(t);
        if let Some(r) = lua_ref_mut(&mut self.at_mut(p).data) {
            let r = *r;
            self.lua_refs.release(r);
        }
        self.at_mut(p).id = id::FREE;
        self.at_mut(p).data = NodeData::Temp;
        self.at_mut(p).attr = None;
        self.free.push(p.0);
        self.in_use -= 1;
        if !self.props.nodes.is_empty() && self.props.nodes.remove(&p.0) && self.props.flush {
            self.props.events.push(PropEvent::Flush(p.0));
        }
    }

    /// The reference number of the Lua value node `p` keeps, if any.
    pub fn lua_ref_of(&mut self, p: NodeRef) -> Option<i32> {
        lua_ref_mut(&mut self.at_mut(p).data).map(|r| *r)
    }

    /// Whether `p` was freed (and not allocated again).
    #[inline]
    pub fn is_free(&self, p: NodeRef) -> bool {
        self.at(p).id == id::FREE
    }

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

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

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

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

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

    /// The box data of an hlist/vlist node.
    pub fn box_data(&self, p: NodeRef) -> Option<&BoxData> {
        match &self.at(p).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.at_mut(p).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;
        }
    }

    /// The last node of the list starting at `p`, or `None` if the list
    /// is circular (Lua code can link nodes into a loop).
    pub fn bounded_tail(&self, mut p: NodeRef) -> Option<NodeRef> {
        if p.is_null() {
            return Some(p);
        }
        for _ in 0..self.nodes.len() {
            let n = self.next(p);
            if n.is_null() {
                return Some(p);
            }
            p = n;
        }
        None
    }

    /// 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() {
                if self.is_free(p) {
                    // Freed already: a list that Lua code made circular,
                    // or a node in two lists.
                    self.free(p);
                    break;
                }
                let next = self.next(p);
                match &self.at(p).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;
        // Lists nested deeper than this are cut off: only Lua code makes
        // them, with a box that contains itself (LuaTeX crashes).
        if self.copy_depth >= MAX_NESTING {
            return head;
        }
        self.copy_depth += 1;
        // A list longer than the arena is circular (made by Lua code;
        // LuaTeX copies until memory runs out): the copy stops.
        let mut left = self.nodes.len();
        while !p.is_null() && left > 0 {
            left -= 1;
            let q = self.copy_node(p);
            if head.is_null() {
                head = q;
            } else {
                self.link(tail, q);
            }
            tail = q;
            p = self.next(p);
        }
        self.copy_depth -= 1;
        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.at(p).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),
            _ => {}
        }
        if let Some(r) = lua_ref_mut(&mut node.data) {
            let old = *r;
            let new = self.lua_refs.take();
            *r = new;
            self.lua_refs.copies.push((new, old));
        }
        self.in_use += 1;
        let q = 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)
        };
        if self.props.copy && self.props.nodes.contains(&p.0) {
            self.props.nodes.insert(q.0);
            self.props.events.push(PropEvent::Copy(p.0, q.0));
        }
        if self.sync.is_some() {
            let id = self.at(q).id;
            let f = if id == id::KERN || id == id::MATH {
                self.sync.as_ref().map_or((0, 0), |s| s.cur)
            } else {
                self.sync_fields(p)
            };
            self.set_sync_fields(q, f);
        }
        q
    }

    /// 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.at(p).data
    }

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

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

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

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

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

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

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

    /// The glyph data of a glyph node.
    #[inline]
    pub fn glyph(&self, p: NodeRef) -> Option<&GlyphData> {
        match &self.at(p).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.at_mut(p).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.at(p).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.at(p).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.at(p).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.at(p).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.at_mut(p).data
        {
            *pre = l.0;
            *post = l.1;
            *replace = l.2;
        }
        for q in [l.0, l.1, l.2] {
            if !q.is_null() {
                self.at_mut(q).prev = NodeRef::NULL;
            }
        }
    }

    /// The list of a box, unset node, insertion or adjust node.
    pub fn list_ptr(&self, p: NodeRef) -> NodeRef {
        match &self.at(p).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.at_mut(p).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.at(p).attr.as_ref()
    }

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

    /// The noad fields of a noad, radical or accent node.
    #[inline]
    pub fn noad(&self, p: NodeRef) -> Option<&NoadData> {
        match &self.at(p).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.at_mut(p).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.at(p).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.at_mut(p).data {
            *head = l;
        }
    }

    /// Whether `p` is a noad that can carry scripts (`scripts_allowed`).
    pub fn scripts_allowed(&self, p: NodeRef) -> bool {
        matches!(self.at(p).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);
    }

    /// A list that Lua code linked into a loop: walks that are bounded
    /// anyway end, and flushing it reports the node freed twice.
    #[test]
    fn circular_list() {
        let mut n = Nodes::new();
        let a = n.new_kern(1, kern_sub::USER);
        let b = n.new_glue(Glue::fixed(2), glue_sub::USER);
        n.link(a, b);
        n.link(b, a);
        assert_eq!(n.bounded_tail(a), None);
        let c = n.copy_list(a);
        assert!(!c.is_null());
        assert_eq!(n.double_free, None);
        n.flush_list(a);
        assert_eq!(n.double_free, Some((id::KERN, a.0)));
        assert_eq!(type_name(id::KERN), "kern");
    }
}