rakata_formats/

gff_compare.rs

//! Comparing a GFF tree against the one it was derived from.
//!
//! A typed view reads a GFF, models some of it, and writes it back. Two
//! questions decide whether that was faithful, and neither can be answered by
//! looking at the view alone:
//!
//! - Did every field it rewrote keep the value the original had?
//! - Did it write a label the original never had?
//!
//! Both are pure tree work: which labels are present, and whether the values
//! under them match. Nothing here knows what a module or a creature is, which
//! is why it sits in this crate rather than above it.
//!
//! Both the test suite and `vanilla-inspector` use these. That is the point:
//! if the tool and the tests grew separate implementations, the tool's verdict
//! would quietly stop meaning what the tests' verdict means, which is the same
//! parallel-definition drift that has produced real defects here before.
//!
//! ## Why a nested struct's id is not compared
//!
//! Such a comparison has no subject. A nested struct is reached by label
//! through `CResGFF::GetStructFromStruct`, which builds its result from the
//! field's `data_or_data_offset`, the struct's *index* rather than its id,
//! and the whole class hands back a wrapper holding only that index. No caller
//! outside it ever holds a pointer it could read an id from. Of the class's
//! sixty-four methods exactly one reads a struct's `id`, and it is not on any
//! path that resolves a struct by label.
//!
//! So the value that comparison reported on cannot be read by the code that
//! reaches these structs, and every difference it found was about nothing.
//! Three sat in the output permanently, which trains a reader to skim a guard
//! that is right the rest of the time.
//!
//! A *list element's* id is a different question and a live one: several
//! loaders test it against a per-list constant and silently skip an element
//! that does not match. Nothing here covers that, deliberately -- pairing
//! elements between two trees is not a tree question, since the rewrite's
//! order is the view's. `vanilla-inspector`'s `validate struct-ids` compares
//! them against the schema and against both corpora instead.
//!
//! The closure is within `CResGFF`, which is the only GFF parser found across
//! the tracing done so far rather than one proven unique against the whole
//! binary. If a second reader exists, the exposure is writing `0` where
//! vanilla writes something and nothing reads it, which is the risk already
//! taken on `CameraList` and the two encounter-nested lists.
//!
//! ## What this does not decide
//!
//! Whether a difference is a defect. A view is a projection and is entitled to
//! drop fields, and a label written but absent from every file may be a field
//! the engine omits at its default rather than a wrong label. The caller
//! supplies that judgement; this module supplies the observation.

use std::collections::{BTreeMap, BTreeSet};

use crate::gff::{GffStruct, GffValue};
use crate::schema::{gff_value_type, GffType};
use rakata_core::StrRef;

/// One field whose value changed between the original and the rewrite.
#[derive(Debug, Clone, PartialEq)]
pub struct ValueDifference {
    /// Label the difference was found under. Nested fields report the label
    /// alone rather than a path, since GFF labels are the unit a reader looks
    /// a field up by.
    pub label: String,
    /// Value the original carried.
    pub before: GffValue,
    /// Value the rewrite carried.
    pub after: GffValue,
}

/// Reports every field the rewrite changed the value of.
///
/// Walks the rewritten tree and compares each field against the original's
/// field of the same label, recursing into nested structs. A label the
/// original does not carry is skipped here; that case is what [`LabelCensus`]
/// exists for.
///
/// Lists are skipped entirely. Element order in a rewrite is the view's, not
/// the file's, so a positional comparison reports differences that are not
/// defects. A caller that models a list's contents compares them directly.
pub fn value_differences(original: &GffStruct, rewritten: &GffStruct) -> Vec<ValueDifference> {
    let mut out = Vec::new();
    collect_differences(original, rewritten, &mut out);
    out
}

fn collect_differences(
    original: &GffStruct,
    rewritten: &GffStruct,
    out: &mut Vec<ValueDifference>,
) {
    for field in &rewritten.fields {
        let Some(before) = original.field(field.label.as_str()) else {
            continue;
        };
        match (before, &field.value) {
            (GffValue::List(_), _) | (_, GffValue::List(_)) => {}
            (GffValue::Struct(before_inner), GffValue::Struct(after_inner)) => {
                collect_differences(before_inner, after_inner, out);
            }
            _ if *before != field.value => out.push(ValueDifference {
                label: field.label.as_str().to_string(),
                before: before.clone(),
                after: field.value.clone(),
            }),
            _ => {}
        }
    }
}

/// Joins a parent path and a label into the dotted form the reports use.
/// Top-level fields are bare labels; list elements carry `[]` on the list.
fn child_path(parent: &str, label: &str) -> String {
    if parent.is_empty() {
        label.to_string()
    } else {
        format!("{parent}.{label}")
    }
}

/// Collects every field path in a struct tree, nested structs and lists
/// included.
///
/// Paths rather than bare labels, because a label alone cannot distinguish a
/// field the corpus holds at one level from the same label a view reads at
/// another. That difference is a defect neither a value comparison nor a
/// symmetry check can see, since a view reading the wrong parent finds
/// nothing there and writes nothing back, which is self-consistent.
fn collect_paths(structure: &GffStruct, parent: &str, out: &mut BTreeSet<String>) {
    for field in &structure.fields {
        let path = child_path(parent, field.label.as_str());
        out.insert(path.clone());
        match &field.value {
            GffValue::Struct(inner) => collect_paths(inner, &path, out),
            GffValue::List(elements) => {
                let element_path = format!("{path}[]");
                for element in elements {
                    collect_paths(element, &element_path, out);
                }
            }
            _ => {}
        }
    }
}

/// Collects every label in a struct tree alongside the types it was seen
/// carrying. A label may hold different types in different files, so this
/// accumulates a set rather than overwriting.
fn collect_typed_paths(
    structure: &GffStruct,
    parent: &str,
    out: &mut BTreeMap<String, (BTreeSet<GffType>, bool)>,
) {
    for field in &structure.fields {
        let path = child_path(parent, field.label.as_str());
        let entry = out.entry(path.clone()).or_default();
        entry.0.insert(gff_value_type(&field.value));
        entry.1 |= is_informative(&field.value);
        match &field.value {
            GffValue::Struct(inner) => collect_typed_paths(inner, &path, out),
            GffValue::List(elements) => {
                let element_path = format!("{path}[]");
                for element in elements {
                    collect_typed_paths(element, &element_path, out);
                }
            }
            _ => {}
        }
    }
}

/// The leaf label of a dotted path.
fn leaf_of(path: &str) -> &str {
    path.rsplit('.').next().unwrap_or(path)
}

/// Folds one file's labels into the running observation, counting each label
/// once per file rather than once per occurrence.
fn merge_observation(
    into: &mut BTreeMap<String, LabelObservation>,
    from: BTreeMap<String, (BTreeSet<GffType>, bool)>,
) {
    for (label, (types, informative)) in from {
        let entry = into.entry(label).or_default();
        entry.types.extend(types);
        entry.files += 1;
        if informative {
            entry.files_with_value += 1;
        }
    }
}

/// Which labels a view writes that no file was seen to contain, accumulated
/// over a corpus.
///
/// [`value_differences`] cannot see a label the original lacks: it walks the
/// rewrite and skips anything the original has no field for. That means a
/// label renamed on both the read and the write side passes it unremarked,
/// which is the self-consistent case a faithfulness check exists to catch.
/// Comparing what gets written against everything the corpus was ever seen to
/// contain is what closes that.
///
/// This has to accumulate across files rather than judge one at a time,
/// because any single file may legitimately omit a field another carries.
#[derive(Debug, Clone, Default)]
pub struct LabelCensus {
    written: BTreeSet<String>,
    seen: BTreeMap<String, LabelObservation>,
    files: usize,
}

/// One leaf label the view models at some of its corpus paths and not others.
///
/// Produced by [`LabelCensus::partially_modelled_leaves`].
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct LeafPathSplit<'a> {
    /// The label shared by every path below.
    pub leaf: &'a str,
    /// Paths the view reads and writes.
    pub modelled: Vec<&'a str>,
    /// Paths the corpus carries that the view does not, with what was seen at
    /// each, so the reader can weigh them without a second pass.
    pub unmodelled: Vec<(&'a str, &'a LabelObservation)>,
}

/// What a corpus was seen to carry under one label.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct LabelObservation {
    /// Types the label was seen holding. A label may hold different types in
    /// different files, so this is a set rather than one value.
    pub types: BTreeSet<GffType>,
    /// How many files carried the label.
    ///
    /// This is what turns a label list into a priority order. A label in
    /// every file and a label in one are very different propositions, and
    /// without the count they read identically.
    pub files: usize,
    /// How many files carried the label holding something other than its
    /// zero value.
    ///
    /// Prevalence alone misranks: a label present in every file and empty in
    /// all of them carries no information, while a label in a handful of
    /// files holding real values does. Ranking needs both.
    ///
    /// # This orders work; it does not decide what to model
    ///
    /// Neither this count nor the file count predicts whether a field is worth
    /// modelling, and both have been wrong in both directions. Only what the
    /// loader does with a field settles it; these counts are for deciding what
    /// to look at first. `docs/src/architecture.md` works through the three
    /// ways the counts mislead, with a real field behind each.
    pub files_with_value: usize,
}

/// Whether a value carries anything beyond the type's zero.
///
/// Deliberately shallow. This is a triage signal for deciding which labels
/// are worth investigating, not a claim about what the engine treats as
/// meaningful: a field's real default may be something other than zero, and
/// only an audit of the loader can say.
fn is_informative(value: &GffValue) -> bool {
    match value {
        GffValue::UInt8(v) => *v != 0,
        GffValue::Int8(v) => *v != 0,
        GffValue::UInt16(v) => *v != 0,
        GffValue::Int16(v) => *v != 0,
        GffValue::UInt32(v) => *v != 0,
        GffValue::Int32(v) => *v != 0,
        GffValue::UInt64(v) => *v != 0,
        GffValue::Int64(v) => *v != 0,
        GffValue::Single(v) => *v != 0.0,
        GffValue::Double(v) => *v != 0.0,
        GffValue::String(v) => !v.is_empty(),
        GffValue::ResRef(v) => !v.as_bytes().is_empty(),
        GffValue::LocalizedString(v) => {
            v.string_ref != StrRef::invalid() || !v.substrings.is_empty()
        }
        GffValue::Binary(v) => v.iter().any(|byte| *byte != 0),
        GffValue::Struct(v) => !v.fields.is_empty(),
        GffValue::List(v) => !v.is_empty(),
        GffValue::Vector3(v) => v.iter().any(|f| *f != 0.0),
        GffValue::Vector4(v) => v.iter().any(|f| *f != 0.0),
    }
}

/// A family of labels that differ only by letter case.
///
/// GFF label lookup is case-sensitive, so a view reading one spelling sees
/// nothing in a file that uses another. Vanilla does ship such families, and
/// the crate already carries a hand-written tolerant read for one of them, so
/// the question is how many more there are rather than whether any exist.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct CaseVariantGroup {
    /// Each spelling found in the corpus, with what was seen under it.
    pub spellings: Vec<(String, LabelObservation)>,
    /// The spellings the view writes. A family where this holds fewer than
    /// every spelling is one the view reads in only some of its forms.
    pub written: BTreeSet<String>,
}

/// Whether a corpus can decide the invented-label question at all.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum InventedLabels {
    /// The corpus held no files, so everything a view writes is trivially
    /// "absent from the corpus" and the question is meaningless.
    ///
    /// This is derived from the corpus rather than configured, so it stops
    /// being reported the moment a corpus with files is handed in, and it
    /// cannot go stale the way a caller-set flag would.
    Undecidable,
    /// Labels written that no file in the corpus contained.
    ///
    /// Not a defect list. A view may write a field the engine omits when it
    /// holds its default, and it may write a field belonging to a form the
    /// corpus does not include. Judging those is the caller's.
    Labels(Vec<String>),
}

impl LabelCensus {
    /// Creates an empty census.
    pub fn new() -> Self {
        Self::default()
    }

    /// Records one file's original tree and the tree a view rewrote from it.
    pub fn observe(&mut self, original: &GffStruct, rewritten: &GffStruct) {
        let mut in_this_file = BTreeMap::new();
        collect_typed_paths(original, "", &mut in_this_file);
        merge_observation(&mut self.seen, in_this_file);
        collect_paths(rewritten, "", &mut self.written);
        self.files += 1;
    }

    /// Number of files observed.
    pub fn files(&self) -> usize {
        self.files
    }

    /// Whether any file in the corpus carried this path.
    ///
    /// Separate from [`Self::invented`] because the two answer questions that
    /// diverge the moment a view stops writing something. `invented` is a
    /// property of the view and the corpus together, so a label the view no
    /// longer writes drops out of it, and reading that as "the corpus does not
    /// carry it" is backwards. This asks the corpus alone, which is the fact a
    /// decision to stop writing a label has to rest on and keep resting on.
    pub fn corpus_carries(&self, path: &str) -> bool {
        self.seen.contains_key(path)
    }

    /// Labels written that the corpus never contained, or
    /// [`InventedLabels::Undecidable`] when there was nothing to compare
    /// against.
    pub fn invented(&self) -> InventedLabels {
        if self.files == 0 {
            return InventedLabels::Undecidable;
        }
        InventedLabels::Labels(
            self.written
                .iter()
                .filter(|label| !self.seen.contains_key(*label))
                .cloned()
                .collect(),
        )
    }

    /// Families of labels in the corpus differing only by letter case.
    ///
    /// Returns only families with more than one spelling, since a lone
    /// spelling has nothing to disagree with. What makes a family worth
    /// attention is when [`CaseVariantGroup::written`] does not cover every
    /// spelling: the view then reads some files' copy of that field and not
    /// others'.
    pub fn case_variants(&self) -> Vec<CaseVariantGroup> {
        let mut families: BTreeMap<String, Vec<&String>> = BTreeMap::new();
        for label in self.seen.keys() {
            families
                .entry(label.to_lowercase())
                .or_default()
                .push(label);
        }

        families
            .into_values()
            .filter(|spellings| spellings.len() > 1)
            .map(|spellings| CaseVariantGroup {
                written: spellings
                    .iter()
                    .filter(|label| self.written.contains(**label))
                    .map(|label| (*label).clone())
                    .collect(),
                spellings: spellings
                    .into_iter()
                    .map(|label| {
                        (
                            label.clone(),
                            self.seen.get(label).cloned().unwrap_or_default(),
                        )
                    })
                    .collect(),
            })
            .collect()
    }

    /// Field paths whose leaf label appears in the corpus at one level and in
    /// the view's output at another.
    ///
    /// This is the wiring-mismatch check, and it exists because nothing else
    /// catches the shape. A view that reads a field off the wrong parent finds
    /// nothing there, so it writes nothing back: the round-trip is stable, the
    /// values that do coincide all match, and every field involved is
    /// modelled. It looks like a projection dropping a field it never wanted.
    ///
    /// Reported as `(leaf, path_in_corpus, path_written)`. A leaf appearing at
    /// several levels legitimately, which nested formats do, yields one entry
    /// per crossing pair and is for a reader to judge rather than a verdict.
    pub fn misplaced(&self) -> Vec<(&str, &str, &str)> {
        let mut out = Vec::new();
        for seen_path in self.seen.keys() {
            if self.written.contains(seen_path) {
                continue;
            }
            let leaf = leaf_of(seen_path);
            for written_path in &self.written {
                if written_path != seen_path
                    && leaf_of(written_path) == leaf
                    && !self.seen.contains_key(written_path)
                {
                    out.push((leaf, seen_path.as_str(), written_path.as_str()));
                }
            }
        }
        out
    }

    /// Leaf labels the corpus carries at several paths, where the view models
    /// some of those paths and not others.
    ///
    /// The blind spot this closes is a reviewer's, not a tool's. Scanning a
    /// list of unmodelled labels, a leaf that also appears somewhere modelled
    /// reads as covered: the eye matches the name, finds it in the view, and
    /// moves on. `OnHeartbeat` survived exactly that way, modelled on the ARE
    /// root and dropped inside every nested minigame `Scripts` struct, and the
    /// inventory that was supposed to surface it counted the root's and called
    /// the label done.
    ///
    /// Distinct from [`Self::misplaced`], which asks whether a path the view
    /// writes exists in any file. Here every path involved is real; the
    /// question is only whether the view covers all of them. A leaf covered at
    /// every path it appears at is not reported, and neither is one covered
    /// nowhere, since [`Self::unmodelled`] already lists that.
    ///
    /// A mixed result is not automatically a defect. Formats reuse labels at
    /// unrelated levels, and a projection may want one and not the other. It
    /// is a prompt to decide, with the paths side by side.
    pub fn partially_modelled_leaves(&self) -> Vec<LeafPathSplit<'_>> {
        let mut by_leaf: BTreeMap<&str, Vec<&String>> = BTreeMap::new();
        for path in self.seen.keys() {
            by_leaf.entry(leaf_of(path)).or_default().push(path);
        }

        by_leaf
            .into_iter()
            .filter_map(|(leaf, paths)| {
                let (modelled, unmodelled): (Vec<_>, Vec<_>) = paths
                    .into_iter()
                    .partition(|path| self.written.contains(*path));
                if modelled.is_empty() || unmodelled.is_empty() {
                    return None;
                }
                Some(LeafPathSplit {
                    leaf,
                    modelled: modelled.into_iter().map(String::as_str).collect(),
                    unmodelled: unmodelled
                        .into_iter()
                        .map(|path| (path.as_str(), &self.seen[path]))
                        .collect(),
                })
            })
            .collect()
    }

    /// Field paths the corpus contained that the view never writes, each with
    /// what was observed under it.
    ///
    /// Dropping a field is what a projection does, so this is a starting
    /// point for deciding what is worth modelling rather than a defect list.
    /// The types come along because they are what makes the follow-on
    /// modelling cheap: a label alone still needs looking up.
    pub fn unmodelled(&self) -> Vec<(&str, &LabelObservation)> {
        self.seen
            .iter()
            .filter(|(label, _)| !self.written.contains(*label))
            .map(|(label, observation)| (label.as_str(), observation))
            .collect()
    }
}

/// Whether one schema serves one reading of a file or two.
///
/// Decides how a corpus's silence about a label should be read, which is not
/// something the census can work out for itself and has now been gotten wrong
/// twice by callers deciding it inline.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum SchemaShape {
    /// One reader, so a label absent from every file is a fallback that runs
    /// on every file.
    ///
    /// UTE's runtime-tracking block is the case that pins this: twelve fields
    /// absent from all 133 vanilla `.ute` files, and live on all 133.
    SingleForm,
    /// Two readings picked at read time, with the corpora separating them.
    ///
    /// A label the corpus never carries belongs to the other reading, so its
    /// fallback is not one this corpus runs. GIT is the case: a static
    /// placement carries `TemplateResRef` and a saved snapshot does not, and
    /// scoring the label against saved objects rates it 100% absent over tens
    /// of thousands of objects that never ask for it.
    Union,
}

/// How often each path was absent, counted per occurrence rather than per
/// file.
///
/// [`LabelCensus`] counts a label once per file, which answers "does the
/// corpus carry this at all". It cannot answer how often a reader's absent
/// fallback runs, because a label inside a list is present on some elements
/// and absent on others and a file-level count collapses that to one bit. A
/// corpus of two hundred creatures where one omits `ScriptHeartbeat` and a
/// corpus where all two hundred omit it are the same file either way.
///
/// So the denominator here is the number of structs visited at the path's
/// parent: the number of times the reader ran at all. A field on a list
/// element gets one occasion per element.
///
/// Paths are label sequences with no list marker, so a schema entry looks up
/// directly by the path a walk builds for it. A list and a struct both become
/// the parent path of whatever hangs beneath them, which is the same nesting
/// [`Shape`](crate::schema::Shape) uses for a container's children.
#[derive(Debug, Clone, Default)]
pub struct AbsenceCensus {
    containers: BTreeMap<String, usize>,
    present: BTreeMap<String, usize>,
}

/// How often one path's reader fallback would fire across a corpus.
///
/// Produced by [`AbsenceCensus::rate`].
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct AbsenceRate {
    /// Structs visited at the path's parent: how many times a reader at this
    /// path would have run.
    pub occasions: usize,
    /// How many of those carried the label.
    pub present: usize,
}

impl AbsenceRate {
    /// Occasions where the label was missing and the fallback would fire.
    #[must_use]
    pub fn absent(&self) -> usize {
        self.occasions.saturating_sub(self.present)
    }

    /// Absent occasions as a fraction of all occasions, `0.0` when the path
    /// was never reached.
    #[must_use]
    #[allow(clippy::as_conversions)]
    // CLIPPY: usize -> f64 for a reporting ratio. A corpus large enough to
    // lose precision here would be several petabytes of GFF.
    pub fn fraction(&self) -> f64 {
        if self.occasions == 0 {
            return 0.0;
        }
        self.absent() as f64 / self.occasions as f64
    }
}

impl AbsenceCensus {
    /// An empty census.
    #[must_use]
    pub fn new() -> Self {
        Self::default()
    }

    /// Folds one file's tree into the running counts.
    pub fn observe(&mut self, root: &GffStruct) {
        self.visit(root, String::new());
    }

    fn visit(&mut self, structure: &GffStruct, path: String) {
        *self.containers.entry(path.clone()).or_default() += 1;
        for field in &structure.fields {
            let child = child_path(&path, field.label.as_str());
            *self.present.entry(child.clone()).or_default() += 1;
            match &field.value {
                GffValue::Struct(inner) => self.visit(inner, child),
                GffValue::List(elements) => {
                    for element in elements {
                        self.visit(element, child.clone());
                    }
                }
                _ => {}
            }
        }
    }

    /// How often `path` was absent, or `None` when the corpus never reached
    /// its parent.
    ///
    /// `None` is not the same as "always present" and not the same as "always
    /// absent". It means no file in the corpus held a struct this field could
    /// have appeared on, so the corpus says nothing about the field either
    /// way. Ranking that as a 0% firing rate would read as evidence the
    /// fallback never runs, which is exactly backwards.
    #[must_use]
    pub fn rate(&self, path: &[&str]) -> Option<AbsenceRate> {
        let (leaf, parents) = path.split_last()?;
        let parent_path = parents.join(".");
        let occasions = *self.containers.get(&parent_path)?;
        let full = child_path(&parent_path, leaf);
        Some(AbsenceRate {
            occasions,
            present: self.present.get(&full).copied().unwrap_or(0),
        })
    }

    /// How often `path`'s fallback fires in this corpus, or `None` when this
    /// corpus cannot speak to it.
    ///
    /// `rate` answers "how often was the label missing here", which is not the
    /// same question. A missing label only means a fallback ran if this
    /// corpus's reader was the one looking for it, and under
    /// [`SchemaShape::Union`] it may not have been. Callers deciding that
    /// inline have gotten it wrong in both directions:
    ///
    /// - Treating a union schema as single-form counts every static-form label
    ///   as firing across the entire saved corpus, which put six
    ///   `TemplateResRef` rows at the head of a ranking on numbers describing
    ///   a reader that never ran.
    /// - Treating a single-form schema as a union drops every field the corpus
    ///   universally omits, which is exactly the set whose fallback runs every
    ///   time and therefore matters most.
    ///
    /// So the shape is a parameter rather than a heuristic, and this is the
    /// only place the rule is written down.
    #[must_use]
    pub fn firing_rate(&self, path: &[&str], shape: SchemaShape) -> Option<AbsenceRate> {
        let rate = self.rate(path)?;
        match shape {
            SchemaShape::SingleForm => Some(rate),
            SchemaShape::Union if rate.present > 0 => Some(rate),
            SchemaShape::Union => None,
        }
    }

    /// How many structs the corpus held at `path`.
    ///
    /// The element count of a list, when `path` names one. Zero for a path the
    /// corpus never held.
    #[must_use]
    pub fn occurrences(&self, path: &[&str]) -> usize {
        self.containers.get(&path.join(".")).copied().unwrap_or(0)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::gff::GffLabel;
    use crate::gff_label;

    fn scalar(label: &'static str, value: u8) -> GffStruct {
        let mut s = GffStruct::new(0);
        s.push_field(GffLabel::from_static(label), GffValue::UInt8(value));
        s
    }

    #[test]
    fn a_changed_value_is_reported_under_its_label() {
        let differences = value_differences(&scalar("Tag", 1), &scalar("Tag", 2));

        assert_eq!(differences.len(), 1);
        assert_eq!(differences[0].label, "Tag");
        assert_eq!(differences[0].before, GffValue::UInt8(1));
        assert_eq!(differences[0].after, GffValue::UInt8(2));
    }

    #[test]
    fn an_unchanged_value_is_not_reported() {
        assert!(value_differences(&scalar("Tag", 1), &scalar("Tag", 1)).is_empty());
    }

    #[test]
    fn a_label_the_original_lacks_is_left_to_the_census() {
        // This is the blind spot that makes LabelCensus necessary: comparing
        // values alone cannot see a label that was invented.
        assert!(value_differences(&scalar("Tag", 1), &scalar("Taag", 1)).is_empty());
    }

    /// No comparison here sees a struct's own id, on a nested struct or a list
    /// element, and neither absence is an oversight. A nested struct's id is
    /// unreachable by the engine code that resolves one; a list element's is
    /// live and belongs to a schema comparison, since pairing elements between
    /// two trees is not a tree question. The module docs have both.
    #[test]
    fn a_struct_id_is_invisible_to_every_comparison_here() {
        let nested = |id| {
            let mut root = GffStruct::new(0);
            let mut inner = scalar("Deep", 1);
            inner.struct_id = id;
            root.push_field(gff_label!("Inner"), GffValue::Struct(Box::new(inner)));
            root
        };
        assert!(value_differences(&nested(14), &nested(0)).is_empty());

        let element = |id| {
            let mut root = GffStruct::new(0);
            let mut item = scalar("Deep", 1);
            item.struct_id = id;
            root.push_field(gff_label!("Items"), GffValue::List(vec![item]));
            root
        };
        assert!(value_differences(&element(6), &element(0)).is_empty());
    }

    #[test]
    fn nested_struct_fields_are_compared() {
        let nest = |value| {
            let mut root = GffStruct::new(0);
            root.push_field(
                gff_label!("Inner"),
                GffValue::Struct(Box::new(scalar("Deep", value))),
            );
            root
        };

        let differences = value_differences(&nest(1), &nest(2));

        assert_eq!(differences.len(), 1);
        assert_eq!(differences[0].label, "Deep");
    }

    #[test]
    fn lists_are_skipped_because_their_order_is_the_writers() {
        let list = |value| {
            let mut root = GffStruct::new(0);
            root.push_field(
                gff_label!("Items"),
                GffValue::List(vec![scalar("Id", value)]),
            );
            root
        };

        assert!(value_differences(&list(1), &list(2)).is_empty());
    }

    #[test]
    fn paths_reach_into_lists_and_structs() {
        let mut root = GffStruct::new(0);
        root.push_field(gff_label!("Items"), GffValue::List(vec![scalar("Id", 1)]));
        root.push_field(
            gff_label!("Inner"),
            GffValue::Struct(Box::new(scalar("Deep", 1))),
        );

        let mut census = LabelCensus::new();
        census.observe(&root, &GffStruct::new(0));

        let found: Vec<&str> = census.unmodelled().into_iter().map(|(p, _)| p).collect();
        // Paths, not bare labels: the level a field sits at is the whole
        // point, and `Id` alone would not say which list it came from.
        for path in ["Items", "Items[].Id", "Inner", "Inner.Deep"] {
            assert!(
                found.contains(&path),
                "{path} should be collected, got {found:?}"
            );
        }
    }

    #[test]
    fn an_invented_label_is_reported_once_a_corpus_exists() {
        let mut census = LabelCensus::new();
        census.observe(&scalar("Tag", 1), &scalar("Taag", 1));

        assert_eq!(census.files(), 1);
        assert_eq!(
            census.invented(),
            InventedLabels::Labels(vec!["Taag".to_string()])
        );
        let unmodelled = census.unmodelled();
        assert_eq!(unmodelled.len(), 1);
        assert_eq!(unmodelled[0].0, "Tag");
        assert!(unmodelled[0].1.types.contains(&GffType::UInt8));
        assert_eq!(unmodelled[0].1.files, 1);
        assert_eq!(unmodelled[0].1.files_with_value, 1);
    }

    #[test]
    fn an_empty_corpus_cannot_decide_the_question() {
        // Everything a view writes is trivially absent from no files at all,
        // so the answer is "cannot say" rather than "all of them".
        assert_eq!(LabelCensus::new().invented(), InventedLabels::Undecidable);
    }

    #[test]
    fn a_label_present_in_any_file_is_not_invented() {
        // One file omitting a field another carries must not condemn it,
        // which is why the census accumulates rather than judging per file.
        let mut census = LabelCensus::new();
        census.observe(&GffStruct::new(0), &scalar("Tag", 1));
        census.observe(&scalar("Tag", 1), &scalar("Tag", 1));

        assert_eq!(census.invented(), InventedLabels::Labels(Vec::new()));
    }
}

#[cfg(test)]
mod prevalence_tests {
    use super::*;
    use crate::gff_label;

    #[test]
    fn an_unmodelled_label_carries_how_many_files_had_it() {
        // A label in one file of a thousand and a label in all thousand read
        // identically without the count, and they are not the same finding.
        let mut census = LabelCensus::new();
        let mut common = GffStruct::new(0);
        common.push_field(gff_label!("Everywhere"), GffValue::UInt8(1));
        let mut rare = GffStruct::new(0);
        rare.push_field(gff_label!("Everywhere"), GffValue::UInt8(1));
        rare.push_field(gff_label!("Once"), GffValue::UInt8(1));

        census.observe(&common, &GffStruct::new(0));
        census.observe(&common, &GffStruct::new(0));
        census.observe(&rare, &GffStruct::new(0));

        let counts: BTreeMap<&str, usize> = census
            .unmodelled()
            .into_iter()
            .map(|(label, observation)| (label, observation.files))
            .collect();

        assert_eq!(counts.get("Everywhere"), Some(&3));
        assert_eq!(counts.get("Once"), Some(&1));
    }
}

#[cfg(test)]
mod wiring_tests {
    use super::*;
    use crate::gff::GffLabel;
    use crate::gff_label;

    fn nested(parent: &'static str, child: &'static str) -> GffStruct {
        let mut inner = GffStruct::new(0);
        inner.push_field(GffLabel::from_static(child), GffValue::UInt8(1));
        let mut root = GffStruct::new(0);
        root.push_field(
            GffLabel::from_static(parent),
            GffValue::Struct(Box::new(inner)),
        );
        root
    }

    #[test]
    fn a_field_read_off_the_wrong_parent_is_reported_as_misplaced() {
        // The shape no other check sees. The corpus holds Thing at
        // Game.Thing; the view looks under Game.Player and so writes
        // Game.Player.Thing. Values never coincide, the round-trip is
        // stable, and both labels are modelled.
        let mut original = GffStruct::new(0);
        let mut game = GffStruct::new(0);
        game.push_field(gff_label!("Thing"), GffValue::UInt8(7));
        original.push_field(gff_label!("Game"), GffValue::Struct(Box::new(game)));

        let mut rewritten = GffStruct::new(0);
        let mut game_out = GffStruct::new(0);
        let mut player = GffStruct::new(0);
        player.push_field(gff_label!("Thing"), GffValue::UInt8(7));
        game_out.push_field(gff_label!("Player"), GffValue::Struct(Box::new(player)));
        rewritten.push_field(gff_label!("Game"), GffValue::Struct(Box::new(game_out)));

        assert!(
            value_differences(&original, &rewritten).is_empty(),
            "a value comparison cannot see this, which is why the check exists"
        );

        let mut census = LabelCensus::new();
        census.observe(&original, &rewritten);

        assert_eq!(
            census.misplaced(),
            vec![("Thing", "Game.Thing", "Game.Player.Thing")]
        );
    }

    #[test]
    fn a_leaf_modelled_at_one_path_and_dropped_at_another_is_reported() {
        // The `OnHeartbeat` shape. The corpus holds the label twice: once at
        // the root, which the view models, and once nested, which it drops.
        // Nothing else flags it. The nested path is in `unmodelled`, but a
        // reviewer reading that list finds the label in the view, matches on
        // the name and moves on, which is how the real one survived a scan
        // built to catch it.
        let mut original = GffStruct::new(0);
        original.push_field(gff_label!("OnHeartbeat"), GffValue::UInt8(1));
        let mut scripts = GffStruct::new(0);
        scripts.push_field(gff_label!("OnHeartbeat"), GffValue::UInt8(2));
        original.push_field(gff_label!("Scripts"), GffValue::Struct(Box::new(scripts)));

        // The view writes only the root one.
        let mut rewritten = GffStruct::new(0);
        rewritten.push_field(gff_label!("OnHeartbeat"), GffValue::UInt8(1));

        let mut census = LabelCensus::new();
        census.observe(&original, &rewritten);

        assert!(
            census.misplaced().is_empty(),
            "both paths are real, so this is not a wiring mismatch"
        );

        let split = census.partially_modelled_leaves();
        assert_eq!(split.len(), 1);
        assert_eq!(split[0].leaf, "OnHeartbeat");
        assert_eq!(split[0].modelled, vec!["OnHeartbeat"]);
        assert_eq!(
            split[0]
                .unmodelled
                .iter()
                .map(|(path, _)| *path)
                .collect::<Vec<_>>(),
            vec!["Scripts.OnHeartbeat"]
        );
    }

    #[test]
    fn a_leaf_covered_at_every_path_it_appears_at_is_not_reported() {
        let mut structure = GffStruct::new(0);
        structure.push_field(gff_label!("OnHeartbeat"), GffValue::UInt8(1));
        let mut scripts = GffStruct::new(0);
        scripts.push_field(gff_label!("OnHeartbeat"), GffValue::UInt8(2));
        structure.push_field(gff_label!("Scripts"), GffValue::Struct(Box::new(scripts)));

        let mut census = LabelCensus::new();
        census.observe(&structure, &structure);
        assert!(census.partially_modelled_leaves().is_empty());
    }

    #[test]
    fn a_leaf_covered_nowhere_is_left_to_the_unmodelled_list() {
        // Reporting it here too would duplicate `unmodelled` and bury the
        // mixed cases this query exists for.
        let structure = nested("Game", "Thing");
        let mut census = LabelCensus::new();
        census.observe(&structure, &GffStruct::new(0));

        assert!(census.partially_modelled_leaves().is_empty());
        assert_eq!(census.unmodelled().len(), 2);
    }

    #[test]
    fn a_field_at_the_same_path_is_not_misplaced() {
        let structure = nested("Game", "Thing");
        let mut census = LabelCensus::new();
        census.observe(&structure, &structure);

        assert!(census.misplaced().is_empty());
        assert!(matches!(
            census.invented(),
            InventedLabels::Labels(ref labels) if labels.is_empty()
        ));
    }

    #[test]
    fn paths_rather_than_labels_are_reported() {
        let structure = nested("Game", "Thing");
        let mut census = LabelCensus::new();
        census.observe(&structure, &GffStruct::new(0));

        let paths: Vec<&str> = census.unmodelled().into_iter().map(|(p, _)| p).collect();
        assert!(paths.contains(&"Game.Thing"), "got {paths:?}");
    }
}

#[cfg(test)]
mod absence_tests {
    use super::*;
    use crate::gff_label;

    /// One list of creatures, two of which carry `Tag` and one of which does
    /// not, inside a root that also carries a top-level `Flag`.
    fn creature_list() -> GffStruct {
        let mut tagged = GffStruct::new(0);
        tagged.push_field(gff_label!("Tag"), GffValue::UInt8(1));
        let untagged = GffStruct::new(0);

        let mut root = GffStruct::new(0);
        root.push_field(gff_label!("Flag"), GffValue::UInt8(1));
        root.push_field(
            gff_label!("Creature List"),
            GffValue::List(vec![tagged.clone(), tagged, untagged]),
        );
        root
    }

    #[test]
    fn a_list_field_gets_one_occasion_per_element() {
        let mut census = AbsenceCensus::new();
        census.observe(&creature_list());

        let rate = census
            .rate(&["Creature List", "Tag"])
            .expect("the list was observed");
        assert_eq!(rate.occasions, 3);
        assert_eq!(rate.present, 2);
        assert_eq!(rate.absent(), 1);
    }

    #[test]
    fn a_top_level_field_gets_one_occasion_per_file() {
        let mut census = AbsenceCensus::new();
        census.observe(&creature_list());
        census.observe(&GffStruct::new(0));

        let rate = census.rate(&["Flag"]).expect("the root was observed");
        assert_eq!(rate.occasions, 2);
        assert_eq!(rate.absent(), 1);
    }

    #[test]
    fn a_path_the_corpus_never_reached_is_none_rather_than_zero() {
        // The distinction the whole type exists for: reporting this as a 0%
        // firing rate would read as "the fallback never runs" when the truth
        // is that nothing was ever checked.
        let mut census = AbsenceCensus::new();
        census.observe(&GffStruct::new(0));

        assert!(census.rate(&["Creature List", "Tag"]).is_none());
        assert_eq!(census.rate(&["Flag"]).expect("root observed").absent(), 1);
    }

    #[test]
    fn occurrences_counts_list_elements() {
        let mut census = AbsenceCensus::new();
        census.observe(&creature_list());
        census.observe(&creature_list());

        assert_eq!(census.occurrences(&["Creature List"]), 6);
        assert_eq!(census.occurrences(&["Encounter List"]), 0);
    }

    #[test]
    fn a_union_corpus_that_never_carries_a_label_is_not_asked_about_it() {
        // The saved side of a GIT: the parent is reached on every element and
        // the label belongs to the other reading.
        let mut census = AbsenceCensus::new();
        census.observe(&creature_list());

        let path = &["Creature List", "TemplateResRef"];
        assert_eq!(census.rate(path).expect("parent reached").absent(), 3);
        assert!(census.firing_rate(path, SchemaShape::Union).is_none());
    }

    #[test]
    fn a_single_form_corpus_that_never_carries_a_label_fires_on_all_of_it() {
        // The opposite reading of the same measurement, and the one that
        // matters most: a field absent from every file is a fallback running
        // every time.
        let mut census = AbsenceCensus::new();
        census.observe(&creature_list());

        let path = &["Creature List", "TemplateResRef"];
        let rate = census
            .firing_rate(path, SchemaShape::SingleForm)
            .expect("a single-form schema reads absence as firing");
        assert_eq!(rate.absent(), 3);
    }

    #[test]
    fn a_label_the_union_corpus_does_carry_is_still_ranked() {
        let mut census = AbsenceCensus::new();
        census.observe(&creature_list());

        let rate = census
            .firing_rate(&["Creature List", "Tag"], SchemaShape::Union)
            .expect("the corpus carries Tag on two of three elements");
        assert_eq!(rate.absent(), 1);
    }

    #[test]
    fn a_struct_field_is_the_parent_of_what_hangs_under_it() {
        let mut inner = GffStruct::new(0);
        inner.push_field(gff_label!("Deep"), GffValue::UInt8(1));
        let mut root = GffStruct::new(0);
        root.push_field(gff_label!("Inner"), GffValue::Struct(Box::new(inner)));

        let mut census = AbsenceCensus::new();
        census.observe(&root);

        let rate = census
            .rate(&["Inner", "Deep"])
            .expect("the struct was observed");
        assert_eq!(rate.occasions, 1);
        assert_eq!(rate.present, 1);
    }
}