gedcomkit 0.1.11

//! Writing a document from a producer's own data.
//!
//! Everything else in this crate starts from a file. This module is for the
//! other direction: a program that holds its family data in its own shape
//! and wants to write it as GEDCOM. [`NodeSpec`] is that shape at its
//! plainest — a tag, an optional identifier and payload, and substructures —
//! which is what a language binding hands across. [`Document::append_records`]
//! adds finished records, and [`Document::wrap_long_lines`] fits a 5.5.1 file
//! to the specification's 255-character line.
//!
//! ```
//! use gedcomkit::{Document, build::NodeSpec};
//!
//! let mut person = NodeSpec::record("@I1@", "INDI");
//! person.children.push(NodeSpec::with_value("NAME", "Ada /Example/"));
//! let mut document = Document::new_v551("EXAMPLE");
//! document.append_records(vec![person.into_node(gedcomkit::Limits::DEFAULT)?])?;
//! assert!(document.to_text().contains("0 @I1@ INDI\n1 NAME Ada /Example/\n0 TRLR\n"));
//! # Ok::<(), gedcomkit::GedcomError>(())
//! ```

use crate::{Document, GedcomError, GedcomErrorKind, Limits, Node, fault, is_tag, is_xref};
use std::collections::HashSet;

/// One structure described by the caller: what a producer builds before it
/// becomes a [`Node`].
///
/// Where [`Node::new`] panics on a tag the parser would not read back,
/// [`NodeSpec::into_node`] refuses it with an error, which is what input
/// from another language needs. With the `serde` feature it deserializes
/// from `{"tag": …, "xref": …, "value": …, "children": […]}`, every key but
/// `tag` optional and any other key refused — a misspelled `childs` is an
/// error, not a silently empty record.
#[derive(Clone, Debug, Default, Eq, PartialEq)]
#[non_exhaustive]
#[cfg_attr(feature = "serde", derive(serde::Deserialize))]
#[cfg_attr(feature = "serde", serde(deny_unknown_fields))]
pub struct NodeSpec {
    /// The `@XREF@` identifier. Only a record — a structure at level zero —
    /// may carry one.
    #[cfg_attr(feature = "serde", serde(default))]
    pub xref: Option<String>,
    /// The tag: ASCII letters, digits, or underscore.
    pub tag: String,
    /// The logical payload. A newline in it becomes a `CONT` line; an empty
    /// payload is the same as none, since GEDCOM cannot tell them apart.
    #[cfg_attr(feature = "serde", serde(default))]
    pub value: Option<String>,
    /// Substructures, in the order they are to be written.
    #[cfg_attr(feature = "serde", serde(default))]
    pub children: Vec<Self>,
}

impl NodeSpec {
    /// A structure with a tag and nothing else.
    #[must_use]
    pub fn new(tag: impl Into<String>) -> Self {
        Self {
            tag: tag.into(),
            ..Self::default()
        }
    }

    /// A structure with a tag and a payload.
    #[must_use]
    pub fn with_value(tag: impl Into<String>, value: impl Into<String>) -> Self {
        Self {
            value: Some(value.into()),
            ..Self::new(tag)
        }
    }

    /// A record: a structure with an identifier.
    #[must_use]
    pub fn record(xref: impl Into<String>, tag: impl Into<String>) -> Self {
        Self {
            xref: Some(xref.into()),
            ..Self::new(tag)
        }
    }

    /// Checks the description and builds the node it describes.
    ///
    /// # Errors
    ///
    /// A [`GedcomErrorKind::Syntax`] error names the first tag or identifier
    /// the parser would not read back — including an identifier below level
    /// zero, where GEDCOM has none — and a [`GedcomErrorKind::Limit`] error
    /// a description nested deeper than `limits.depth` or larger than
    /// `limits.structures`.
    pub fn into_node(self, limits: Limits) -> Result<Node, GedcomError> {
        let mut structures = 0;
        self.build(0, limits, &mut structures)
    }

    /// As [`NodeSpec::into_node`], for a substructure rather than a record:
    /// an identifier on it is refused too.
    ///
    /// # Errors
    ///
    /// As [`NodeSpec::into_node`].
    pub fn into_substructure(self, limits: Limits) -> Result<Node, GedcomError> {
        let mut structures = 0;
        self.build(1, limits, &mut structures)
    }

    fn build(
        self,
        level: u16,
        limits: Limits,
        structures: &mut usize,
    ) -> Result<Node, GedcomError> {
        if level > limits.depth {
            return Err(fault(
                0,
                GedcomErrorKind::Limit,
                "the structure is nested deeper than the limit",
            ));
        }
        *structures += 1;
        if *structures > limits.structures {
            return Err(fault(
                0,
                GedcomErrorKind::Limit,
                "the record has too many structures",
            ));
        }
        if !is_tag(&self.tag) {
            return Err(fault(
                0,
                GedcomErrorKind::Syntax,
                format!(
                    "{:?} is not a GEDCOM tag: ASCII letters, digits, or underscore",
                    self.tag
                ),
            ));
        }
        let mut node = match self.xref {
            Some(xref) if level > 0 => {
                return Err(fault(
                    0,
                    GedcomErrorKind::Syntax,
                    format!(
                        "{xref} is on a {} below level zero, where only records carry identifiers",
                        self.tag
                    ),
                ));
            }
            Some(xref) if !is_xref(&xref) || xref.contains(' ') => {
                return Err(fault(
                    0,
                    GedcomErrorKind::Syntax,
                    format!("{xref:?} is not a cross-reference identifier: the @I1@ shape"),
                ));
            }
            Some(xref) => Node::record(xref, self.tag),
            None => Node::new(self.tag),
        };
        if let Some(value) = self.value.filter(|value| !value.is_empty()) {
            node.set_logical_value(&value);
        }
        for child in self.children {
            node.push(child.build(level + 1, limits, structures)?);
        }
        Ok(node)
    }
}

/// A structure [`Document::wrap_long_lines`] rewrote, addressed as
/// [`crate::UnresolvedPointer`] addresses one.
#[derive(Clone, Debug, PartialEq, Eq)]
#[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 WrappedLine {
    /// The record, by cross-reference identifier — or by tag, for the header
    /// and anything else without one.
    pub record: String,
    /// The path to the structure inside that record, as [`Node::at`] reads
    /// it after the rewrite.
    pub path: Vec<usize>,
    /// That structure's tag.
    pub tag: String,
}

/// The fewest bytes a line limit may leave for level, tag, and payload.
const SMALLEST_LINE_LIMIT: usize = 32;

/// GEDCOM 5.5.1's line length limit, in bytes.
///
/// The specification: "The total length of a GEDCOM line, including level
/// number, cross-reference number, tag, value, delimiters, and terminator,
/// must not exceed 255 (wide) characters." GEDCOM 7.0 removed `CONC` and
/// every length limit, so this only matters for a document that declares
/// 5.5.x. Pass it to [`Node::fit_line_limit`] or
/// [`Document::wrap_long_lines`] — the two reserve a different number of
/// bytes for the line terminator; see [`Node::fit_line_limit`]'s own
/// documentation for why.
pub const MAX_LINE_LENGTH: usize = 255;

/// Bytes [`Node::fit_line_limit`] reserves for the line terminator when
/// measuring whether a line fits: exactly 2, for a `\r\n` (CRLF)
/// terminator. [`Document::wrap_long_lines`] reserves only 1, for the
/// `\n` this crate's own writer emits; `fit_line_limit` reserves the wider
/// CRLF instead because callers of this function may hand the result to a
/// pipeline that preserves the source file's own terminator — CRLF
/// included — rather than always writing LF. A line this leaves alone is
/// therefore safe under either terminator convention.
const TERMINATOR_RESERVE: usize = 2;

/// The bytes a line spends before its payload, payload delimiter included:
/// level, a space, the identifier and a space when there is one, the tag,
/// and the space that introduces the payload.
fn segment_prefix_bytes(level: usize, xref: Option<&str>, tag: &str) -> usize {
    level.to_string().len() + 1 + xref.map_or(0, |xref| xref.len() + 1) + tag.len() + 1
}

/// Fits one payload segment — a node's own line plus the `CONC` lines that
/// continue it without a newline — inside `max_line` bytes, the way
/// [`Node::fit_line_limit`] documents. `old_concs` is that segment's
/// existing trailing `CONC` children (already removed from the tree by the
/// caller); the return value is what should replace them.
///
/// Left alone, unconditionally: a segment whose head carries a verbatim
/// source line (its line is fixed, not ours to move text out of), a
/// segment with a verbatim `CONC` in it (same reason), a pointer payload
/// (pointers are short; splitting one would corrupt it), and a segment that
/// already fits. Otherwise every byte of the segment's folded text — the
/// head's value followed by each old `CONC`'s value, exactly as
/// [`Node::logical_value`] would fold them — is recut with [`cut`] and
/// redistributed, which is what guarantees the fold-after-split round trip.
fn resplit_segment(
    level: usize,
    xref: Option<&str>,
    tag: &str,
    verbatim: Option<&str>,
    value: &mut Option<String>,
    old_concs: Vec<Node>,
    max_line: usize,
) -> (Vec<Node>, bool) {
    if verbatim.is_some() || old_concs.iter().any(|conc| conc.verbatim.is_some()) {
        return (old_concs, false);
    }
    if value.as_deref().is_some_and(is_xref) {
        return (old_concs, false);
    }

    let head_budget =
        max_line.checked_sub(TERMINATOR_RESERVE + segment_prefix_bytes(level, xref, tag));
    let conc_budget =
        max_line.checked_sub(TERMINATOR_RESERVE + segment_prefix_bytes(level + 1, None, "CONC"));
    // Four bytes is the widest UTF-8 character: less and a cut may not be
    // able to make progress, so the line is left as it is.
    let (Some(head_budget), Some(conc_budget)) = (head_budget, conc_budget) else {
        return (old_concs, false);
    };
    if head_budget < 4 || conc_budget < 4 {
        return (old_concs, false);
    }

    let head_fits = value.as_deref().map_or(0, str::len) <= head_budget;
    let concs_fit = old_concs
        .iter()
        .all(|conc| conc.value.as_deref().map_or(0, str::len) <= conc_budget);
    if head_fits && concs_fit {
        return (old_concs, false);
    }

    let mut text = value.clone().unwrap_or_default();
    for conc in &old_concs {
        text.push_str(conc.value.as_deref().unwrap_or_default());
    }

    let mut pieces = cut(&text, head_budget, conc_budget).into_iter();
    let head_piece = pieces.next().unwrap_or_default();
    *value = (!head_piece.is_empty()).then(|| head_piece.to_owned());
    let new_concs = pieces
        .map(|piece| Node::with_value("CONC", piece))
        .collect();
    (new_concs, true)
}

impl Node {
    /// Fits this node and its substructures inside a 5.5.x document's line
    /// limit — [`MAX_LINE_LENGTH`] for the specification's own 255 bytes —
    /// by inserting `CONC` lines. Returns whether anything changed.
    ///
    /// Call this on the records a caller edited in a pre-7.0 document, just
    /// before serializing: [`Node::set_logical_value`] only ever splits a
    /// payload across `CONT` at the newlines it is given, so an edited note
    /// with one long paragraph is otherwise written as a single over-long
    /// line. `level` is the nesting level this node is rendered at — the
    /// same number [`Node::at`]'s caller already tracks, since a node does
    /// not store its own level (see the type's own documentation).
    ///
    /// Only nodes with no verbatim source line are touched, checked at
    /// every node this walks into, recursively: a node still carrying its
    /// verbatim line — meaning a caller never reached into it — is left
    /// exactly as it was, whether or not its rendered line is over length.
    /// That is what keeps this additive next to the byte-preservation
    /// guarantee: it only ever rewrites a node through the same setters an
    /// editing caller already surrendered the node's verbatim line to use.
    /// A payload read as a pointer ([`Node::pointer`]) is never split
    /// either — pointers are well under any real line limit, and cutting
    /// one would corrupt it.
    ///
    /// A too-long line becomes its payload's head plus `CONC` children
    /// inserted right after whatever `CONC` lines already continued that
    /// same line (so an existing, already-fitting split is preserved in
    /// place rather than reordered); a too-long `CONT` line is split the
    /// same way, into that `CONT` followed by its own new `CONC` siblings.
    /// Every cut lands on a UTF-8 character boundary and, whenever the
    /// payload has one within the limit, on a byte with a non-space
    /// character on each side, since GEDCOM 5.5.1 warns that a line broken
    /// beside a space loses that space on re-joining. Failing that — a run
    /// of spaces wider than the limit, say — the cut falls back to the
    /// latest legal byte boundary instead, which is documented behavior of
    /// [`cut`] this call reuses, not a special case here.
    ///
    /// The rendered line is measured in UTF-8 bytes, including level,
    /// optional cross-reference, tag, delimiters, and a terminator reserved
    /// at 2 bytes — a `\r\n` (CRLF) terminator, not the single-byte `\n`
    /// this crate's own writer emits. That is deliberately wider than
    /// [`Document::wrap_long_lines`]'s 1-byte reserve: this function exists
    /// for a caller that fits one edited record before handing the document
    /// on to something that may write it with the source file's own
    /// terminator, CRLF included, so a line this leaves alone is safe under
    /// either convention.
    ///
    /// ```
    /// use gedcomkit::{Node, build::MAX_LINE_LENGTH};
    ///
    /// let mut note = Node::record("@N1@", "NOTE");
    /// note.set_logical_value(&"word ".repeat(80));
    /// let changed = note.fit_line_limit(0, MAX_LINE_LENGTH);
    /// assert!(changed);
    /// assert_eq!(note.logical_value(), "word ".repeat(80));
    /// ```
    pub fn fit_line_limit(&mut self, level: usize, max_line: usize) -> bool {
        fit_node(self, level, max_line)
    }
}

fn fit_node(node: &mut Node, level: usize, max_line: usize) -> bool {
    let run_len = node
        .children
        .iter()
        .take_while(|child| matches!(child.tag.as_str(), "CONT" | "CONC"))
        .count();
    let mut run: Vec<Node> = node.children.drain(0..run_len).collect();
    let self_conc_end = run
        .iter()
        .position(|child| child.tag == "CONT")
        .unwrap_or(run.len());
    let self_concs: Vec<Node> = run.drain(0..self_conc_end).collect();

    let xref = node.xref.clone();
    let tag = node.tag.clone();
    let verbatim = node.verbatim.clone();
    let (mut output, mut changed) = resplit_segment(
        level,
        xref.as_deref(),
        &tag,
        verbatim.as_deref(),
        &mut node.value,
        self_concs,
        max_line,
    );
    if changed {
        node.verbatim = None;
    }

    let mut segments = run.into_iter().peekable();
    while let Some(mut cont) = segments.next() {
        let mut concs = Vec::new();
        while segments.peek().is_some_and(|next| next.tag == "CONC") {
            concs.push(segments.next().expect("peeked"));
        }
        let cont_verbatim = cont.verbatim.clone();
        let (new_concs, seg_changed) = resplit_segment(
            level + 1,
            None,
            "CONT",
            cont_verbatim.as_deref(),
            &mut cont.value,
            concs,
            max_line,
        );
        if seg_changed {
            cont.verbatim = None;
        }
        changed |= seg_changed;
        output.push(cont);
        output.extend(new_concs);
    }

    let inserted = output.len();
    node.children.splice(0..0, output);
    for child in node.children.iter_mut().skip(inserted) {
        changed |= fit_node(child, level + 1, max_line);
    }
    changed
}

impl Document {
    /// Adds substructures after the existing ones of the structure at `path`
    /// in `record` — a header's `DATE` and `SUBM`, say, which
    /// [`Document::new_v551`] cannot know.
    ///
    /// `record` is a cross-reference identifier, compared without regard to
    /// case, or the tag of a record that has none: `HEAD`. Adding
    /// substructures leaves every existing line as it was, so a parsed
    /// document keeps its byte-for-byte guarantee everywhere else.
    ///
    /// ```
    /// use gedcomkit::{Document, Node};
    ///
    /// let mut document = Document::new_v551("EXAMPLE");
    /// document.append_structures("HEAD", &[], vec![Node::with_value("SUBM", "@U1@")])?;
    /// assert_eq!(document.header().and_then(|header| header.value_of("SUBM")).as_deref(), Some("@U1@"));
    /// # Ok::<(), gedcomkit::GedcomError>(())
    /// ```
    ///
    /// # Errors
    ///
    /// A [`GedcomErrorKind::Structure`] error, with nothing added, when no
    /// record or structure answers to the address, and a
    /// [`GedcomErrorKind::Syntax`] error when a structure carries an
    /// identifier, which only a record may.
    pub fn append_structures(
        &mut self,
        record: &str,
        path: &[usize],
        structures: Vec<Node>,
    ) -> Result<(), GedcomError> {
        if let Some(named) = structures.iter().find(|node| node.xref.is_some()) {
            return Err(fault(
                0,
                GedcomErrorKind::Syntax,
                format!(
                    "a {} below level zero cannot carry an identifier",
                    named.tag
                ),
            ));
        }
        let wanted = record.to_ascii_uppercase();
        let owner = self
            .records
            .iter_mut()
            .find(|node| {
                node.xref.as_ref().map_or_else(
                    || node.tag == record,
                    |xref| xref.to_ascii_uppercase() == wanted,
                )
            })
            .ok_or_else(|| fault(0, GedcomErrorKind::Structure, format!("no record {record}")))?;
        let target = owner.at_mut(path).ok_or_else(|| {
            fault(
                0,
                GedcomErrorKind::Structure,
                format!("no structure at {path:?} in {record}"),
            )
        })?;
        target.children.extend(structures);
        Ok(())
    }

    /// Adds records before the trailer, all or none.
    ///
    /// # Errors
    ///
    /// A [`GedcomErrorKind::Structure`] error, with nothing added, when a
    /// record is a header or trailer — the document already has its own — or
    /// when an identifier repeats one the document holds or another record in
    /// the same call (compared without regard to case, as
    /// [`Document::record`] compares).
    pub fn append_records(&mut self, records: Vec<Node>) -> Result<(), GedcomError> {
        let mut seen: HashSet<String> = self.xref_index().into_keys().collect();
        for record in &records {
            if matches!(record.tag.as_str(), "HEAD" | "TRLR") {
                return Err(fault(
                    0,
                    GedcomErrorKind::Structure,
                    format!(
                        "a document has one {}, and this one already does",
                        record.tag
                    ),
                ));
            }
            if let Some(xref) = &record.xref
                && !seen.insert(xref.to_ascii_uppercase())
            {
                return Err(fault(
                    0,
                    GedcomErrorKind::Structure,
                    format!("the document already has a record {xref}"),
                ));
            }
        }
        let at = self
            .records
            .iter()
            .rposition(|record| record.tag == "TRLR")
            .unwrap_or(self.records.len());
        self.records.splice(at..at, records);
        Ok(())
    }

    /// Splits every line longer than `max_line_bytes` across `CONC` lines,
    /// the 5.5.1 way, and names each structure it rewrote.
    ///
    /// GEDCOM 5.5.1 limits a line to 255 characters, terminator included,
    /// and pass `255` for exactly that; the count here is of UTF-8 bytes,
    /// which is never fewer than characters, so a line that fits is safe
    /// under either reading. A payload is only ever cut at a character
    /// boundary, and never beside a space where a choice exists — the
    /// specification's warning, since some readers strip the space at the
    /// end of a line and lose it from the joined value.
    ///
    /// The terminator is reserved at 1 byte here, matching the single `\n`
    /// this crate's own writer emits ([`Document::to_text`],
    /// [`Document::to_bytes`]) — this function measures the document it is
    /// about to write out itself. [`Node::fit_line_limit`] reserves 2 bytes
    /// instead, for a caller that fits one record ahead of writing the
    /// document through something else that may keep the source file's own
    /// terminator, CRLF included.
    ///
    /// This rewrites what it touches, so it is an explicit operation with a
    /// report rather than something writing does: a structure that fits is
    /// left exactly as it is, and one that does not has its payload's
    /// continuation lines rebuilt — as [`Node::set_logical_value`] rebuilds
    /// them — and is named in the result. A line whose level, identifier,
    /// and tag alone leave no room for a payload is left as it is.
    ///
    /// ```
    /// let mut document = gedcomkit::Document::new_v551("EXAMPLE");
    /// let note = gedcomkit::Node::record("@N1@", "NOTE").child(gedcomkit::Node::with_value("CONT", "x".repeat(300)));
    /// document.append_records(vec![note])?;
    /// let wrapped = document.wrap_long_lines(255)?;
    /// assert_eq!(wrapped.len(), 1);
    /// assert!(document.to_text().lines().all(|line| line.len() < 255));
    /// assert_eq!(document.record("@N1@").map(|note| note.logical_value()), Some(format!("\n{}", "x".repeat(300))));
    /// # Ok::<(), gedcomkit::GedcomError>(())
    /// ```
    ///
    /// # Errors
    ///
    /// A [`GedcomErrorKind::Structure`] error when the document declares
    /// version 7, which has no `CONC` and no line limit, and a
    /// [`GedcomErrorKind::Limit`] error for a limit under 32 bytes.
    pub fn wrap_long_lines(
        &mut self,
        max_line_bytes: usize,
    ) -> Result<Vec<WrappedLine>, GedcomError> {
        if self.is_version_7_or_later() {
            return Err(fault(
                0,
                GedcomErrorKind::Structure,
                "version 7 has no CONC and no line limit, so there is nothing to wrap",
            ));
        }
        if max_line_bytes < SMALLEST_LINE_LIMIT {
            return Err(fault(
                0,
                GedcomErrorKind::Limit,
                format!(
                    "a line limit under {SMALLEST_LINE_LIMIT} bytes leaves no room for a payload"
                ),
            ));
        }
        // The terminator is part of the specification's count.
        let budget = max_line_bytes - 1;
        let mut wrapped = Vec::new();
        for record in &mut self.records {
            let owner = record.xref.clone().unwrap_or_else(|| record.tag.clone());
            let mut path = Vec::new();
            wrap_node(record, 0, budget, &owner, &mut path, &mut wrapped);
        }
        Ok(wrapped)
    }

    /// [`Node::fit_line_limit`] for one record, addressed by cross-reference
    /// identifier — the `Document`-level entry point for it, the way
    /// [`Document::record_mut`] is for reaching a record to edit it in the
    /// first place. Records sit at level 0, so unlike [`Node::fit_line_limit`]
    /// there is no level for the caller to track. Returns whether anything
    /// changed.
    ///
    /// ```
    /// use gedcomkit::{Document, Node, build::MAX_LINE_LENGTH};
    ///
    /// let mut document = Document::new_v551("EXAMPLE");
    /// let mut note = Node::record("@N1@", "NOTE");
    /// note.set_logical_value(&"word ".repeat(80));
    /// document.append_records(vec![note])?;
    ///
    /// assert!(document.fit_line_limit("@N1@", MAX_LINE_LENGTH)?);
    /// assert!(document.to_text().lines().all(|line| line.len() < MAX_LINE_LENGTH));
    /// # Ok::<(), gedcomkit::GedcomError>(())
    /// ```
    ///
    /// # Errors
    ///
    /// A [`GedcomErrorKind::Structure`] error when no record answers to
    /// `xref`.
    pub fn fit_line_limit(&mut self, xref: &str, max_line: usize) -> Result<bool, GedcomError> {
        let record = self
            .record_mut(xref)
            .ok_or_else(|| fault(0, GedcomErrorKind::Structure, format!("no record {xref}")))?;
        Ok(record.fit_line_limit(0, max_line))
    }
}

fn wrap_node(
    node: &mut Node,
    level: u16,
    budget: usize,
    owner: &str,
    path: &mut Vec<usize>,
    wrapped: &mut Vec<WrappedLine>,
) {
    if needs_wrapping(node, level, budget) && rewrap(node, level, budget) {
        wrapped.push(WrappedLine {
            record: owner.to_owned(),
            path: path.clone(),
            tag: node.tag.clone(),
        });
    }
    for (index, child) in node.children.iter_mut().enumerate() {
        if matches!(child.tag.as_str(), "CONT" | "CONC") {
            continue;
        }
        path.push(index);
        wrap_node(child, level + 1, budget, owner, path, wrapped);
        path.pop();
    }
}

/// The bytes a line spends before its payload: level, a space, the
/// identifier and a space when there is one, the tag, and the space that
/// introduces the payload.
fn prefix_bytes(level: u16, xref: Option<&str>, tag: &str) -> usize {
    level.to_string().len() + 1 + xref.map_or(0, |xref| xref.len() + 1) + tag.len() + 1
}

fn line_bytes(node: &Node, level: u16) -> usize {
    node.verbatim.as_deref().map_or_else(
        || {
            prefix_bytes(level, node.xref.as_deref(), &node.tag) - 1
                + node.value.as_deref().map_or(0, |value| value.len() + 1)
        },
        str::len,
    )
}

fn needs_wrapping(node: &Node, level: u16, budget: usize) -> bool {
    line_bytes(node, level) > budget
        || node
            .children
            .iter()
            .filter(|child| matches!(child.tag.as_str(), "CONT" | "CONC"))
            .any(|child| line_bytes(child, level + 1) > budget)
}

/// Rebuilds one node's payload lines to fit. Returns false, changing
/// nothing, when the first line has no room for a payload at all.
fn rewrap(node: &mut Node, level: u16, budget: usize) -> bool {
    let Some(first_room) = budget.checked_sub(prefix_bytes(level, node.xref.as_deref(), &node.tag))
    else {
        return false;
    };
    let continuation_room = budget.saturating_sub(prefix_bytes(level + 1, None, "CONC"));
    // Four bytes is the widest UTF-8 character: less and a cut may not be
    // able to make progress.
    if first_room < 4 || continuation_room < 4 {
        return false;
    }
    let logical = node.logical_value();
    let mut value = None;
    let mut continuations = Vec::new();
    for (index, line) in logical.split('\n').enumerate() {
        let room = if index == 0 {
            first_room
        } else {
            continuation_room
        };
        let mut pieces = cut(line, room, continuation_room).into_iter();
        let head = pieces.next().filter(|piece| !piece.is_empty());
        if index == 0 {
            value = head.map(str::to_owned);
        } else {
            continuations.push(
                head.map_or_else(|| Node::new("CONT"), |head| Node::with_value("CONT", head)),
            );
        }
        continuations.extend(pieces.map(|piece| Node::with_value("CONC", piece)));
    }
    node.children
        .retain(|child| !matches!(child.tag.as_str(), "CONT" | "CONC"));
    node.set_value(value);
    for (index, continuation) in continuations.into_iter().enumerate() {
        node.children.insert(index, continuation);
    }
    true
}

/// Cuts one line of payload into pieces: the first at most `first` bytes, the
/// rest at most `rest`. Cuts fall on character boundaries and, where the
/// text allows, not beside a space.
fn cut(line: &str, first: usize, rest: usize) -> Vec<&str> {
    let mut pieces = Vec::new();
    let mut remaining = line;
    let mut room = first;
    while remaining.len() > room {
        let at = best_cut(remaining, room);
        pieces.push(&remaining[..at]);
        remaining = &remaining[at..];
        room = rest;
    }
    pieces.push(remaining);
    pieces
}

/// Where to cut `text` so the first piece holds at most `room` bytes: the
/// widest boundary with no space on either side of it; failing that, one
/// that at least leaves no space at the end of the line, where a reader is
/// likeliest to strip it; failing both, the widest. The search stays in the
/// upper half of the room, so text with few such boundaries still gets
/// lines of a useful length.
fn best_cut(text: &str, room: usize) -> usize {
    let widest = floor_boundary(text, room);
    let lowest = (widest / 2).max(1);
    let boundaries = || {
        (lowest..=widest)
            .rev()
            .filter(|&at| text.is_char_boundary(at))
    };
    boundaries()
        .find(|&at| !text[..at].ends_with(' ') && !text[at..].starts_with(' '))
        .or_else(|| boundaries().find(|&at| !text[..at].ends_with(' ')))
        .unwrap_or(widest)
}

/// The largest character boundary at or below `index`.
fn floor_boundary(text: &str, index: usize) -> usize {
    let mut at = index.min(text.len());
    while !text.is_char_boundary(at) {
        at -= 1;
    }
    at
}

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

    fn spec(tag: &str) -> NodeSpec {
        NodeSpec::new(tag)
    }

    #[test]
    fn a_description_becomes_the_node_it_describes() {
        let mut record = NodeSpec::record("@I1@", "INDI");
        let mut birth = spec("BIRT");
        birth
            .children
            .push(NodeSpec::with_value("DATE", "5 JAN 1882"));
        record
            .children
            .push(NodeSpec::with_value("NAME", "Ada /Example/"));
        record.children.push(birth);
        record
            .children
            .push(NodeSpec::with_value("NOTE", "one\ntwo"));
        record.children.push(NodeSpec::with_value("SEX", ""));
        let node = record.into_node(Limits::DEFAULT).expect("valid");
        let text = Document {
            records: vec![node],
        }
        .to_text();
        assert_eq!(
            text,
            "0 @I1@ INDI\n1 NAME Ada /Example/\n1 BIRT\n2 DATE 5 JAN 1882\n1 NOTE one\n2 CONT two\n1 SEX\n"
        );
    }

    #[test]
    fn a_description_the_parser_would_not_read_back_is_refused() {
        let refused = |spec: NodeSpec| spec.into_node(Limits::DEFAULT).expect_err("refused").kind();
        assert_eq!(refused(spec("NA ME")), GedcomErrorKind::Syntax);
        assert_eq!(refused(spec("")), GedcomErrorKind::Syntax);
        assert_eq!(
            refused(NodeSpec::record("I1", "INDI")),
            GedcomErrorKind::Syntax
        );
        assert_eq!(
            refused(NodeSpec::record("@I 1@", "INDI")),
            GedcomErrorKind::Syntax
        );
        let mut nested = spec("INDI");
        nested.children.push(NodeSpec::record("@X1@", "NOTE"));
        assert_eq!(refused(nested), GedcomErrorKind::Syntax);
    }

    #[test]
    fn a_description_is_bounded() {
        let mut deep = spec("A");
        for _ in 0..10 {
            let mut parent = spec("A");
            parent.children.push(deep);
            deep = parent;
        }
        let shallow = Limits::DEFAULT.with_depth(5);
        let error = deep.into_node(shallow).expect_err("too deep");
        assert_eq!(error.kind(), GedcomErrorKind::Limit);
    }

    #[test]
    fn substructures_join_the_header_or_a_record_and_nothing_else_moves() {
        let input = "0 HEAD\n1 SOUR  ODD\n1 GEDC\n2 VERS 5.5.1\n0 @I1@ INDI\n1 NAME Ada /Example/\n0 TRLR\n";
        let mut document = Document::parse(input).expect("parses");
        document
            .append_structures("HEAD", &[], vec![Node::with_value("SUBM", "@U1@")])
            .expect("header");
        document
            .append_structures("@i1@", &[0], vec![Node::with_value("GIVN", "Ada")])
            .expect("record");
        assert_eq!(
            document.to_text(),
            "0 HEAD\n1 SOUR  ODD\n1 GEDC\n2 VERS 5.5.1\n1 SUBM @U1@\n0 @I1@ INDI\n1 NAME Ada /Example/\n2 GIVN Ada\n0 TRLR\n"
        );
        let refused = |result: Result<(), GedcomError>| result.expect_err("refused").kind();
        assert_eq!(
            refused(document.append_structures("@I9@", &[], vec![Node::new("NOTE")])),
            GedcomErrorKind::Structure
        );
        assert_eq!(
            refused(document.append_structures("@I1@", &[7], vec![Node::new("NOTE")])),
            GedcomErrorKind::Structure
        );
        assert_eq!(
            refused(document.append_structures("@I1@", &[], vec![Node::record("@N1@", "NOTE")])),
            GedcomErrorKind::Syntax
        );
        let spec = NodeSpec::record("@N1@", "NOTE");
        assert!(spec.into_substructure(Limits::DEFAULT).is_err());
    }

    #[test]
    fn records_go_before_the_trailer_all_or_none() {
        let mut document = Document::new_v551("TEST");
        document
            .append_records(vec![
                Node::record("@I1@", "INDI"),
                Node::record("@F1@", "FAM"),
            ])
            .expect("appended");
        let tags: Vec<&str> = document.records.iter().map(Node::tag).collect();
        assert_eq!(tags, ["HEAD", "INDI", "FAM", "TRLR"]);

        let before = document.clone();
        let repeated = document.append_records(vec![
            Node::record("@I2@", "INDI"),
            Node::record("@i1@", "INDI"),
        ]);
        assert_eq!(
            repeated.expect_err("a repeated identifier").kind(),
            GedcomErrorKind::Structure
        );
        let twice = document.append_records(vec![
            Node::record("@I3@", "INDI"),
            Node::record("@I3@", "INDI"),
        ]);
        assert!(twice.is_err());
        assert!(document.append_records(vec![Node::new("TRLR")]).is_err());
        assert_eq!(document, before, "a refused call adds nothing");
    }

    #[test]
    fn long_lines_are_wrapped_at_characters_not_beside_spaces() {
        let text = "Pointe-Claire, Île de Montréal, Québec ".repeat(12);
        let mut document = Document::new_v551("TEST");
        let record = Node::record("@N1@", "NOTE").child(Node::with_value("NOTE", text.trim_end()));
        document.append_records(vec![record]).expect("appended");
        let untouched = document.records[0].clone();

        let wrapped = document.wrap_long_lines(80).expect("wrapped");
        assert_eq!(
            wrapped,
            [WrappedLine {
                record: "@N1@".into(),
                path: vec![0],
                tag: "NOTE".into()
            }]
        );
        let written = document.to_text();
        for line in written.lines() {
            assert!(line.len() < 80, "{line:?}");
            assert!(!line.ends_with(' '), "{line:?}");
        }
        let reread = Document::parse(&written).expect("reads back");
        let note = reread
            .record("@N1@")
            .and_then(|note| note.first("NOTE"))
            .expect("note");
        assert_eq!(note.logical_value(), text.trim_end());
        assert_eq!(
            document.records[0], untouched,
            "the header fits and is not touched"
        );
    }

    #[test]
    fn a_long_continuation_line_is_wrapped_in_place() {
        let long = "word ".repeat(80);
        let logical = format!("short\n{}\nend", long.trim_end());
        let mut document = Document::new_v551("TEST");
        let mut note = Node::record("@N1@", "NOTE");
        note.set_logical_value(&logical);
        let note = note.child(Node::with_value("SOUR", "@S1@"));
        document.append_records(vec![note]).expect("appended");
        document.wrap_long_lines(255).expect("wrapped");
        let reread = Document::parse(&document.to_text()).expect("reads back");
        let note = reread.record("@N1@").expect("note");
        assert_eq!(note.logical_value(), logical);
        assert_eq!(note.children.last().map(Node::tag), Some("SOUR"));
        assert!(document.to_text().lines().all(|line| line.len() < 255));
    }

    #[test]
    fn a_file_that_fits_is_left_exactly_as_it_was() {
        let input = "0 HEAD\n1 GEDC\n2 VERS 5.5.1\n0  @I1@ INDI\n1 NAME Ada /Example/\n0 TRLR\n";
        let mut document = Document::parse(input).expect("parses");
        assert!(document.wrap_long_lines(255).expect("wrapped").is_empty());
        assert_eq!(document.to_text(), input);
    }

    #[test]
    fn version_seven_and_tiny_limits_are_refused() {
        let mut seven = Document::new_v7();
        assert_eq!(
            seven.wrap_long_lines(255).expect_err("7.0").kind(),
            GedcomErrorKind::Structure
        );
        let mut five = Document::new_v551("TEST");
        assert_eq!(
            five.wrap_long_lines(10).expect_err("tiny").kind(),
            GedcomErrorKind::Limit
        );
    }

    #[test]
    fn cuts_fall_on_character_boundaries() {
        let text = "ÅÅÅÅÅÅÅÅÅÅ";
        for piece in cut(text, 5, 5) {
            assert!(piece.len() <= 5);
        }
        assert_eq!(cut(text, 5, 5).concat(), text);
        assert_eq!(cut("a b", 1, 1), ["a", " ", "b"]);
        // Every boundary in `x x x` has a space beside it; the cut leaves the
        // space at the start of the next line, never at the end of this one.
        for piece in cut(&"x ".repeat(40), 9, 9).iter().rev().skip(1) {
            assert!(!piece.ends_with(' '), "{piece:?}");
        }
    }

    fn fits(node: &Node, max_line: usize) -> bool {
        Document {
            records: vec![node.clone()],
        }
        .to_text()
        .lines()
        .all(|line| line.len() < max_line)
    }

    #[test]
    fn fit_line_limit_splits_a_long_edited_ascii_payload() {
        let mut note = Node::record("@N1@", "NOTE");
        let text = "word ".repeat(80);
        note.set_logical_value(&text);
        assert!(note.verbatim().is_none(), "an edited node has no verbatim");

        assert!(note.fit_line_limit(0, MAX_LINE_LENGTH));
        assert_eq!(note.logical_value(), text, "fold(split(x)) == x");
        assert!(fits(&note, MAX_LINE_LENGTH));
        assert!(
            note.all("CONC").count() > 0,
            "the overflow became CONC children"
        );
        // A second pass has nothing left to do.
        assert!(!note.fit_line_limit(0, MAX_LINE_LENGTH));
    }

    #[test]
    fn fit_line_limit_splits_multibyte_text_on_character_boundaries() {
        let mut note = Node::record("@N1@", "NOTE");
        let text = "Pointe-Claire, Île de Montréal, Québec ".repeat(12);
        note.set_logical_value(text.trim_end());

        assert!(note.fit_line_limit(0, 80));
        assert_eq!(note.logical_value(), text.trim_end());
        assert!(fits(&note, 80));
        assert!(note.all("CONC").count() > 0);
    }

    #[test]
    fn fit_line_limit_handles_a_space_at_every_candidate_boundary() {
        let mut note = Node::record("@N1@", "NOTE");
        // Every legal cut point in `x x x ...` has a space on at least one
        // side of it, exercising the fallback in `best_cut`.
        let text = "x ".repeat(200);
        note.set_logical_value(text.trim_end());

        assert!(note.fit_line_limit(0, 40));
        assert_eq!(note.logical_value(), text.trim_end());
        assert!(fits(&note, 40));
    }

    #[test]
    fn fit_line_limit_splits_an_over_long_cont_line_in_place() {
        let mut note = Node::record("@N1@", "NOTE");
        let long_second_line = "b".repeat(80);
        let logical = format!("short first line\n{long_second_line}\nlast line");
        note.set_logical_value(&logical);
        note.push(Node::with_value("SOUR", "@S1@"));

        assert!(note.fit_line_limit(0, 40));
        assert_eq!(note.logical_value(), logical);
        assert!(fits(&note, 40));
        // The CONT run still comes before the untouched substructure that
        // followed it.
        assert_eq!(note.children.last().map(Node::tag), Some("SOUR"));
        let tags: Vec<&str> = note.children.iter().map(Node::tag).collect();
        assert_eq!(tags.last(), Some(&"SOUR"));
        assert_eq!(tags.iter().filter(|tag| **tag == "CONT").count(), 2);
        assert!(tags.contains(&"CONC"));
    }

    #[test]
    fn fit_line_limit_never_splits_a_pointer_payload() {
        let long_pointer = format!("@{}@", "I".repeat(300));
        let mut record = Node::record("@F1@", "FAM");
        record.push(Node::with_value("HUSB", long_pointer.clone()));

        let husb = record.first_mut("HUSB").expect("HUSB");
        assert!(husb.pointer().is_some());
        assert!(!husb.fit_line_limit(1, MAX_LINE_LENGTH));
        assert_eq!(husb.value(), Some(long_pointer.as_str()));
        assert!(husb.all("CONC").next().is_none());
    }

    #[test]
    fn fit_line_limit_never_touches_a_node_still_carrying_its_verbatim_line() {
        // The double space between the level and the xref is not what
        // canonical rendering would produce, so the parser keeps this
        // line's exact bytes — the mark of a node no caller has reached
        // into yet.
        let long = "y".repeat(300);
        let input = format!("0 HEAD\n0  @N1@ NOTE {long}\n0 TRLR\n");
        let mut document = Document::parse(&input).expect("parses");
        let note = document.record_mut("@N1@").expect("note");
        assert!(note.verbatim().is_some(), "kept because of the odd spacing");

        let before = note.clone();
        assert!(!note.fit_line_limit(0, MAX_LINE_LENGTH));
        assert_eq!(*note, before, "an untouched node is not rewritten");
        assert_eq!(document.to_text(), input);
    }

    #[test]
    fn fit_line_limit_recurses_past_an_untouched_verbatim_child() {
        // The record itself has no verbatim (it was appended fresh), but
        // its NOTE child is a kept verbatim line the caller never reached
        // into — that child must be left exactly as it was even though the
        // record around it is being fitted.
        let long = "z".repeat(300);
        let odd_note = format!("0  NOTE  {long}\n");
        let reparsed = Document::parse(&format!("0 HEAD\n{odd_note}0 TRLR\n"))
            .expect("parses")
            .records
            .remove(1);
        assert!(reparsed.verbatim().is_some());

        let mut record = Node::record("@I1@", "INDI");
        record.push(reparsed.clone());
        let mut edited_name = Node::with_value("NAME", "x".repeat(300));
        edited_name.set_logical_value(&"x".repeat(300));
        record.push(edited_name);

        assert!(record.fit_line_limit(0, MAX_LINE_LENGTH));
        assert_eq!(
            record.children[0], reparsed,
            "the verbatim child is untouched"
        );
        assert!(
            record.children[1].all("CONC").count() > 0,
            "the edited sibling was still fitted"
        );
    }

    #[test]
    fn fit_line_limit_covers_a_record_with_an_xref() {
        let mut record = Node::record("@I123456@", "INDI");
        record.push(Node::with_value("NOTE", "n".repeat(260)));

        assert!(record.fit_line_limit(0, MAX_LINE_LENGTH));
        assert!(fits(&record, MAX_LINE_LENGTH));
        let note = record.first("NOTE").expect("note");
        assert_eq!(note.logical_value(), "n".repeat(260));
    }

    #[test]
    fn document_fit_line_limit_reaches_one_record_by_xref() {
        let mut document = Document::new_v551("TEST");
        let mut note = Node::record("@N1@", "NOTE");
        note.set_logical_value(&"word ".repeat(80));
        document.append_records(vec![note]).expect("appended");

        assert!(
            document
                .fit_line_limit("@N1@", MAX_LINE_LENGTH)
                .expect("record exists")
        );
        assert!(
            document
                .to_text()
                .lines()
                .all(|line| line.len() < MAX_LINE_LENGTH)
        );

        let missing = document.fit_line_limit("@N9@", MAX_LINE_LENGTH);
        assert_eq!(
            missing.expect_err("no such record").kind(),
            GedcomErrorKind::Structure
        );
    }
}