tsv_html 0.8.0

//! The generator and freshness gate for `src/entities_table.rs`, the committed perfect hash
//! table of named character references.
//!
//! The table is generated from `src/entities.json` (the WHATWG list; the crate's `NOTICE`
//! attributes it) and committed, so building the crate runs no build script and pulls no
//! code generator or JSON parser into a consumer's build. `entities_table_is_fresh` renders
//! the table and fails when the committed file differs; `deno task entities:update` (the
//! same test with `TSV_ENTITIES_UPDATE=1`) writes it instead. A unit test rather than an
//! integration test because it builds the table with the lookup's own private hash. So a
//! table too broken to compile (deleted, or a merge conflict in it) is restored from git
//! first; the generator reads none of it. The JSON stays in the repository (the published
//! crate excludes it), so the test skips when it is absent rather than failing a test run
//! from the crate's tarball.
//!
//! The construction is CHD (hash, displace and compress), the algorithm `phf_generator`
//! runs: names are grouped into buckets by hash, and the buckets, largest first, each search
//! for a displacement pair that sends every one of their names to a free slot. Both searches
//! are deterministic — seeds count up from zero, pairs in order — so a regeneration from the
//! same JSON writes the same bytes.

use std::collections::BTreeMap;
use std::fmt::Write as _;
use std::fs;
use std::path::Path;

use crate::entities::{entity_hash_parts, entity_hash_seeded};

/// Names per bucket on average — `phf_generator`'s default load. A higher load means fewer
/// displacement pairs to store and longer searches to place them.
const LAMBDA: usize = 5;

/// The built table: the seed, a displacement pair per bucket, and each slot's entry.
struct Table<'a> {
    seed: u64,
    displacements: Vec<(u32, u32)>,
    slots: Vec<(&'a str, &'a str)>,
}

/// The table for `entities` from the first seed every bucket can be placed under.
fn build(entities: &BTreeMap<String, String>) -> Table<'_> {
    (0..1000)
        .find_map(|seed| try_build(entities, seed))
        .expect("no seed under 1000 places every bucket")
}

/// The table under `seed`, or `None` when some bucket finds no displacement pair.
fn try_build(entities: &BTreeMap<String, String>, seed: u64) -> Option<Table<'_>> {
    let len = entities.len();
    let bucket_count = len.div_ceil(LAMBDA);
    let hashes: Vec<(u32, u32, u32)> = entities
        .keys()
        .map(|name| entity_hash_parts(entity_hash_seeded(name.as_bytes(), seed)))
        .collect();

    let mut buckets: Vec<Vec<usize>> = vec![Vec::new(); bucket_count];
    for (key, &(bucket, _, _)) in hashes.iter().enumerate() {
        buckets[bucket as usize % bucket_count].push(key);
    }
    // Largest first, ties by bucket index, so the order is fixed.
    let mut order: Vec<usize> = (0..bucket_count).collect();
    order.sort_by_key(|&bucket| std::cmp::Reverse(buckets[bucket].len()));

    let mut slot_key: Vec<Option<usize>> = vec![None; len];
    let mut displacements = vec![(0u32, 0u32); bucket_count];
    // The slots the current trial claims, generation-stamped so a failed trial needs no reset.
    let mut trial = vec![0u64; len];
    let mut generation = 0u64;
    let mut placed = Vec::new();
    for bucket in order {
        let keys = &buckets[bucket];
        if keys.is_empty() {
            continue;
        }
        let mut found = false;
        'pairs: for d1 in 0..len as u32 {
            'd2: for d2 in 0..len as u32 {
                generation += 1;
                placed.clear();
                for &key in keys {
                    let (_, f1, f2) = hashes[key];
                    let slot = d2.wrapping_add(f1.wrapping_mul(d1)).wrapping_add(f2) as usize % len;
                    if slot_key[slot].is_some() || trial[slot] == generation {
                        continue 'd2;
                    }
                    trial[slot] = generation;
                    placed.push((slot, key));
                }
                for &(slot, key) in &placed {
                    slot_key[slot] = Some(key);
                }
                displacements[bucket] = (d1, d2);
                found = true;
                break 'pairs;
            }
        }
        if !found {
            return None;
        }
    }

    let entries: Vec<(&str, &str)> = entities
        .iter()
        .map(|(name, characters)| (name.as_str(), characters.as_str()))
        .collect();
    let slots = slot_key
        .into_iter()
        .map(|key| entries[key.expect("every slot is filled: one name per slot")])
        .collect();
    Some(Table {
        seed,
        displacements,
        slots,
    })
}

/// The committed file's text for `table`.
fn render(table: &Table<'_>) -> String {
    let mut out = String::new();
    out.push_str(
        "// @generated by `deno task entities:update` (`src/entities_gen.rs`) from\n\
         // `src/entities.json`, the WHATWG named character references, which the crate's NOTICE\n\
         // file attributes. Do not edit by hand.\n\n",
    );
    out.push_str(
        "/// The seed of `entity_hash`, the first under which every bucket found a displacement\n\
         /// pair.\n",
    );
    writeln!(out, "pub(crate) const ENTITY_SEED: u64 = {};\n", table.seed).unwrap();
    out.push_str("/// Each bucket's displacement pair, applied by `entity_slot`.\n");
    writeln!(
        out,
        "pub(crate) static ENTITY_DISPLACEMENTS: [(u32, u32); {}] = [",
        table.displacements.len()
    )
    .unwrap();
    for (d1, d2) in &table.displacements {
        writeln!(out, "    ({d1}, {d2}),").unwrap();
    }
    out.push_str("];\n\n");
    out.push_str(
        "/// Every named character reference, name (without its `&`) to the characters it stands\n\
         /// for, each in the one slot `entity_slot` computes for its name.\n",
    );
    writeln!(
        out,
        "pub(crate) static ENTITIES: [(&str, &str); {}] = [",
        table.slots.len()
    )
    .unwrap();
    for (name, characters) in &table.slots {
        // Names are ASCII. The characters are escaped: one can be a combining mark or a
        // variation selector, which would be invisible in the source.
        let mut escaped = String::new();
        for c in characters.chars() {
            if c.is_ascii_graphic() && c != '"' && c != '\\' {
                escaped.push(c);
            } else {
                write!(escaped, "\\u{{{:x}}}", c as u32).unwrap();
            }
        }
        writeln!(out, "    (\"{name}\", \"{escaped}\"),").unwrap();
    }
    out.push_str("];\n\n");
    let longest = table
        .slots
        .iter()
        .map(|(name, _)| name.len())
        .max()
        .unwrap();
    out.push_str(
        "/// The byte length of the longest name in [`ENTITIES`] — no reference is longer, so a\n\
         /// name search need not look past it.\n",
    );
    writeln!(
        out,
        "pub(crate) const LONGEST_ENTITY_NAME: usize = {longest};"
    )
    .unwrap();
    out
}

#[test]
fn entities_table_is_fresh() {
    let root = Path::new(env!("CARGO_MANIFEST_DIR"));
    let json_path = root.join("src/entities.json");
    if !json_path.exists() {
        // The published crate excludes the JSON (it ships only the generated table), so a
        // test run from the crates.io tarball has nothing to grade the table against.
        eprintln!(
            "skipping entities_table_is_fresh: src/entities.json is absent (a packaged crate)"
        );
        return;
    }
    let json = fs::read_to_string(&json_path).unwrap();
    let entities: BTreeMap<String, String> = serde_json::from_str(&json).unwrap();
    // A broken or truncated entities.json fails here rather than shipping a short table.
    assert!(
        entities.len() > 2000,
        "entity map suspiciously small: {} entries",
        entities.len()
    );
    assert!(
        entities.values().all(|characters| !characters.is_empty()),
        "an entity naming no characters cannot be decoded"
    );
    assert!(
        entities.keys().all(|name| name.is_ascii()),
        "a name the table holds unescaped must be ASCII"
    );

    let rendered = render(&build(&entities));
    let table = root.join("src/entities_table.rs");
    if std::env::var_os("TSV_ENTITIES_UPDATE").is_some_and(|v| v == "1") {
        fs::write(&table, &rendered).unwrap();
        return;
    }
    let committed = fs::read_to_string(&table).unwrap_or_default();
    assert!(
        committed == rendered,
        "src/entities_table.rs is stale against src/entities.json: run `deno task entities:update`"
    );
}