gedcomkit 0.1.1

//! A byte-preserving GEDCOM document model.
//!
//! This crate reads, represents, and writes GEDCOM — 5.5 through 7.x — on the
//! theory that the file is the truth and a library's job is to lose none of
//! it. Everything a file contains is represented whether or not the caller
//! understands it: unknown tags, vendor extensions, record order, and the
//! exact bytes of every line.
//!
//! The central guarantee is in [`Document::to_text`]: **a node no caller
//! touched is written back byte for byte.** That is what makes preservation a
//! property of the representation rather than a feature implemented per
//! construct, and it is why [`Node`] keeps its source line whenever the
//! canonical rendering of that line would differ from what arrived.
//!
//! The pieces, from the outside in:
//!
//! - [`decode`] turns the bytes of a file into text: byte-order marks, UTF-16,
//!   ANSEL, and the lies a `CHAR` line tells.
//! - [`Document::parse`] reads that text into records, under [`Limits`] that
//!   keep a hostile file from exhausting memory before it can be rejected.
//! - [`dates`], [`names`], [`tags`], and [`view`] are *readings*: projections
//!   computed on demand for display, sorting, and search, never a parallel
//!   model that could disagree with the document and never a rewrite of it.
//! - [`validate`] reports what the file says that cannot all be true, without
//!   refusing or changing any of it.
//! - [`convert`] rewrites a document between 5.5.1 and 7.0 as an explicit,
//!   reported operation; [`schema`] handles version 7's extension
//!   declarations.
//! - [`gedzip`] reads and writes the GEDZIP container, with the same bounds.
//!
//! What this crate deliberately does not contain: application extension tags
//! and their meanings, interface state, or any I/O beyond bytes handed to it.
//! Callers with their own extension vocabulary label and declare it
//! themselves ([`schema`], [`convert::to_version_7_with`]).
//!
//! # Quickstart
//!
//! ```
//! use gedcomkit::view::IndividualView;
//!
//! let bytes = b"0 HEAD\n1 GEDC\n2 VERS 7.0\n0 @I1@ INDI\n1 NAME Ada /Example/\n1 BIRT\n2 DATE 5 JAN 1882\n0 TRLR\n";
//!
//! // Bytes to document: encoding sniffed and reported, then parsed.
//! let (mut document, report) = gedcomkit::Document::from_bytes(bytes)?;
//! assert!(report.summary().starts_with("Read as UTF-8"));
//!
//! // Read through a projection; the document stays the truth.
//! let record = document.record("@I1@").expect("known record");
//! let person = IndividualView::from_node(record);
//! assert_eq!(person.display_name(), "Ada Example");
//! assert_eq!(person.event_year("BIRT"), Some(1882));
//!
//! // Edit through the setters, which surrender exactly one kept line…
//! document
//!     .record_mut("@I1@")
//!     .and_then(|record| record.first_mut("NAME"))
//!     .expect("the name line")
//!     .set_logical_value("Ada /Lovelace/");
//!
//! // …and write back: every untouched line, byte for byte.
//! let written = document.to_bytes();
//! assert!(std::str::from_utf8(&written)?.contains("1 NAME Ada /Lovelace/"));
//! # Ok::<(), Box<dyn std::error::Error>>(())
//! ```

// Every public item carries documentation; the lint keeps that a property
// of the build rather than a habit.
#![warn(missing_docs)]

pub mod convert;
pub mod dates;
pub mod decode;
pub mod family;
#[cfg(feature = "gedzip")]
pub mod gedzip;
pub mod names;
pub mod schema;
#[cfg(feature = "fixture")]
pub mod synthetic;
pub mod tags;
pub mod validate;
pub mod view;

pub use decode::{EncodingReport, GedcomEncoding, decode_gedcom};

use std::collections::{HashMap, HashSet};
use std::fmt;

/// Bounds on what will be read. Imported data is hostile, and
/// every one of these exists to keep a malformed or malicious file from
/// exhausting memory before it can be rejected.
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
#[non_exhaustive]
pub struct Limits {
    /// Largest decoded document. Text is allocated beside the bytes it came
    /// from, so this bounds both. It admits the largest file in the fixture
    /// corpus, a 48 MB export of 203,154 people, with room to spare.
    pub input_bytes: usize,
    /// Longest single line. The specification's own limit is 255 characters
    /// and real producers exceed it; surveyed exports reach 913 bytes.
    /// This is a sanity bound, not a conformance check.
    pub line_bytes: usize,
    /// Deepest nesting. GEDCOM 7 uses at most 4; 64 is far beyond any real
    /// file and still bounds the recursive reader.
    pub depth: u16,
    /// Most level-zero records.
    pub records: usize,
    /// Most structures in total, counting every line of every record.
    pub structures: usize,
}

impl Limits {
    /// The default bounds.
    pub const DEFAULT: Self = Self {
        input_bytes: 128 * 1024 * 1024,
        line_bytes: 64 * 1024,
        depth: 64,
        records: 2_000_000,
        structures: 20_000_000,
    };

    /// These bounds with a different input-size ceiling.
    #[must_use]
    pub const fn with_input_bytes(mut self, input_bytes: usize) -> Self {
        self.input_bytes = input_bytes;
        self
    }

    /// These bounds with a different single-line ceiling.
    #[must_use]
    pub const fn with_line_bytes(mut self, line_bytes: usize) -> Self {
        self.line_bytes = line_bytes;
        self
    }

    /// These bounds with a different nesting-depth ceiling.
    #[must_use]
    pub const fn with_depth(mut self, depth: u16) -> Self {
        self.depth = depth;
        self
    }

    /// These bounds with a different record-count ceiling.
    #[must_use]
    pub const fn with_records(mut self, records: usize) -> Self {
        self.records = records;
        self
    }

    /// These bounds with a different total-structure ceiling.
    #[must_use]
    pub const fn with_structures(mut self, structures: usize) -> Self {
        self.structures = structures;
        self
    }
}

impl Default for Limits {
    fn default() -> Self {
        Self::DEFAULT
    }
}

/// What kind of fault a [`GedcomError`] reports, for callers that react
/// programmatically rather than showing the message.
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
#[non_exhaustive]
pub enum GedcomErrorKind {
    /// A [`Limits`] or [`gedzip::ArchiveLimits`] bound was exceeded. The input
    /// may be well-formed; it is refused for its size, depth, or count.
    Limit,
    /// A line could not be read: no level, no tag, a malformed
    /// cross-reference identifier.
    Syntax,
    /// The lines read but do not form records: a skipped nesting level, a
    /// file that does not begin at level zero.
    Structure,
    /// A GEDZIP container fault: a truncated or malformed archive, an unsafe
    /// entry path, a failed checksum.
    Archive,
}

/// A bounded fault in GEDCOM input, with the relevant one-based line.
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct GedcomError {
    line: usize,
    kind: GedcomErrorKind,
    message: String,
}

impl GedcomError {
    /// The one-based input line the fault was found on, or zero when the fault
    /// is about the file as a whole.
    #[must_use]
    pub const fn line(&self) -> usize {
        self.line
    }

    /// What kind of fault this is.
    #[must_use]
    pub const fn kind(&self) -> GedcomErrorKind {
        self.kind
    }

    /// What went wrong, without the line prefix.
    #[must_use]
    pub fn message(&self) -> &str {
        &self.message
    }
}

impl fmt::Display for GedcomError {
    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
        if self.line == 0 {
            formatter.write_str(&self.message)
        } else {
            write!(formatter, "GEDCOM line {}: {}", self.line, self.message)
        }
    }
}

impl std::error::Error for GedcomError {}

fn error(line: usize, message: impl Into<String>) -> GedcomError {
    fault(line, GedcomErrorKind::Syntax, message)
}

fn fault(line: usize, kind: GedcomErrorKind, message: impl Into<String>) -> GedcomError {
    GedcomError {
        line,
        kind,
        message: message.into(),
    }
}

/// One GEDCOM line and the lines nested beneath it.
///
/// The level is not stored. It is a function of position in the tree, and a
/// stored copy is one more thing a mutation can leave stale; it is computed on
/// write instead.
///
/// The line-owning fields are private so an edit cannot bypass the byte
/// preservation: every setter surrenders the node's kept source line, where a
/// direct field write would silently keep rendering the old bytes. `children`
/// stays public — the kept line describes only this node's own line, so
/// adding, removing, or reordering substructures cannot invalidate it, and a
/// child reached through it can in turn only be changed through its own
/// setters.
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct Node {
    xref: Option<String>,
    tag: String,
    value: Option<String>,
    /// Nested lines, in file order.
    pub children: Vec<Self>,
    /// The source line, kept only when rendering this node canonically would
    /// not reproduce it — an extra delimiter space, say, which `RootsMagic` 8
    /// writes. Round-tripping a file exactly is worth one string per oddity.
    verbatim: Option<Box<str>>,
}

impl Node {
    /// A node with a tag and nothing else.
    ///
    /// # Panics
    ///
    /// When the tag is not one [`Document::parse`] would read back — ASCII
    /// letters, digits, or underscore. A node that cannot re-parse would
    /// corrupt the document it is pushed into.
    #[must_use]
    pub fn new(tag: impl Into<String>) -> Self {
        let tag = tag.into();
        assert!(
            is_tag(&tag),
            "{tag:?} is not a GEDCOM tag: ASCII letters, digits, or underscore"
        );
        Self {
            xref: None,
            tag,
            value: None,
            children: Vec::new(),
            verbatim: None,
        }
    }

    /// A node with a tag and a payload. A payload holding newlines is split
    /// across `CONT` substructures, exactly as [`Node::set_logical_value`]
    /// would — written inline, a newline would corrupt every line after it.
    #[must_use]
    pub fn with_value(tag: impl Into<String>, value: impl Into<String>) -> Self {
        let value = value.into();
        if value.contains('\r') || value.contains('\n') {
            let mut node = Self::new(tag);
            node.set_logical_value(&value);
            return node;
        }
        Self {
            value: Some(value),
            ..Self::new(tag)
        }
    }

    /// A record: a node with a cross-reference identifier.
    ///
    /// # Panics
    ///
    /// When the identifier is not the `@XREF@` shape [`Document::parse`]
    /// would read back.
    #[must_use]
    pub fn record(xref: impl Into<String>, tag: impl Into<String>) -> Self {
        let xref = xref.into();
        assert!(
            is_xref(&xref),
            "{xref:?} is not a cross-reference identifier: the @I1@ shape"
        );
        Self {
            xref: Some(xref),
            ..Self::new(tag)
        }
    }

    /// The `@XREF@` token before the tag, on records that have one.
    #[must_use]
    pub fn xref(&self) -> Option<&str> {
        self.xref.as_deref()
    }

    /// The tag, including unknown and extension tags, exactly as written.
    #[must_use]
    pub fn tag(&self) -> &str {
        &self.tag
    }

    /// The payload after the tag, verbatim except for the line ending. A
    /// payload split across `CONT`/`CONC` lines is folded together by
    /// [`Node::logical_value`]; this is only the first line's share.
    #[must_use]
    pub fn value(&self) -> Option<&str> {
        self.value.as_deref()
    }

    /// Adds a substructure and returns the node, for building by chain.
    #[must_use]
    pub fn child(mut self, child: Self) -> Self {
        self.push(child);
        self
    }

    /// Adds a substructure. The node's own kept source line describes only
    /// its own line, so gaining a child does not surrender it.
    pub fn push(&mut self, child: Self) {
        self.children.push(child);
    }

    /// Gives up this node's verbatim source line.
    ///
    /// A node keeps the line it was read from so an untouched record writes
    /// back byte for byte. Anything that changes a node by reaching into it
    /// directly — a tag rewritten, a child removed — has to say so, or the
    /// record will be written from a line that no longer describes it.
    pub fn forget_verbatim(&mut self) {
        self.verbatim = None;
    }

    /// The source line this node still owes its rendering to, when it has one.
    ///
    /// `Some` means the line as parsed would not re-render identically — an
    /// extra delimiter space, say — and writing the document reproduces this
    /// text instead. A diff or an editor can use it to show that a node
    /// carries an odd original line.
    #[must_use]
    pub fn verbatim(&self) -> Option<&str> {
        self.verbatim.as_deref()
    }

    /// Replaces the single-line payload, giving up this node's verbatim source
    /// line because it no longer describes the node.
    ///
    /// # Panics
    ///
    /// When the value contains a line ending. Use [`Node::set_logical_value`]
    /// for user-entered or multiline text.
    pub fn set_value(&mut self, value: Option<String>) {
        assert!(
            value
                .as_deref()
                .is_none_or(|value| !value.contains('\r') && !value.contains('\n')),
            "a single-line node payload cannot contain a line ending"
        );
        self.verbatim = None;
        self.value = value;
    }

    /// Replaces the tag, giving up this node's verbatim source line because it
    /// no longer describes the node.
    ///
    /// # Panics
    ///
    /// When the tag is not one [`Document::parse`] would accept.
    pub fn set_tag(&mut self, tag: impl Into<String>) {
        let tag = tag.into();
        assert!(is_tag(&tag), "{tag:?} is not a GEDCOM tag");
        self.verbatim = None;
        self.tag = tag;
    }

    /// Replaces the cross-reference identifier, giving up this node's verbatim
    /// source line because it no longer describes the node.
    ///
    /// # Panics
    ///
    /// When an identifier is present and is not the `@XREF@` shape
    /// [`Document::parse`] would accept.
    pub fn set_xref(&mut self, xref: Option<String>) {
        assert!(
            xref.as_deref().is_none_or(is_xref),
            "the cross-reference identifier is not in @XREF@ form"
        );
        self.verbatim = None;
        self.xref = xref;
    }

    /// The payload with `CONT`/`CONC` substructures folded in: `CONT` adds a
    /// newline before its payload, `CONC` joins directly.
    ///
    /// The substructures themselves are left alone, so a value that is only
    /// read still writes back byte for byte.
    #[must_use]
    pub fn logical_value(&self) -> String {
        let mut text = self.value.clone().unwrap_or_default();
        for child in &self.children {
            match child.tag.as_str() {
                "CONT" => {
                    text.push('\n');
                    text.push_str(child.value.as_deref().unwrap_or_default());
                }
                "CONC" => text.push_str(child.value.as_deref().unwrap_or_default()),
                _ => (),
            }
        }
        text
    }

    /// Replaces the logical payload, splitting it across `CONT` lines when it
    /// holds newlines — the inverse of [`Node::logical_value`].
    ///
    /// This is *the* way to rewrite a payload. It rebuilds continuation lines
    /// only for the node being edited, which is why an untouched record keeps
    /// its own `CONC` splits: they are never re-derived. Continuations belong
    /// immediately after the payload, before any other substructure, and are
    /// inserted there.
    pub fn set_logical_value(&mut self, value: &str) {
        self.verbatim = None;
        self.children
            .retain(|child| !matches!(child.tag.as_str(), "CONT" | "CONC"));
        let normalized;
        let value = if value.contains('\r') {
            normalized = value.replace("\r\n", "\n").replace('\r', "\n");
            normalized.as_str()
        } else {
            value
        };
        let mut lines = value.split('\n');
        self.set_value(
            lines
                .next()
                .map(str::to_owned)
                .filter(|line| !line.is_empty()),
        );
        for (index, line) in lines.map(|line| Self::with_value("CONT", line)).enumerate() {
            self.children.insert(index, line);
        }
    }

    /// The payload read as a pointer, when it is one.
    #[must_use]
    pub fn pointer(&self) -> Option<&str> {
        self.value.as_deref().filter(|value| is_xref(value))
    }

    /// Whether this is the GEDCOM 7 placeholder pointer, which is a deliberate
    /// reference to nothing and is not a dangling pointer.
    #[must_use]
    pub fn is_void_pointer(&self) -> bool {
        self.pointer() == Some("@VOID@")
    }

    /// The first substructure with this tag.
    #[must_use]
    pub fn first(&self, tag: &str) -> Option<&Self> {
        self.children.iter().find(|child| child.tag == tag)
    }

    /// The first substructure with this tag, mutably. Any change made through
    /// the returned node goes through its setters, each of which surrenders
    /// that node's own kept line — nothing else needs surrendering.
    pub fn first_mut(&mut self, tag: &str) -> Option<&mut Self> {
        self.children.iter_mut().find(|child| child.tag == tag)
    }

    /// Every substructure with this tag, in file order.
    pub fn all<'a>(&'a self, tag: &'a str) -> impl Iterator<Item = &'a Self> {
        self.children.iter().filter(move |child| child.tag == tag)
    }

    /// The folded payload of the first substructure with this tag.
    #[must_use]
    pub fn value_of(&self, tag: &str) -> Option<String> {
        self.first(tag).map(Self::logical_value)
    }

    /// Substructures other than `CONT`/`CONC`, which belong to the payload.
    pub fn substructures(&self) -> impl Iterator<Item = &Self> {
        self.children
            .iter()
            .filter(|child| !matches!(child.tag.as_str(), "CONT" | "CONC"))
    }

    /// The structure at this path: the child index at each level, which is
    /// exactly what [`view::StructureView::path`] carries.
    #[must_use]
    pub fn at(&self, path: &[usize]) -> Option<&Self> {
        let mut node = self;
        for index in path {
            node = node.children.get(*index)?;
        }
        Some(node)
    }

    /// The structure at this path, mutably. Nodes on the way keep their
    /// verbatim source lines: each line describes only itself, and the
    /// returned node can only be changed through setters that surrender its
    /// own.
    pub fn at_mut(&mut self, path: &[usize]) -> Option<&mut Self> {
        let mut node = self;
        for index in path {
            node = node.children.get_mut(*index)?;
        }
        Some(node)
    }

    /// Removes the structure at this path and returns it.
    pub fn remove_at(&mut self, path: &[usize]) -> Option<Self> {
        let (last, parents) = path.split_last()?;
        let parent = self.at_mut(parents)?;
        (*last < parent.children.len()).then(|| parent.children.remove(*last))
    }

    /// This node and everything beneath it, depth first in file order.
    pub fn walk(&self) -> impl Iterator<Item = &Self> {
        let mut stack = vec![self];
        std::iter::from_fn(move || {
            let node = stack.pop()?;
            stack.extend(node.children.iter().rev());
            Some(node)
        })
    }

    /// How many lines this node and its substructures occupy.
    #[must_use]
    pub fn line_count(&self) -> usize {
        1 + self.children.iter().map(Self::line_count).sum::<usize>()
    }

    fn render_into(&self, level: u16, output: &mut String) {
        if let Some(verbatim) = &self.verbatim {
            output.push_str(verbatim);
        } else {
            render_line(
                level,
                self.xref.as_deref(),
                &self.tag,
                self.value.as_deref(),
                output,
            );
        }
        output.push('\n');
        for child in &self.children {
            child.render_into(level + 1, output);
        }
    }
}

fn render_line(
    level: u16,
    xref: Option<&str>,
    tag: &str,
    value: Option<&str>,
    output: &mut String,
) {
    let mut buffer = itoa(level);
    output.push_str(buffer.as_str());
    buffer.clear();
    output.push(' ');
    if let Some(xref) = xref {
        output.push_str(xref);
        output.push(' ');
    }
    output.push_str(tag);
    if let Some(value) = value {
        output.push(' ');
        output.push_str(value);
    }
}

fn itoa(level: u16) -> String {
    level.to_string()
}

/// A pointer with no record behind it, addressed precisely enough to repair.
///
/// The report is only half the job: a user told that `@I9@` is missing wants
/// to point it somewhere real, mark it deliberately unknown, or take the line
/// out. All three need the exact structure, not a sentence about it.
#[derive(Clone, Debug, PartialEq, Eq)]
#[non_exhaustive]
#[cfg_attr(feature = "serde", derive(serde::Serialize))]
#[cfg_attr(feature = "serde", serde(rename_all = "camelCase"))]
pub struct UnresolvedPointer {
    /// The record carrying it, by cross-reference identifier — or by tag, for
    /// the header and trailer, which have none and so cannot be repaired.
    pub record: String,
    /// The path to the structure inside that record, as [`Node::at`] reads it.
    pub path: Vec<usize>,
    /// That structure's tag.
    pub tag: String,
    /// The payload nothing answers to.
    pub pointer: String,
}

/// A GEDCOM document: the records of one file, in file order.
#[derive(Clone, Debug, Default, Eq, PartialEq)]
pub struct Document {
    /// Every level-zero record, including `HEAD` and `TRLR`.
    pub records: Vec<Node>,
}

impl Document {
    /// Reads a document straight from a file's bytes: [`decode_gedcom`]
    /// followed by [`Document::parse`], which is the pair every caller
    /// otherwise writes. The [`EncodingReport`] says what decoding decided
    /// and belongs in front of the user before an import is accepted.
    ///
    /// ```
    /// let bytes = b"0 HEAD\n1 GEDC\n2 VERS 7.0\n0 TRLR\n";
    /// let (document, report) = gedcomkit::Document::from_bytes(bytes)?;
    /// assert_eq!(document.records.len(), 2);
    /// assert!(report.summary().starts_with("Read as"));
    /// # Ok::<(), gedcomkit::GedcomError>(())
    /// ```
    ///
    /// # Errors
    ///
    /// As [`decode_gedcom`] and [`Document::parse`].
    pub fn from_bytes(bytes: &[u8]) -> Result<(Self, EncodingReport), GedcomError> {
        Self::from_bytes_with(bytes, Limits::DEFAULT)
    }

    /// Reads a document from bytes with explicit limits.
    ///
    /// # Errors
    ///
    /// As [`Document::from_bytes`].
    pub fn from_bytes_with(
        bytes: &[u8],
        limits: Limits,
    ) -> Result<(Self, EncodingReport), GedcomError> {
        let (text, report) = decode::decode_gedcom_with(bytes, limits)?;
        let document = Self::parse_with(&text, limits)?;
        Ok((document, report))
    }

    /// Reads a document with the default limits.
    ///
    /// ```
    /// let document = gedcomkit::Document::parse("0 HEAD\n0 @I1@ INDI\n1 _ANY kept\n0 TRLR\n")?;
    /// assert_eq!(document.records.len(), 3);
    /// assert_eq!(document.record("@I1@").and_then(|r| r.value_of("_ANY")).as_deref(), Some("kept"));
    /// # Ok::<(), gedcomkit::GedcomError>(())
    /// ```
    ///
    /// # Errors
    ///
    /// Returns [`GedcomError`] for input that is oversized, malformed, or
    /// structurally invalid. An unsupported tag is never an error: it stays in
    /// the tree like any other.
    pub fn parse(input: &str) -> Result<Self, GedcomError> {
        Self::parse_with(input, Limits::DEFAULT)
    }

    /// Reads a document with explicit limits.
    ///
    /// # Errors
    ///
    /// As [`Document::parse`].
    pub fn parse_with(input: &str, limits: Limits) -> Result<Self, GedcomError> {
        if input.len() > limits.input_bytes {
            return Err(fault(
                0,
                GedcomErrorKind::Limit,
                format!(
                    "the file is {} MB and the limit is {} MB",
                    input.len() / (1024 * 1024),
                    limits.input_bytes / (1024 * 1024)
                ),
            ));
        }

        // GEDCOM 5.5 allows CR, LF, or CRLF, and the 5.5 torture files are
        // written with bare CRs. Splitting on LF alone would leave a CR at the
        // end of every payload, which is a silent corruption rather than a
        // parse failure, so line ends are normalized first.
        let normalized;
        let input = if input.contains('\r') {
            normalized = input.replace("\r\n", "\n").replace('\r', "\n");
            normalized.as_str()
        } else {
            input
        };

        let mut parsed = Vec::new();
        for (index, line) in input.lines().enumerate() {
            if line.is_empty() {
                continue;
            }
            if parsed.len() >= limits.structures {
                return Err(fault(
                    index + 1,
                    GedcomErrorKind::Limit,
                    "the file has too many lines",
                ));
            }
            parsed.push(parse_line(index + 1, line, limits)?);
        }

        let mut position = 0;
        let mut records = Vec::new();
        while position < parsed.len() {
            if parsed[position].level != 0 {
                return Err(fault(
                    parsed[position].line,
                    GedcomErrorKind::Structure,
                    "a record must begin at level 0",
                ));
            }
            if records.len() >= limits.records {
                return Err(fault(
                    parsed[position].line,
                    GedcomErrorKind::Limit,
                    "the file has too many records",
                ));
            }
            records.push(build_node(&parsed, &mut position, 0)?);
        }
        Ok(Self { records })
    }

    /// Writes the document back out.
    ///
    /// A node that has not been touched since it was read reproduces its
    /// source line exactly; a node a command changed is rendered canonically.
    #[must_use]
    pub fn to_text(&self) -> String {
        let mut output = String::new();
        for record in &self.records {
            record.render_into(0, &mut output);
        }
        output
    }

    /// The document as the UTF-8 bytes a file should hold, with a `CHAR`
    /// declaration that tells the truth about them.
    ///
    /// [`Document::to_text`] renders exactly what the document holds — and a
    /// file read as ANSEL or Windows-1252 still holds the header line that
    /// says so. Serializing that text as UTF-8 under the old declaration
    /// tells the next reader to misdecode every byte above ASCII, so this
    /// renders with the `CHAR` payload corrected to `UTF-8` without touching
    /// the document itself. A caller that wants the correction to persist in
    /// the document calls [`Document::declare_utf8_encoding`] first; GEDCOM 7
    /// has no `CHAR` and a header without one is left alone.
    #[must_use]
    pub fn to_bytes(&self) -> Vec<u8> {
        let needs_fix = self.header().is_some_and(|header| {
            header
                .first("CHAR")
                .is_some_and(|declared| !declares_utf8(declared))
        });
        if !needs_fix {
            return self.to_text().into_bytes();
        }
        let mut corrected = self.clone();
        corrected.declare_utf8_encoding();
        corrected.to_text().into_bytes()
    }

    /// Makes the header's `CHAR` declaration say `UTF-8`, which is what
    /// [`Document::to_bytes`] writes. Returns whether anything changed; a
    /// header with no `CHAR` — every GEDCOM 7 file — is left alone.
    pub fn declare_utf8_encoding(&mut self) -> bool {
        let Some(header) = self.records.iter_mut().find(|record| record.tag == "HEAD") else {
            return false;
        };
        let Some(declared) = header.first_mut("CHAR") else {
            return false;
        };
        if declares_utf8(declared) {
            return false;
        }
        declared.set_value(Some("UTF-8".to_owned()));
        true
    }

    /// An index from upper-cased cross-reference identifier to position in
    /// [`Document::records`], built in one pass.
    ///
    /// [`Document::record`] scans the whole document per call, which is the
    /// right cost for one lookup and the wrong one for twenty thousand: build
    /// this once and index instead. When two records claim the same
    /// identifier the first wins, matching what [`Document::record`] finds.
    #[must_use]
    pub fn xref_index(&self) -> HashMap<String, usize> {
        let mut index = HashMap::with_capacity(self.records.len());
        for (position, record) in self.records.iter().enumerate() {
            if let Some(xref) = &record.xref {
                index.entry(xref.to_ascii_uppercase()).or_insert(position);
            }
        }
        index
    }

    /// The record with this cross-reference identifier.
    ///
    /// Matching is case-insensitive because 5.5.1 producers disagree about
    /// case and `xref-case.ged` in the fixture corpus proves it matters.
    #[must_use]
    pub fn record(&self, xref: &str) -> Option<&Node> {
        let wanted = xref.to_ascii_uppercase();
        self.records.iter().find(|record| {
            record
                .xref
                .as_ref()
                .is_some_and(|own| own.to_ascii_uppercase() == wanted)
        })
    }

    /// The record with this cross-reference identifier, mutably.
    pub fn record_mut(&mut self, xref: &str) -> Option<&mut Node> {
        let wanted = xref.to_ascii_uppercase();
        self.records.iter_mut().find(|record| {
            record
                .xref
                .as_ref()
                .is_some_and(|own| own.to_ascii_uppercase() == wanted)
        })
    }

    /// Every record carrying this tag, in file order.
    pub fn records_of<'a>(&'a self, tag: &'a str) -> impl Iterator<Item = &'a Node> {
        self.records.iter().filter(move |record| record.tag == tag)
    }

    /// The header record.
    #[must_use]
    pub fn header(&self) -> Option<&Node> {
        self.records.first().filter(|record| record.tag == "HEAD")
    }

    /// The GEDCOM version the header declares, as written.
    #[must_use]
    pub fn version(&self) -> Option<String> {
        self.header()?.first("GEDC")?.value_of("VERS")
    }

    /// Whether the header declares a version 7 or later, which decides
    /// `CONC` handling, `SNOTE`, `SCHMA`, and the shape of a written date.
    #[must_use]
    pub fn is_version_7_or_later(&self) -> bool {
        self.version()
            .and_then(|version| version.split('.').next()?.trim().parse::<u32>().ok())
            .is_some_and(|major| major >= 7)
    }

    /// The lowest unused cross-reference identifier with this prefix, in the
    /// `@I123@` style every producer uses.
    #[must_use]
    pub fn next_xref(&self, prefix: &str) -> String {
        let mut highest = 0u64;
        for record in &self.records {
            let Some(xref) = &record.xref else { continue };
            let inner = xref.trim_matches('@');
            let Some(digits) = inner.strip_prefix(prefix) else {
                continue;
            };
            if let Ok(number) = digits.parse::<u64>() {
                highest = highest.max(number);
            }
        }
        format!("@{prefix}{}@", highest + 1)
    }

    /// Every pointer in the document whose target is not a record, reported as
    /// `(record xref, pointer)`. `@VOID@` is not a dangling pointer.
    #[deprecated(
        since = "0.1.0",
        note = "use `unresolved_pointers`, which addresses each fault precisely enough to repair"
    )]
    #[must_use]
    pub fn dangling_pointers(&self) -> Vec<(String, String)> {
        self.unresolved_pointers()
            .into_iter()
            .map(|found| (found.record, found.pointer))
            .collect()
    }

    /// The same faults, each addressed precisely enough to repair.
    #[must_use]
    pub fn unresolved_pointers(&self) -> Vec<UnresolvedPointer> {
        // A set, not a list. A real file has tens of thousands of records and
        // as many pointers, and a linear membership test turns this into
        // billions of string comparisons — the same mistake that once made the
        // index take three and a half minutes.
        let known: HashSet<String> = self
            .records
            .iter()
            .filter_map(|record| record.xref.as_ref().map(|xref| xref.to_ascii_uppercase()))
            .collect();
        let mut problems = Vec::new();
        for record in &self.records {
            let owner = record.xref.clone().unwrap_or_else(|| record.tag.clone());
            // Depth first in file order, carrying the child index at each
            // level — the same address `Node::at` and the interface's structure
            // paths use, so a repair can name exactly one line.
            let mut stack: Vec<(Vec<usize>, &Node)> = vec![(Vec::new(), record)];
            while let Some((path, node)) = stack.pop() {
                if let Some(pointer) = node.pointer()
                    && pointer != "@VOID@"
                    && !known.contains(&pointer.to_ascii_uppercase())
                {
                    problems.push(UnresolvedPointer {
                        record: owner.clone(),
                        path: path.clone(),
                        tag: node.tag.clone(),
                        pointer: pointer.to_owned(),
                    });
                }
                for (index, child) in node.children.iter().enumerate().rev() {
                    let mut child_path = path.clone();
                    child_path.push(index);
                    stack.push((child_path, child));
                }
            }
        }
        problems
    }

    /// How many lines the document occupies.
    #[must_use]
    pub fn line_count(&self) -> usize {
        self.records.iter().map(Node::line_count).sum()
    }

    /// How many records the document holds besides the header and trailer,
    /// which are structure rather than content: counting them makes a
    /// one-person file read as three records.
    #[must_use]
    pub fn content_records(&self) -> usize {
        self.records
            .iter()
            .filter(|record| !matches!(record.tag.as_str(), "HEAD" | "TRLR"))
            .count()
    }

    /// A minimal valid GEDCOM 7.0 document: a header declaring the version,
    /// and a trailer. Records are inserted before the trailer.
    #[must_use]
    pub fn new_v7() -> Self {
        Self {
            records: vec![
                Node::new("HEAD").child(Node::new("GEDC").child(Node::with_value("VERS", "7.0"))),
                Node::new("TRLR"),
            ],
        }
    }

    /// A minimal valid GEDCOM 5.5.1 document, naming the producing system —
    /// 5.5.1 requires `HEAD`.`SOUR` — and declaring UTF-8.
    #[must_use]
    pub fn new_v551(source_system: &str) -> Self {
        Self {
            records: vec![
                Node::new("HEAD")
                    .child(Node::with_value("SOUR", source_system))
                    .child(
                        Node::new("GEDC")
                            .child(Node::with_value("VERS", "5.5.1"))
                            .child(Node::with_value("FORM", "LINEAGE-LINKED")),
                    )
                    .child(Node::with_value("CHAR", "UTF-8")),
                Node::new("TRLR"),
            ],
        }
    }
}

/// Whether a `CHAR` node already declares UTF-8.
fn declares_utf8(declared: &Node) -> bool {
    declared
        .value
        .as_deref()
        .is_some_and(|value| value.trim().eq_ignore_ascii_case("UTF-8"))
}

#[derive(Clone, Debug)]
struct ParsedLine {
    line: usize,
    level: u16,
    xref: Option<String>,
    tag: String,
    value: Option<String>,
    verbatim: Option<Box<str>>,
}

fn parse_line(line_number: usize, line: &str, limits: Limits) -> Result<ParsedLine, GedcomError> {
    if line.len() > limits.line_bytes {
        return Err(fault(
            line_number,
            GedcomErrorKind::Limit,
            "the line is longer than the limit",
        ));
    }
    let (level_text, remainder) = line
        .split_once(' ')
        .ok_or_else(|| error(line_number, "the line has no tag"))?;
    let level = level_text
        .parse::<u16>()
        .ok()
        .ok_or_else(|| error(line_number, "the line does not begin with a level"))?;
    if level > limits.depth {
        return Err(fault(
            line_number,
            GedcomErrorKind::Limit,
            "the line is nested deeper than the limit",
        ));
    }
    // The specification says one delimiter space and producers disagree:
    // RootsMagic 8 writes `0  _PUBLISH` with two. Extra spaces before the tag
    // are ignored; anything after the tag is payload and is left alone.
    let remainder = remainder.trim_start_matches(' ');
    let (first, remainder) = remainder
        .split_once(' ')
        .map_or((remainder, None), |(first, rest)| (first, Some(rest)));
    if first.is_empty() {
        return Err(error(line_number, "the line has no tag"));
    }
    let (xref, tag, value) = if is_xref(first) {
        let rest = remainder
            .filter(|value| !value.is_empty())
            .ok_or_else(|| error(line_number, "the record has an identifier but no tag"))?;
        let (tag, value) = rest
            .split_once(' ')
            .map_or((rest, None), |(tag, value)| (tag, Some(value)));
        (Some(first.to_owned()), tag, value)
    } else if first.starts_with('@') {
        return Err(error(
            line_number,
            "the cross-reference identifier is not closed, or contains a space",
        ));
    } else {
        (None, first, remainder)
    };
    if !is_tag(tag) {
        return Err(error(
            line_number,
            "a tag must be ASCII letters, digits, or underscore",
        ));
    }

    // Keep the source line only when writing the parsed pieces back would not
    // reproduce it, which is what lets an odd file round-trip exactly without
    // paying for a second copy of an ordinary one.
    let mut canonical = String::with_capacity(line.len());
    render_line(level, xref.as_deref(), tag, value, &mut canonical);
    let verbatim = (canonical != line).then(|| Box::from(line));

    Ok(ParsedLine {
        line: line_number,
        level,
        xref,
        tag: tag.to_owned(),
        value: value.map(str::to_owned),
        verbatim,
    })
}

fn build_node(
    lines: &[ParsedLine],
    position: &mut usize,
    expected_level: u16,
) -> Result<Node, GedcomError> {
    let current = &lines[*position];
    if current.level != expected_level {
        return Err(fault(
            current.line,
            GedcomErrorKind::Structure,
            "the line is nested at the wrong level",
        ));
    }
    let mut node = Node {
        xref: current.xref.clone(),
        tag: current.tag.clone(),
        value: current.value.clone(),
        children: Vec::new(),
        verbatim: current.verbatim.clone(),
    };
    *position += 1;
    while let Some(next) = lines.get(*position) {
        if next.level <= expected_level {
            break;
        }
        if next.level != expected_level + 1 {
            return Err(fault(
                next.line,
                GedcomErrorKind::Structure,
                "the line skips a nesting level",
            ));
        }
        node.children
            .push(build_node(lines, position, expected_level + 1)?);
    }
    Ok(node)
}

fn is_xref(value: &str) -> bool {
    value.len() >= 3
        && value.starts_with('@')
        && value.ends_with('@')
        && !value[1..value.len() - 1].contains('@')
}

fn is_tag(value: &str) -> bool {
    !value.is_empty()
        && value
            .bytes()
            .all(|byte| byte.is_ascii_alphanumeric() || byte == b'_')
}

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

    const SAMPLE: &str = "0 HEAD\n1 GEDC\n2 VERS 7.0\n1 CHAR UTF-8\n0 @I1@ INDI\n1 NAME Ada /Example/\n1 _VENDOR retained verbatim\n2 DATA extension child\n0 TRLR\n";

    #[test]
    fn unknown_extension_tags_and_values_round_trip() {
        let document = Document::parse(SAMPLE).expect("parse sample");

        assert_eq!(document.records.len(), 3);
        assert_eq!(document.records[1].xref.as_deref(), Some("@I1@"));
        assert_eq!(document.records[1].children[1].tag, "_VENDOR");
        assert_eq!(document.to_text(), SAMPLE);
    }

    #[test]
    fn an_unusual_line_is_written_back_exactly_as_it_arrived() {
        // RootsMagic 8 writes two spaces before the tag. Rendering the parsed
        // pieces would emit one, so the source line is kept instead.
        let input = "0 HEAD\n0  _PUBLISH\n0 TRLR\n";
        let document = Document::parse(input).expect("parse doubled delimiter");

        assert_eq!(document.records[1].tag, "_PUBLISH");
        assert_eq!(document.to_text(), input);
    }

    #[test]
    fn editing_a_node_gives_up_its_verbatim_line() {
        let mut document = Document::parse("0 HEAD\n0  _PUBLISH\n0 TRLR\n").expect("parse");
        document.records[1].set_value(Some("now".to_owned()));

        assert_eq!(document.to_text(), "0 HEAD\n0 _PUBLISH now\n0 TRLR\n");
    }

    #[test]
    fn continuation_lines_fold_for_reading_and_stay_put_for_writing() {
        let input = "0 HEAD\n0 @N1@ NOTE first\n1 CONT second\n1 CONC  and more\n0 TRLR\n";
        let document = Document::parse(input).expect("parse continuations");
        let note = document.record("@N1@").expect("note record");

        assert_eq!(note.logical_value(), "first\nsecond and more");
        assert_eq!(note.substructures().count(), 0);
        assert_eq!(document.to_text(), input);
    }

    #[test]
    fn parser_rejects_skipped_nesting_and_invalid_tags() {
        assert!(Document::parse("0 HEAD\n2 CHAR UTF-8\n").is_err());
        assert!(Document::parse("0 bad-tag\n").is_err());
    }

    #[test]
    fn a_space_inside_a_cross_reference_identifier_is_named_as_the_fault() {
        let failure = Document::parse("0 @NoTe ref@ NOTE text\n").expect_err("must fail");

        assert!(
            failure.message().contains("cross-reference"),
            "message blamed the wrong thing: {failure}"
        );
    }

    #[test]
    fn parser_accepts_every_line_ending_gedcom_allows() {
        for input in [
            "0 HEAD\n0 TRLR\n",
            "0 HEAD\r\n0 TRLR\r\n",
            "0 HEAD\r0 TRLR\r",
        ] {
            let document = Document::parse(input).expect("parse line endings");
            assert_eq!(document.records.len(), 2);
        }
    }

    #[test]
    fn pointers_resolve_case_insensitively_and_void_is_not_dangling() {
        let document = Document::parse(
            "0 HEAD\n0 @i1@ INDI\n1 FAMS @F1@\n1 ASSO @VOID@\n1 FAMC @F9@\n0 @f1@ FAM\n0 TRLR\n",
        )
        .expect("parse pointers");

        assert!(document.record("@I1@").is_some());
        let unresolved = document.unresolved_pointers();
        assert_eq!(unresolved.len(), 1);
        assert_eq!(unresolved[0].record, "@i1@");
        assert_eq!(unresolved[0].pointer, "@F9@");
        #[allow(
            deprecated,
            reason = "the deprecated form stays equivalent until removed"
        )]
        {
            assert_eq!(
                document.dangling_pointers(),
                vec![("@i1@".to_owned(), "@F9@".to_owned())]
            );
        }
    }

    #[test]
    fn next_xref_continues_the_files_own_numbering() {
        let document = Document::parse("0 HEAD\n0 @I1@ INDI\n0 @I7@ INDI\n0 @F1@ FAM\n0 TRLR\n")
            .expect("parse");

        assert_eq!(document.next_xref("I"), "@I8@");
        assert_eq!(document.next_xref("F"), "@F2@");
        assert_eq!(document.next_xref("S"), "@S1@");
    }

    #[test]
    fn version_is_read_from_the_header() {
        let five = Document::parse("0 HEAD\n1 GEDC\n2 VERS 5.5.1\n0 TRLR\n").expect("parse 5.5.1");
        let seven = Document::parse("0 HEAD\n1 GEDC\n2 VERS 7.0\n0 TRLR\n").expect("parse 7.0");

        assert_eq!(five.version().as_deref(), Some("5.5.1"));
        assert!(!five.is_version_7_or_later());
        assert!(seven.is_version_7_or_later());
    }

    #[test]
    fn a_structure_is_addressed_by_the_path_the_record_view_shows() {
        let mut document = Document::parse(
            "0 HEAD\n0 @I1@ INDI\n1 NAME Ada /Example/\n1 BIRT\n2 DATE 1815\n2 PLAC London\n0 TRLR\n",
        )
        .expect("parse");
        let record = document.record_mut("@I1@").expect("individual");

        assert_eq!(record.at(&[1, 0]).expect("date").logical_value(), "1815");
        record
            .at_mut(&[1, 0])
            .expect("date")
            .set_value(Some("10 December 1815".to_owned()));
        assert_eq!(record.remove_at(&[1, 1]).expect("place").tag, "PLAC");

        assert_eq!(
            document.to_text(),
            "0 HEAD\n0 @I1@ INDI\n1 NAME Ada /Example/\n1 BIRT\n2 DATE 10 December 1815\n0 TRLR\n"
        );
    }

    #[test]
    fn set_logical_value_is_the_inverse_of_logical_value() {
        let mut node = Node::with_value("NOTE", "first");
        node.push(Node::with_value("CONC", " and more"));
        node.push(Node::with_value("SOUR", "@S1@"));

        node.set_logical_value("one\ntwo\nthree");
        assert_eq!(node.logical_value(), "one\ntwo\nthree");
        // Continuations come before other substructures, as GEDCOM requires,
        // and the old CONC is gone rather than re-derived.
        let tags: Vec<&str> = node
            .children
            .iter()
            .map(|child| child.tag.as_str())
            .collect();
        assert_eq!(tags, ["CONT", "CONT", "SOUR"]);

        node.set_logical_value("");
        assert_eq!(node.value, None);
        assert_eq!(node.logical_value(), "");
    }

    #[test]
    fn content_records_exclude_the_header_and_trailer() {
        let document = Document::parse(SAMPLE).expect("parse sample");
        assert_eq!(document.records.len(), 3);
        assert_eq!(document.content_records(), 1);
    }

    #[test]
    fn limits_refuse_a_line_longer_than_the_bound() {
        let limits = Limits::DEFAULT.with_line_bytes(32);
        let long = format!("0 HEAD\n1 NOTE {}\n0 TRLR\n", "x".repeat(64));

        let failure = Document::parse_with(&long, limits).expect_err("must refuse");
        assert_eq!(failure.kind(), GedcomErrorKind::Limit);
        assert_eq!(failure.line(), 2, "the long line is named");
    }

    #[test]
    fn limits_refuse_nesting_deeper_than_the_bound() {
        let limits = Limits::DEFAULT.with_depth(3);
        let deep = "0 HEAD\n1 A\n2 B\n3 C\n4 D\n0 TRLR\n";

        let failure = Document::parse_with(deep, limits).expect_err("must refuse");
        assert_eq!(failure.kind(), GedcomErrorKind::Limit);
    }

    #[test]
    fn limits_refuse_a_flat_file_with_too_many_structures() {
        // A pathological file need not nest at all; the structure count is
        // what stops it before the record limit would.
        let limits = Limits::DEFAULT.with_structures(4);
        let flat = "0 HEAD\n1 NOTE a\n1 NOTE b\n1 NOTE c\n1 NOTE d\n0 TRLR\n";

        let failure = Document::parse_with(flat, limits).expect_err("must refuse");
        assert_eq!(failure.kind(), GedcomErrorKind::Limit);
    }

    #[test]
    fn error_kinds_tell_a_bound_from_a_malformed_line() {
        assert_eq!(
            Document::parse("0 bad-tag\n").expect_err("syntax").kind(),
            GedcomErrorKind::Syntax
        );
        assert_eq!(
            Document::parse("0 HEAD\n2 CHAR UTF-8\n")
                .expect_err("structure")
                .kind(),
            GedcomErrorKind::Structure
        );
    }

    #[test]
    fn a_builder_payload_with_newlines_becomes_continuation_lines() {
        // Written inline, the newline would corrupt every line after it; the
        // builder must produce the same shape set_logical_value would.
        let node = Node::with_value("NOTE", "first\nsecond");
        let text = Document {
            records: vec![node],
        }
        .to_text();

        assert_eq!(text, "0 NOTE first\n1 CONT second\n");
        Document::parse(&text).expect("the built document re-parses");
    }

    #[test]
    fn a_builder_normalizes_every_line_ending_into_continuations() {
        let node = Node::with_value("NOTE", "first\r\nsecond\rthird\nfourth");

        assert_eq!(node.logical_value(), "first\nsecond\nthird\nfourth");
        assert!(
            !Document {
                records: vec![node.clone()]
            }
            .to_text()
            .contains('\r')
        );
        assert_eq!(node.all("CONT").count(), 3);
    }

    #[test]
    fn programmatic_fields_that_could_inject_a_line_are_refused() {
        assert!(std::panic::catch_unwind(|| Node::new("NAME\n0 TRLR")).is_err());
        assert!(std::panic::catch_unwind(|| Node::record("@I1@\n0 TRLR", "INDI")).is_err());
        assert!(
            std::panic::catch_unwind(|| {
                let mut node = Node::new("NOTE");
                node.set_value(Some("text\n0 TRLR".to_owned()));
            })
            .is_err()
        );
        assert!(
            std::panic::catch_unwind(|| {
                let mut node = Node::new("NOTE");
                node.set_tag("NOTE\n0 TRLR");
            })
            .is_err()
        );
        assert!(
            std::panic::catch_unwind(|| {
                let mut node = Node::new("NOTE");
                node.set_xref(Some("@I1@\n0 TRLR".to_owned()));
            })
            .is_err()
        );
    }

    #[test]
    fn an_edit_beside_an_odd_line_leaves_the_odd_line_alone() {
        // RootsMagic's doubled delimiter, with an ordinary substructure
        // edited beneath it: the odd parent line must still write back byte
        // for byte, because only the child changed.
        let input = "0 HEAD\n0  _PUBLISH\n1 DATE 1900\n0 TRLR\n";
        let mut document = Document::parse(input).expect("parse");
        document.records[1]
            .first_mut("DATE")
            .expect("date")
            .set_value(Some("1901".to_owned()));

        assert_eq!(
            document.to_text(),
            "0 HEAD\n0  _PUBLISH\n1 DATE 1901\n0 TRLR\n"
        );
    }

    #[test]
    fn to_bytes_corrects_a_char_declaration_the_bytes_would_contradict() {
        let mut document =
            Document::parse("0 HEAD\n1 CHAR ANSEL\n0 @N1@ NOTE K\u{f6}nig\n0 TRLR\n")
                .expect("parse");

        // Rendering without the correction would tell the next reader to
        // misdecode every byte above ASCII.
        let bytes = document.to_bytes();
        let text = String::from_utf8(bytes).expect("UTF-8 out");
        assert!(text.contains("1 CHAR UTF-8"), "{text}");
        assert!(text.contains("K\u{f6}nig"), "{text}");

        // The document itself was not touched; the explicit form is what
        // persists the change.
        assert!(document.to_text().contains("1 CHAR ANSEL"));
        assert!(document.declare_utf8_encoding());
        assert!(document.to_text().contains("1 CHAR UTF-8"));
        assert!(!document.declare_utf8_encoding(), "already true");
    }

    #[test]
    fn limits_refuse_a_file_with_too_many_records() {
        let limits = Limits {
            records: 2,
            ..Limits::DEFAULT
        };
        let failure =
            Document::parse_with("0 HEAD\n0 @I1@ INDI\n0 TRLR\n", limits).expect_err("must refuse");

        assert!(failure.to_string().contains("too many records"));
    }
}