retex_engine/

fingerprint.rs

//! Fingerprints of the engine state, for `--watch` (see
//! `docs/design/incremental-rebuilds.md`): after an edit, the rebuild
//! compares its state at a page with the previous build's at the same
//! page; when they agree, the rest of the previous build's output is what
//! the rebuild would produce.
//!
//! The fingerprint covers what decides the rest of the run: the input
//! still to be read (not the line numbers, which an edit shifts), the
//! table of equivalents and the meanings, the save stack, the semantic
//! nest, the page builder, marks, conditionals, the PDF state and the
//! backend's. Node lists are hashed by structure (their nodes are
//! numbered by allocation, which differs between the builds), hash maps in
//! key order. Not covered: the Lua state, and what was already written
//! out (it differs before the edit by construction). A fingerprint can so
//! agree when the runs would not: the rebuild goes on to the end and
//! checks.

use std::collections::HashMap;
use std::fmt::Write as _;
use std::rc::Rc;

use crate::Engine;
use crate::eqtb::{CodeTable, Meaning, Page, Val};
use crate::input::{Level, LineSource};
use crate::nodes::{NodeData, NodeRef};
use crate::save::SaveEntry;
use crate::token::Macro;

/// A 64-bit FNV-1a hash, fed bytes, integers and `Debug` output.
pub struct Fp(u64);

impl Default for Fp {
    fn default() -> Self {
        Fp(0xcbf2_9ce4_8422_2325)
    }
}

impl std::fmt::Write for Fp {
    fn write_str(&mut self, s: &str) -> std::fmt::Result {
        self.bytes(s.as_bytes());
        Ok(())
    }
}

impl Fp {
    /// The hash so far.
    pub fn get(&self) -> u64 {
        self.0
    }

    /// Adds bytes.
    pub fn bytes(&mut self, b: &[u8]) {
        for &x in b {
            self.0 ^= u64::from(x);
            self.0 = self.0.wrapping_mul(0x0100_0000_01b3);
        }
    }

    /// Adds an integer.
    pub fn u(&mut self, v: u64) {
        self.0 ^= v;
        self.0 = self.0.wrapping_mul(0x0100_0000_01b3).rotate_left(29);
    }

    /// Adds a signed integer.
    pub fn i(&mut self, v: i64) {
        self.u(v as u64);
    }

    /// Adds the `Debug` form of `v`.
    pub fn debug(&mut self, v: &impl std::fmt::Debug) {
        let _ = write!(self, "{v:?}");
    }

    /// Adds glue.
    pub fn glue(&mut self, g: &crate::glue::Glue) {
        self.i(g.width.into());
        self.i(g.stretch.into());
        self.i(g.shrink.into());
        self.u(u64::from(g.stretch_order) << 8 | u64::from(g.shrink_order));
    }

    /// Adds a token list.
    pub fn tokens(&mut self, t: &[crate::token::Token]) {
        self.u(t.len() as u64);
        for x in t {
            self.u(x.0.into());
        }
    }

    /// Adds the entries of a map, in the order of their `Debug` forms
    /// (iteration order depends on the map's history).
    pub fn map<K: std::fmt::Debug, V: std::fmt::Debug>(&mut self, m: impl Iterator<Item = (K, V)>) {
        let mut v: Vec<String> = m.map(|(k, x)| format!("{k:?}\u{0}{x:?}")).collect();
        v.sort();
        self.u(v.len() as u64);
        for e in v {
            self.bytes(e.as_bytes());
            self.u(0);
        }
    }
}

/// Hashes of code-table pages and macros, by address. Each entry holds a
/// reference, so that the object is neither freed (its address reused)
/// nor changed in place: a code table copies a shared page before
/// changing it.
#[derive(Default)]
pub struct FpCache {
    pages: HashMap<usize, (Rc<Page>, u64)>,
    macros: HashMap<usize, (Rc<Macro>, u64)>,
}

fn page_hash(p: &Page) -> u64 {
    let mut h = Fp::default();
    for s in p.iter() {
        h.i(s.val);
        h.u(s.level.into());
    }
    h.get()
}

fn macro_hash(m: &Macro) -> u64 {
    let mut h = Fp::default();
    h.u(m.protected.into());
    h.tokens(&m.tokens);
    h.get()
}

impl Engine {
    /// Hashes the code-table pages and macros that exist now, so that
    /// fingerprints taken later (in this process and the processes it
    /// forks) need not hash them again: most are the preamble's and never
    /// change.
    pub fn prepare_fingerprints(&mut self) {
        let mut c = FpCache::default();
        let e = &self.eqtb;
        let tables = e
            .catcode_tables
            .values()
            .chain([&e.lc, &e.uc, &e.sf, &e.math, &e.del]);
        for t in tables {
            for p in t.pages().iter().flatten() {
                c.pages
                    .entry(Rc::as_ptr(p) as usize)
                    .or_insert_with(|| (p.clone(), page_hash(p)));
            }
        }
        for s in &e.cs {
            if let Some(m) = &s.val.mac {
                c.macros
                    .entry(Rc::as_ptr(m) as usize)
                    .or_insert_with(|| (m.clone(), macro_hash(m)));
            }
        }
        self.fp_cache = Some(Box::new(c));
    }

    /// Adds a code table.
    fn fp_code_table(&self, h: &mut Fp, t: &CodeTable) {
        for (k, p) in t.pages().iter().enumerate() {
            if let Some(p) = p {
                h.u(k as u64);
                let cached = self
                    .fp_cache
                    .as_ref()
                    .and_then(|c| c.pages.get(&(Rc::as_ptr(p) as usize)));
                h.u(cached.map_or_else(|| page_hash(p), |c| c.1));
            }
        }
        h.u(u64::MAX);
    }

    /// Adds a meaning.
    fn fp_meaning(&self, h: &mut Fp, m: &Meaning) {
        h.u(m.cmd as u64);
        h.u(m.chr.into());
        match &m.mac {
            Some(mac) => {
                let cached = self
                    .fp_cache
                    .as_ref()
                    .and_then(|c| c.macros.get(&(Rc::as_ptr(mac) as usize)));
                h.u(cached.map_or_else(|| macro_hash(mac), |c| c.1));
            }
            None => h.u(0),
        }
    }

    /// The fingerprint of the state, by part (for debugging), and in all.
    pub fn fingerprint(&mut self) -> (Vec<(&'static str, u64)>, u64) {
        let backend = self.backend.as_mut().map_or(0, |b| b.fingerprint());
        let parts: Vec<(&'static str, u64)> = vec![
            ("input", self.fp_input()),
            ("meanings", self.fp_meanings()),
            ("registers", self.fp_registers()),
            ("save stack", self.fp_save()),
            ("nest", self.fp_nest()),
            ("page builder", self.fp_page()),
            ("conditionals", self.fp_cond()),
            ("pdf", self.fp_pdf()),
            ("backend", backend),
            ("misc", self.fp_misc()),
        ];
        let mut all = Fp::default();
        for (_, h) in &parts {
            all.u(*h);
        }
        (parts, all.get())
    }

    /// The registers, one per line, and the names of the control sequences
    /// defined as `\count` and `\dimen` registers: for finding why the
    /// register part of two fingerprints differs (`RETEX_DEBUG_FINGERPRINT`).
    pub fn fingerprint_dump(&self) -> String {
        let mut out = String::new();
        let e = &self.eqtb;
        let names = ["int_par", "count", "attr", "dimen_par", "dimen"];
        for (n, v) in names
            .iter()
            .zip([&e.int_par, &e.count, &e.attr, &e.dimen_par, &e.dimen])
        {
            for (i, s) in v.iter().enumerate() {
                let _ = writeln!(out, "{n} {i} {} {}", s.val, s.level);
            }
        }
        for (n, v) in ["glue_par", "skip", "muskip"]
            .iter()
            .zip([&e.glue_par, &e.skip, &e.muskip])
        {
            for (i, s) in v.iter().enumerate() {
                let _ = writeln!(out, "{n} {i} {:?} {}", s.val, s.level);
            }
        }
        for (n, v) in ["toks_par", "toks"].iter().zip([&e.toks_par, &e.toks]) {
            for (i, s) in v.iter().enumerate() {
                let mut h = Fp::default();
                h.tokens(&s.val);
                let _ = writeln!(out, "{n} {i} {:x} {}", h.get(), s.level);
            }
        }
        for (i, s) in e.boxes.iter().enumerate() {
            let mut h = Fp::default();
            self.fp_list(&mut h, s.val);
            let _ = writeln!(out, "box {i} {:x} {}", h.get(), s.level);
        }
        let _ = writeln!(
            out,
            "misc {:?}",
            (&e.cur_font, &e.math_font, &e.par_shape, &e.etex_shape)
        );
        let _ = writeln!(
            out,
            "misc2 {:?}",
            (&e.dir_par, &e.local_count, e.attrs_in_use)
        );
        for ((name, _), slot) in self.hash.entries().zip(&e.cs) {
            let m = &slot.val;
            if matches!(
                m.cmd,
                crate::cmd::Cmd::AssignInt | crate::cmd::Cmd::AssignDimen
            ) && m.chr >= crate::scan::REG_OFFSET
            {
                let _ = writeln!(
                    out,
                    "name {:?} {} = {}",
                    m.cmd,
                    m.chr - crate::scan::REG_OFFSET,
                    String::from_utf8_lossy(name)
                );
            }
        }
        let mut tables: Vec<(&u32, &crate::eqtb::CodeTable)> = e.catcode_tables.iter().collect();
        tables.sort_by_key(|(k, _)| **k);
        for (k, t) in tables {
            let mut h = Fp::default();
            for (k, page) in t.dump_pages() {
                h.u(k as u64);
                for v in page {
                    h.i(v);
                }
            }
            let _ = writeln!(out, "catcodes {k} {:x}", h.get());
        }
        out
    }

    /// Adds the node list starting at `p` (null for none).
    fn fp_list(&self, h: &mut Fp, mut p: NodeRef) {
        while !p.is_null() {
            self.fp_node(h, p);
            p = self.nodes.next(p);
        }
        h.u(u64::MAX);
    }

    /// Adds one node, with the lists it holds.
    fn fp_node(&self, h: &mut Fp, p: NodeRef) {
        let n = self.nodes.get(p);
        h.u(n.id.into());
        h.u(n.subtype.into());
        match &n.attr {
            Some(a) => h.debug(&&a[..]),
            None => h.u(0),
        }
        match &n.data {
            NodeData::Box(b) => {
                h.debug(&(b.width, b.depth, b.height, b.dir, b.shift));
                h.debug(&(b.glue_order, b.glue_sign, b.glue_set.to_bits()));
                self.fp_list(h, b.head);
            }
            NodeData::Unset {
                b,
                span_count,
                stretch,
                shrink,
                stretch_order,
                shrink_order,
            } => {
                h.debug(&(b.width, b.depth, b.height, b.dir, b.shift));
                h.debug(&(span_count, stretch, shrink, stretch_order, shrink_order));
                self.fp_list(h, b.head);
            }
            NodeData::Ins {
                cost,
                depth,
                height,
                spec,
                head,
            } => {
                h.debug(&(cost, depth, height, spec));
                self.fp_list(h, *head);
            }
            NodeData::Adjust { head } | NodeData::SubList { head } => self.fp_list(h, *head),
            NodeData::Disc {
                pre,
                post,
                replace,
                penalty,
            } => {
                h.i((*penalty).into());
                self.fp_list(h, *pre);
                self.fp_list(h, *post);
                self.fp_list(h, *replace);
            }
            NodeData::LocalPar {
                pen_inter,
                pen_broken,
                dir,
                box_left,
                box_left_width,
                box_right,
                box_right_width,
            } => {
                h.debug(&(pen_inter, pen_broken, dir, box_left_width, box_right_width));
                self.fp_list(h, *box_left);
                self.fp_list(h, *box_right);
            }
            NodeData::Glue { spec, leader } => {
                h.debug(spec);
                self.fp_list(h, *leader);
            }
            NodeData::Glyph(g) => {
                h.debug(&(g.chr, g.font, g.lang, g.left, g.right, g.uchyph));
                h.debug(&(g.xoffset, g.yoffset, g.expansion_factor, g.data));
                self.fp_list(h, g.components);
            }
            NodeData::MarginKern { width, glyph } => {
                h.i((*width).into());
                if !glyph.is_null() {
                    self.fp_node(h, *glyph);
                }
            }
            NodeData::Noad(d) => {
                h.debug(&(d.options, d.width, d.fraction));
                for l in [
                    d.nucleus,
                    d.sub,
                    d.sup,
                    d.left,
                    d.degree,
                    d.accent,
                    d.bot_accent,
                    d.new_hlist,
                ] {
                    self.fp_list(h, l);
                }
            }
            NodeData::Fraction(d) => {
                h.debug(&(d.thickness, d.options));
                for l in [d.num, d.denom, d.left, d.right, d.middle, d.new_hlist] {
                    self.fp_list(h, l);
                }
            }
            NodeData::Fence(d) => {
                h.debug(&(d.italic, d.height, d.depth, d.options, d.class));
                self.fp_list(h, d.delim);
                self.fp_list(h, d.new_hlist);
            }
            NodeData::Choice(c) => {
                for l in c.iter() {
                    self.fp_list(h, *l);
                }
            }
            // No node references in the others.
            other => h.debug(other),
        }
    }

    /// Adds a saved or current value.
    fn fp_val(&self, h: &mut Fp, v: &Val) {
        match v {
            Val::Meaning(m) => self.fp_meaning(h, m),
            Val::Node(p) => self.fp_list(h, *p),
            Val::Toks(t) => h.tokens(t),
            other => h.debug(other),
        }
    }

    /// The input still to be read. Of a file, what follows the point
    /// read and the number of lines it has: not the line number, which
    /// an edit before shifts.
    fn fp_input(&self) -> u64 {
        let mut h = Fp::default();
        let inp = &self.input;
        h.u(inp.stack.len() as u64);
        for l in &inp.stack {
            match l {
                Level::Text(t) => {
                    h.u(1);
                    h.debug(&(t.state, t.loc, t.is_input_file, t.eof_seen));
                    h.debug(&(t.grp_boundary, t.if_depth, t.catmode));
                    h.debug(&&t.buf[..]);
                    h.bytes(&t.name);
                    match &t.source {
                        LineSource::File { data, pos } => {
                            let rest = data.get(*pos..).unwrap_or_default();
                            h.u(2);
                            h.bytes(rest);
                        }
                        other => h.debug(other),
                    }
                }
                Level::Tokens(t) => {
                    h.u(3);
                    h.tokens(&t.list);
                    h.debug(&(t.loc, t.kind, t.param_start, t.name));
                }
            }
        }
        for p in &inp.param_stack {
            h.tokens(p);
        }
        h.debug(&(inp.align_state, inp.scanner_status, inp.warning_index));
        h.debug(&(inp.force_eof, inp.in_open));
        h.get()
    }

    /// The control sequences and their meanings.
    fn fp_meanings(&self) -> u64 {
        let mut h = Fp::default();
        h.u(self.hash.len() as u64);
        for (name, kind) in self.hash.entries() {
            h.bytes(name);
            h.debug(kind);
        }
        for s in &self.eqtb.cs {
            h.u(s.level.into());
            self.fp_meaning(&mut h, &s.val);
        }
        h.get()
    }

    /// Parameters, registers and code tables.
    fn fp_registers(&self) -> u64 {
        let mut h = Fp::default();
        let e = &self.eqtb;
        let ints = |h: &mut Fp, v: &[crate::eqtb::Slot<i32>]| {
            h.u(v.len() as u64);
            for s in v {
                h.i(s.val.into());
                h.u(s.level.into());
            }
        };
        for v in [&e.int_par, &e.count, &e.attr, &e.dimen_par, &e.dimen] {
            ints(&mut h, v);
        }
        for v in [&e.glue_par, &e.skip, &e.muskip] {
            h.u(v.len() as u64);
            for s in v {
                h.glue(&s.val);
                h.u(s.level.into());
            }
        }
        for v in [&e.toks_par, &e.toks] {
            h.u(v.len() as u64);
            for s in v {
                h.tokens(&s.val);
                h.u(s.level.into());
            }
        }
        h.u(e.boxes.len() as u64);
        for s in &e.boxes {
            self.fp_list(&mut h, s.val);
            h.u(s.level.into());
        }
        for s in &e.local_box {
            self.fp_list(&mut h, s.val);
            h.u(s.level.into());
        }
        h.debug(&(&e.cur_font, &e.math_font, &e.par_shape, &e.etex_shape));
        h.debug(&(&e.dir_par, &e.local_count, e.attrs_in_use));
        h.map(e.math_param.iter());
        let mut tables: Vec<(&u32, &crate::eqtb::CodeTable)> = e.catcode_tables.iter().collect();
        tables.sort_by_key(|(k, _)| **k);
        let all = tables
            .iter()
            .map(|(_, t)| *t)
            .chain([&e.lc, &e.uc, &e.sf, &e.math, &e.del]);
        for (k, _) in &tables {
            h.u((**k).into());
        }
        for t in all {
            self.fp_code_table(&mut h, t);
        }
        h.get()
    }

    /// The save stack (not the lines where groups began).
    fn fp_save(&self) -> u64 {
        let mut h = Fp::default();
        let s = &self.save;
        h.debug(&(s.cur_level, s.cur_group, s.cur_boundary));
        for e in &s.stack {
            match e {
                SaveEntry::Restore { loc, old, level } => {
                    h.u(1);
                    h.debug(&(loc, level));
                    self.fp_val(&mut h, old);
                }
                SaveEntry::InsertToken(t) => {
                    h.u(2);
                    h.u(t.0.into());
                }
                SaveEntry::Boundary {
                    group, boundary, ..
                } => {
                    h.u(3);
                    h.debug(&(group, boundary));
                }
                SaveEntry::Value(v) => {
                    h.u(4);
                    h.i(*v);
                }
                SaveEntry::RestoreCodes { kind, old, upto } => {
                    h.u(5);
                    h.debug(&(kind, upto));
                    self.fp_code_table(&mut h, old);
                }
            }
        }
        h.get()
    }

    /// The semantic nest (not the lines where modes began).
    fn fp_nest(&self) -> u64 {
        let mut h = Fp::default();
        for l in &self.nest {
            h.debug(&(l.mode, l.prev_graf, l.prev_depth, l.space_factor));
            h.debug(&(l.clang, l.math_style));
            self.fp_list(&mut h, self.nodes.next(l.head));
            self.fp_list(&mut h, l.incompleat_noad);
            self.fp_list(&mut h, l.delim_ptr);
        }
        h.debug(&(self.mode, self.local_level));
        h.get()
    }

    /// The page builder, marks and the typesetting state.
    fn fp_page(&self) -> u64 {
        let mut h = Fp::default();
        let p = &self.page;
        self.fp_list(&mut h, self.nodes.next(p.contrib_head));
        self.fp_list(&mut h, self.nodes.next(p.page_head));
        h.debug(&(p.so_far, p.fi_stretch, p.max_depth, p.contents));
        h.debug(&(p.least_cost, p.best_size, p.best_so_far, p.best_infinite));
        // The best break by its place in the page.
        let mut q = p.page_head;
        let mut k = 0u64;
        while !q.is_null() && q != p.best_break {
            q = self.nodes.next(q);
            k += 1;
        }
        h.u(if q.is_null() { u64::MAX } else { k });
        h.u(p.ins.len() as u64);
        h.debug(&(&p.last_glue, p.last_penalty, p.last_kern, p.last_node_type));
        h.map(self.marks.classes.iter());
        let ts = &self.ts;
        h.debug(&(ts.output_active, ts.last_totals, &ts.box_attrs));
        for l in ts.disc_ptr {
            self.fp_list(&mut h, l);
        }
        for l in [ts.adjust_head, ts.pre_adjust_head] {
            if !l.is_null() {
                self.fp_list(&mut h, self.nodes.next(l));
            }
        }
        h.get()
    }

    /// Conditionals (not the lines where they began).
    fn fp_cond(&self) -> u64 {
        let mut h = Fp::default();
        let c = &self.cond;
        h.u(c.stack.len() as u64);
        h.debug(&(c.if_limit, c.cur_if, c.is_in_csname));
        h.get()
    }

    /// The engine's PDF state.
    fn fp_pdf(&self) -> u64 {
        let mut h = Fp::default();
        let p = &self.pdf;
        h.debug(&(&p.page_images, &p.objects, &p.catalog, &p.open_action));
        h.debug(&(&p.info, &p.names, &p.trailer, &p.outlines));
        h.debug(&(
            &p.glyph_to_unicode,
            &p.colorstacks,
            p.last_obj,
            p.last_annot,
        ));
        h.debug(&(p.last_link, p.counter.get(), &p.map_entries, &p.lua));
        h.debug(&(p.retval, p.pos, &p.page_annots, p.output_opened));
        h.debug(&(&p.dest_order, &p.threads, &p.pending, p.fatal));
        h.debug(&(&p.active_links, p.stream_written));
        h.map(p.kinds.iter());
        h.map(p.page_refs.iter());
        h.map(p.fonts.iter());
        h.map(p.font_attrs.iter());
        h.map(p.dests.iter());
        h.map(p.struct_dests.iter());
        h.debug(&(&self.pending_forms, &self.form_objects));
        h.debug(&(
            self.images.len(),
            self.last_image_index,
            self.last_image_pages,
        ));
        h.debug(&(self.box_resources.len(), self.last_box_index));
        h.map(self.colorstack_values.iter());
        h.get()
    }

    /// Fonts, files and counters.
    fn fp_misc(&self) -> u64 {
        let mut h = Fp::default();
        h.u(self.fonts.fonts.len() as u64);
        for f in &self.fonts.fonts {
            h.bytes(&f.name);
            h.i(f.size.into());
        }
        h.debug(&(self.dead_cycles, self.insert_penalties, self.last_badness));
        h.debug(&(
            self.random_seed,
            &self.randoms,
            self.last_x_pos,
            self.last_y_pos,
        ));
        h.debug(&(self.mag_set, self.total_pages, self.err.interaction));
        h.debug(&(self.err.history, self.long_state, self.pack_dir));
        h.debug(&(self.cur_cmd, self.cur_chr, self.cur_cs, self.cur_tok));
        h.debug(&(&self.deferred_writes, &self.text_dirs, &self.math_glues));
        h.map(self.lua_functions.iter());
        h.u(self.languages.len() as u64);
        h.debug(&self.printer.open_write_streams());
        h.debug(&self.write_paths);
        for r in &self.files.read_files {
            h.debug(r);
        }
        h.get()
    }
}