gedcomkit 0.1.8

//! A synthetic tree of any size, generated rather than collected.
//!
//! Performance and stress fixtures must be generated by committed code and
//! never derived from a real tree: a performance fixture that came from
//! somebody's family is living-person data wearing a benchmark's clothes.
//!
//! The shape matters as much as the size. A tree of 100,000 unrelated
//! individuals measures nothing a real file would: it has no pointers to
//! resolve, no families to walk, no citations to follow, and it compresses and
//! indexes quite unlike a real file. What is generated here is deliberately
//! shaped like a representative linked family-history document:
//!
//! - roughly one family per three people, each with two partners and children;
//! - a birth on almost everyone and a death on most;
//! - places drawn from a small pool, because a real tree reuses places heavily;
//! - a source per five people, cited from the individuals that use it;
//! - a note on one person in ten, and an identifier on all of them.
//!
//! Everything is deterministic: the same count always produces the same
//! document, byte for byte, so two measurements are comparable.

use crate::{Document, Node};
use std::fmt::Write as _;

/// A tiny deterministic generator. Not for anything that needs randomness to
/// be unguessable; only for making the same fixture twice.
struct Rng(u64);

impl Rng {
    const fn new(seed: u64) -> Self {
        Self(seed | 1)
    }

    /// `xorshift64*`, which is short, fast, and good enough to spread names.
    const fn next(&mut self) -> u64 {
        let mut value = self.0;
        value ^= value >> 12;
        value ^= value << 25;
        value ^= value >> 27;
        self.0 = value;
        value.wrapping_mul(0x2545_F491_4F6C_DD1D)
    }

    fn pick<'a, T>(&mut self, from: &'a [T]) -> &'a T {
        let index = usize::try_from(self.next() % (from.len() as u64)).unwrap_or(0);
        &from[index]
    }

    const fn below(&mut self, ceiling: u64) -> u64 {
        if ceiling == 0 {
            0
        } else {
            self.next() % ceiling
        }
    }
}

const GIVEN: [&str; 24] = [
    "Given-Aster",
    "Given-Bramble",
    "Given-Cinder",
    "Given-Dapple",
    "Given-Ember",
    "Given-Fable",
    "Given-Glimmer",
    "Given-Harbor",
    "Given-Indigo",
    "Given-Juniper",
    "Given-Kestrel",
    "Given-Lantern",
    "Given-Meadow",
    "Given-Nimbus",
    "Given-Orbit",
    "Given-Pebble",
    "Given-Quartz",
    "Given-Ripple",
    "Given-Sparrow",
    "Given-Thistle",
    "Given-Umber",
    "Given-Vesper",
    "Given-Willow",
    "Given-Zephyr",
];

const SURNAMES: [&str; 20] = [
    "Amberquill",
    "Birchvale",
    "Coppermere",
    "Dawnfield",
    "Emberwick",
    "Frostmere",
    "Glenquill",
    "Hearthvale",
    "Ironwill",
    "Juniperfall",
    "Kestrelmere",
    "Larkspur",
    "Moonridge",
    "Northwind",
    "Oakenshade",
    "Pinecroft",
    "Quartzwell",
    "Riverglass",
    "Starling",
    "Thornfield",
];

const PLACES: [&str; 12] = [
    "Northbridge, Example County",
    "Southmere, Example County",
    "Eastbarrow, Sample District",
    "Westhaven, Sample District",
    "Amber Crossing, Test Province",
    "Birch Hollow, Test Province",
    "Copper Bay, Fictional Region",
    "Dawn Ridge, Fictional Region",
    "Ember Falls, Demo Territory",
    "Frost Vale, Demo Territory",
    "Glen Harbor, Placeholder State",
    "Hearth Point, Placeholder State",
];

const OCCUPATIONS: [&str; 8] = [
    "Cabinetmaker",
    "Farmer",
    "Schoolteacher",
    "Machinist",
    "Seamstress",
    "Railway clerk",
    "Blacksmith",
    "Midwife",
];

/// Builds a synthetic document of about `people` individuals.
///
/// The count is exact for individuals; families, sources, and notes are added
/// in proportion, so the record total is roughly 1.4 times the person count.
#[must_use]
#[allow(
    clippy::too_many_lines,
    reason = "one pass that builds a whole tree reads better than five that each need the others' state"
)]
pub fn tree(people: usize) -> Document {
    let mut rng = Rng::new(0x5EED_5EED_5EED_5EED);
    let mut records = Vec::with_capacity(people * 2);

    records.push(
        Node::new("HEAD")
            .child(Node::new("GEDC").child(Node::with_value("VERS", "5.5.1")))
            .child(
                Node::with_value("SOUR", "GEDCOMKIT-SYNTHETIC")
                    .child(Node::with_value("NAME", "Generated performance fixture")),
            )
            .child(Node::with_value("CHAR", "UTF-8"))
            .child(Node::with_value(
                "NOTE",
                format!("Synthetic. {people} invented people; no real person is described here."),
            )),
    );

    let sources = (people / 5).max(1);
    for number in 1..=sources {
        records.push(
            Node::record(format!("@S{number}@"), "SOUR")
                .child(Node::with_value(
                    "TITL",
                    format!("Parish register, volume {number}"),
                ))
                .child(Node::with_value("AUTH", "Synthetic Records Office"))
                .child(Node::with_value("PUBL", "Generated for measurement")),
        );
    }

    // Families first, so an individual can name the family it belongs to
    // without a second pass. Three people to a family is the ratio the
    // representative linked documents have.
    let families = (people / 3).max(1);
    let mut family_of_child = vec![0usize; people + 1];
    let mut families_of_partner = vec![Vec::<usize>::new(); people + 1];
    let mut children_of_family = vec![Vec::<usize>::new(); families + 1];
    let mut partners_of_family = vec![Vec::<usize>::new(); families + 1];

    for family in 1..=families {
        // Partners come from earlier in the tree than their children, which is
        // what gives the document a generational shape rather than a random
        // graph.
        let husband = 1 + usize::try_from(rng.below(people as u64)).unwrap_or(0);
        let wife = 1 + usize::try_from(rng.below(people as u64)).unwrap_or(0);
        if husband != wife {
            partners_of_family[family] = vec![husband, wife];
            families_of_partner[husband].push(family);
            families_of_partner[wife].push(family);
        }

        let count = 1 + rng.below(4);
        for _ in 0..count {
            let child = 1 + usize::try_from(rng.below(people as u64)).unwrap_or(0);
            if partners_of_family[family].contains(&child) || family_of_child[child] != 0 {
                continue;
            }
            family_of_child[child] = family;
            children_of_family[family].push(child);
        }
    }

    for person in 1..=people {
        let given = rng.pick(&GIVEN);
        let surname = rng.pick(&SURNAMES);
        let birth = 1780 + rng.below(180);
        let mut record = Node::record(format!("@I{person}@"), "INDI")
            .child(Node::with_value("NAME", format!("{given} /{surname}/")))
            .child(Node::with_value(
                "SEX",
                if person % 2 == 0 { "F" } else { "M" },
            ));

        record.push(
            Node::new("BIRT")
                .child(Node::with_value("DATE", birth.to_string()))
                .child(Node::with_value("PLAC", *rng.pick(&PLACES))),
        );
        if rng.below(10) < 7 {
            record.push(
                Node::new("DEAT")
                    .child(Node::with_value(
                        "DATE",
                        (birth + 40 + rng.below(45)).to_string(),
                    ))
                    .child(Node::with_value("PLAC", *rng.pick(&PLACES))),
            );
        }
        if rng.below(10) < 4 {
            record.push(Node::with_value("OCCU", *rng.pick(&OCCUPATIONS)));
        }
        if rng.below(10) < 3 {
            record.push(
                Node::new("RESI")
                    .child(Node::with_value("DATE", (birth + 30).to_string()))
                    .child(Node::with_value("PLAC", *rng.pick(&PLACES))),
            );
        }

        if family_of_child[person] != 0 {
            record.push(Node::with_value(
                "FAMC",
                format!("@F{}@", family_of_child[person]),
            ));
        }
        for family in &families_of_partner[person] {
            record.push(Node::with_value("FAMS", format!("@F{family}@")));
        }

        let source = 1 + usize::try_from(rng.below(sources as u64)).unwrap_or(0);
        record.push(
            Node::with_value("SOUR", format!("@S{source}@")).child(Node::with_value(
                "PAGE",
                format!("folio {}", rng.below(400) + 1),
            )),
        );

        let mut identifier = String::new();
        let _ = write!(identifier, "SYN-{person:07}");
        record.push(
            Node::with_value("REFN", identifier).child(Node::with_value("TYPE", "Synthetic")),
        );
        if rng.below(10) == 0 {
            record.push(Node::with_value(
                "NOTE",
                "Two spellings appear in the register; the second is the one the family used.",
            ));
        }
        records.push(record);
    }

    for family in 1..=families {
        let mut record = Node::record(format!("@F{family}@"), "FAM");
        for (index, partner) in partners_of_family[family].iter().enumerate() {
            record.push(Node::with_value(
                if index == 0 { "HUSB" } else { "WIFE" },
                format!("@I{partner}@"),
            ));
        }
        for child in &children_of_family[family] {
            record.push(Node::with_value("CHIL", format!("@I{child}@")));
        }
        if !partners_of_family[family].is_empty() {
            record.push(
                Node::new("MARR")
                    .child(Node::with_value(
                        "DATE",
                        (1800 + rng.below(170)).to_string(),
                    ))
                    .child(Node::with_value("PLAC", *rng.pick(&PLACES))),
            );
        }
        records.push(record);
    }

    records.push(Node::new("TRLR"));
    Document { records }
}

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

    #[test]
    fn the_same_size_always_produces_the_same_document() {
        assert_eq!(tree(200).to_text(), tree(200).to_text());
    }

    #[test]
    fn it_is_corpus_shaped_rather_than_a_bag_of_strangers() {
        let document = tree(3_000);

        assert_eq!(document.records_of("INDI").count(), 3_000);
        let families = document.records_of("FAM").count();
        assert!(
            (900..=1_100).contains(&families),
            "about one family per three people, got {families}"
        );
        assert!(document.records_of("SOUR").count() >= 500);

        // Pointers in both directions, and every one of them resolves: a
        // fixture with dangling pointers would measure the error path.
        assert!(
            document.unresolved_pointers().is_empty(),
            "a synthetic tree must not measure the broken case by accident"
        );
        let with_family = document
            .records_of("INDI")
            .filter(|record| record.first("FAMC").is_some() || record.first("FAMS").is_some())
            .count();
        assert!(
            with_family > 1_500,
            "most people must belong to a family, got {with_family}"
        );
    }

    #[test]
    fn what_it_writes_reads_back_as_gedcom() {
        let text = tree(500).to_text();
        let reparsed = Document::parse(&text).expect("the fixture is valid GEDCOM");

        assert_eq!(reparsed.to_text(), text);
    }
}