gedcomkit 0.1.11

//! The family graph: who is whose parent, child, and partner.
//!
//! A GEDCOM family is written twice — a `FAM` record lists `HUSB`, `WIFE`,
//! and `CHIL`, and each individual carries `FAMC`/`FAMS` links pointing back —
//! and real files routinely write only one of the two directions. A surveyed
//! 20,000-person export records every child through `FAMC` alone, with not a
//! single `CHIL` line. A walk that reads only one side draws half a family, so
//! [`FamilyGraph`] merges both directions: everything either side asserts is
//! in the graph.
//!
//! Cross-reference identifiers are matched case-insensitively, as everywhere
//! in this crate, and the ancestor and descendant walks are bounded so a file
//! that makes somebody their own ancestor is traversed safely rather than
//! looped over.

use crate::Document;
use std::collections::HashMap;

/// How far an ancestor or descendant walk goes before deciding the file is
/// looping. No real pedigree is this deep; a file that claims to be is a file
/// with a cycle in it.
const MAX_GENERATIONS: u32 = 128;

/// One family's membership, read from both directions of the link.
#[derive(Clone, Debug, Default, Eq, PartialEq)]
#[non_exhaustive]
#[cfg_attr(feature = "serde", derive(serde::Serialize))]
#[cfg_attr(feature = "ts", derive(ts_rs::TS))]
#[cfg_attr(feature = "serde", serde(rename_all = "camelCase"))]
pub struct FamilyMembers {
    /// The partners: `HUSB` and `WIFE` pointers, plus anyone whose own `FAMS`
    /// names this family. In file order, the `FAM` record's side first.
    pub partners: Vec<String>,
    /// The children: `CHIL` pointers, plus anyone whose own `FAMC` names this
    /// family. In file order, the `FAM` record's side first.
    pub children: Vec<String>,
}

/// The family graph of one document, built once and asked repeatedly.
///
/// Everything is keyed by upper-cased cross-reference identifier, and the
/// answers return identifiers exactly as the file wrote them at the first
/// place each person was seen.
///
/// ```
/// use gedcomkit::{Document, family::FamilyGraph};
///
/// // A one-sided file: the family lists no children, only the child
/// // points at the family. The graph still knows whose child @I3@ is.
/// let document = Document::parse(
///     "0 HEAD\n0 @I1@ INDI\n0 @I3@ INDI\n1 FAMC @F1@\n0 @F1@ FAM\n1 HUSB @I1@\n0 TRLR\n",
/// )?;
/// let graph = FamilyGraph::new(&document);
/// assert_eq!(graph.parents_of("@I3@"), ["@I1@"]);
/// assert_eq!(graph.children_of("@I1@"), ["@I3@"]);
/// # Ok::<(), gedcomkit::GedcomError>(())
/// ```
#[derive(Clone, Debug, Default)]
pub struct FamilyGraph {
    parents: HashMap<String, Vec<String>>,
    children: HashMap<String, Vec<String>>,
    partners: HashMap<String, Vec<String>>,
    families: HashMap<String, FamilyMembers>,
}

impl FamilyGraph {
    /// Reads the family graph in one pass over the document.
    #[must_use]
    pub fn new(document: &Document) -> Self {
        let mut graph = Self::default();

        // The FAM side first, addressed by identifier so the FAMC/FAMS pass
        // below is a lookup rather than a scan per link.
        for record in document.records_of("FAM") {
            let Some(xref) = &record.xref else { continue };
            let members = graph.families.entry(key(xref)).or_default();
            for tag in ["HUSB", "WIFE"] {
                for node in record.all(tag) {
                    if let Some(pointer) = node.pointer().filter(|value| *value != "@VOID@") {
                        push_unique(&mut members.partners, pointer);
                    }
                }
            }
            for node in record.all("CHIL") {
                if let Some(pointer) = node.pointer().filter(|value| *value != "@VOID@") {
                    push_unique(&mut members.children, pointer);
                }
            }
        }

        // The individual side: a FAMC or FAMS link adds its person to the
        // family whether or not the FAM record remembered them — and creates
        // the family when the file never wrote a FAM record at all.
        for record in document.records_of("INDI") {
            let Some(xref) = &record.xref else { continue };
            for (tag, side) in [("FAMC", Side::Child), ("FAMS", Side::Partner)] {
                for link in record.all(tag) {
                    let Some(family) = link.pointer().filter(|value| *value != "@VOID@") else {
                        continue;
                    };
                    let members = graph.families.entry(key(family)).or_default();
                    match side {
                        Side::Child => push_unique(&mut members.children, xref),
                        Side::Partner => push_unique(&mut members.partners, xref),
                    }
                }
            }
        }

        for members in graph.families.values() {
            for (index, one) in members.partners.iter().enumerate() {
                for other in &members.partners[index + 1..] {
                    push_unique(graph.partners.entry(key(one)).or_default(), other);
                    push_unique(graph.partners.entry(key(other)).or_default(), one);
                }
            }
            for child in &members.children {
                for parent in &members.partners {
                    push_unique(graph.parents.entry(key(child)).or_default(), parent);
                    push_unique(graph.children.entry(key(parent)).or_default(), child);
                }
            }
        }

        graph
    }

    /// This person's parents: everyone recorded as a partner in a family the
    /// person is a child of, from either direction of the link.
    #[must_use]
    pub fn parents_of(&self, xref: &str) -> &[String] {
        lookup(&self.parents, xref)
    }

    /// This person's children, from either direction of the link.
    #[must_use]
    pub fn children_of(&self, xref: &str) -> &[String] {
        lookup(&self.children, xref)
    }

    /// This person's partners across every family they appear in.
    #[must_use]
    pub fn partners_of(&self, xref: &str) -> &[String] {
        lookup(&self.partners, xref)
    }

    /// One family's merged membership, or `None` when nothing in the file
    /// names that family.
    #[must_use]
    pub fn family(&self, xref: &str) -> Option<&FamilyMembers> {
        self.families.get(&key(xref))
    }

    /// Every family the graph knows, keyed by upper-cased identifier —
    /// including families only ever named by a `FAMC`/`FAMS` link.
    #[must_use]
    pub const fn families(&self) -> &HashMap<String, FamilyMembers> {
        &self.families
    }

    /// Every ancestor, with how many generations up each one is. The person
    /// themselves is included at zero, because a common ancestor is often one
    /// of the two people being compared. Bounded, so a cyclic file terminates.
    #[must_use]
    pub fn ancestors(&self, xref: &str) -> HashMap<String, u32> {
        Self::walk(xref, &self.parents)
    }

    /// Every descendant, with how many generations down each one is, the
    /// person themselves at zero. Bounded, so a cyclic file terminates.
    #[must_use]
    pub fn descendants(&self, xref: &str) -> HashMap<String, u32> {
        Self::walk(xref, &self.children)
    }

    fn walk(start: &str, along: &HashMap<String, Vec<String>>) -> HashMap<String, u32> {
        let mut found: HashMap<String, u32> = HashMap::new();
        let mut frontier = vec![key(start)];
        found.insert(key(start), 0);
        for generation in 1..=MAX_GENERATIONS {
            let mut next = Vec::new();
            for person in frontier {
                for linked in along.get(&person).into_iter().flatten() {
                    let linked = key(linked);
                    if !found.contains_key(&linked) {
                        found.insert(linked.clone(), generation);
                        next.push(linked);
                    }
                }
            }
            if next.is_empty() {
                break;
            }
            frontier = next;
        }
        found
    }
}

enum Side {
    Child,
    Partner,
}

/// The canonical key for a cross-reference identifier: matching is
/// case-insensitive because 5.5.1 producers disagree about case.
fn key(xref: &str) -> String {
    xref.to_ascii_uppercase()
}

fn lookup<'a>(map: &'a HashMap<String, Vec<String>>, xref: &str) -> &'a [String] {
    map.get(&key(xref)).map_or(&[], Vec::as_slice)
}

fn push_unique(list: &mut Vec<String>, value: &str) {
    if !list.iter().any(|held| held.eq_ignore_ascii_case(value)) {
        list.push(value.to_owned());
    }
}

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

    fn graph(text: &str) -> FamilyGraph {
        FamilyGraph::new(&Document::parse(text).expect("parse"))
    }

    #[test]
    fn a_family_written_from_both_sides_is_read_once() {
        let graph = graph(
            "0 HEAD\n\
             0 @I1@ INDI\n1 FAMS @F1@\n\
             0 @I2@ INDI\n1 FAMS @F1@\n\
             0 @I3@ INDI\n1 FAMC @F1@\n\
             0 @F1@ FAM\n1 HUSB @I1@\n1 WIFE @I2@\n1 CHIL @I3@\n\
             0 TRLR\n",
        );

        assert_eq!(graph.parents_of("@I3@"), ["@I1@", "@I2@"]);
        assert_eq!(graph.children_of("@I1@"), ["@I3@"]);
        assert_eq!(graph.partners_of("@I2@"), ["@I1@"]);
        let family = graph.family("@F1@").expect("family");
        assert_eq!(family.partners, ["@I1@", "@I2@"]);
        assert_eq!(family.children, ["@I3@"]);
    }

    #[test]
    fn a_file_that_writes_only_famc_still_draws_the_whole_family() {
        // The commonest real-world defect: the FAM record forgets its
        // children, or never exists at all.
        let graph = graph(
            "0 HEAD\n\
             0 @I1@ INDI\n1 FAMS @F1@\n\
             0 @I3@ INDI\n1 FAMC @F1@\n\
             0 @I4@ INDI\n1 FAMC @F1@\n\
             0 TRLR\n",
        );

        assert_eq!(graph.parents_of("@I3@"), ["@I1@"]);
        assert_eq!(graph.children_of("@I1@"), ["@I3@", "@I4@"]);
        assert_eq!(
            graph.family("@F1@").expect("linked family").children,
            ["@I3@", "@I4@"]
        );
    }

    #[test]
    fn the_two_directions_disagreeing_reads_as_the_union() {
        let graph = graph(
            "0 HEAD\n\
             0 @I1@ INDI\n\
             0 @I2@ INDI\n1 FAMC @F1@\n\
             0 @F1@ FAM\n1 HUSB @I1@\n1 CHIL @I3@\n\
             0 @I3@ INDI\n\
             0 TRLR\n",
        );

        let family = graph.family("@F1@").expect("family");
        assert_eq!(family.children, ["@I3@", "@I2@"]);
        assert_eq!(graph.children_of("@I1@"), ["@I3@", "@I2@"]);
    }

    #[test]
    fn identifiers_match_case_insensitively_and_void_is_no_relative() {
        let graph = graph(
            "0 HEAD\n\
             0 @i1@ INDI\n1 FAMS @f1@\n\
             0 @I2@ INDI\n1 FAMC @F1@\n1 FAMC @VOID@\n\
             0 TRLR\n",
        );

        assert_eq!(graph.parents_of("@I2@"), ["@i1@"]);
        assert_eq!(graph.children_of("@I1@"), ["@I2@"]);
        assert!(graph.family("@VOID@").is_none());
    }

    #[test]
    fn a_cyclic_file_terminates_with_everyone_counted_once() {
        // @I1@ is their own grandparent. The walk must terminate and report
        // each person at the first generation they were reached.
        let graph = graph(
            "0 HEAD\n\
             0 @I1@ INDI\n1 FAMC @F1@\n1 FAMS @F2@\n\
             0 @I2@ INDI\n1 FAMS @F1@\n1 FAMC @F2@\n\
             0 TRLR\n",
        );

        let up = graph.ancestors("@I1@");
        assert_eq!(up.get("@I1@"), Some(&0));
        assert_eq!(up.get("@I2@"), Some(&1));
        assert_eq!(up.len(), 2);
    }

    #[test]
    fn ancestors_and_descendants_count_generations() {
        let graph = graph(
            "0 HEAD\n\
             0 @I1@ INDI\n\
             0 @I2@ INDI\n1 FAMC @F1@\n\
             0 @I3@ INDI\n1 FAMC @F2@\n\
             0 @F1@ FAM\n1 HUSB @I1@\n\
             0 @F2@ FAM\n1 HUSB @I2@\n\
             0 TRLR\n",
        );

        let down = graph.descendants("@I1@");
        assert_eq!(down.get("@I2@"), Some(&1));
        assert_eq!(down.get("@I3@"), Some(&2));
        let up = graph.ancestors("@I3@");
        assert_eq!(up.get("@I1@"), Some(&2));
    }
}