tilewright_diff/
compare.rs

1// Copyright 2026 Seraphina Studios
2// SPDX-License-Identifier: MIT
3
4//! Comparing two snapshots: removed, added and renamed IDs, and which
5//! removals an allowlist accepts (`docs/spec/DIFF.md`).
6
7use crate::{
8    Added, Allowance, Allowlist, Basis, Kind, Reason, Removed, Renamed, Report, Snapshot, Unused,
9    allow::Intent, snapshot::Fingerprint,
10};
11use std::collections::BTreeMap;
12
13/// The order kinds are paired in: planes first, so that zones, anchors and
14/// stairwells of a renamed plane pair with those of its new ID.
15const PAIRING_ORDER: [Kind; 7] = [
16    Kind::Plane,
17    Kind::Anchor,
18    Kind::Definition,
19    Kind::Object,
20    Kind::RenderLayer,
21    Kind::Stairwell,
22    Kind::Zone,
23];
24
25/// Removed and added IDs, grouped by scope and content.
26type Groups<'a> = BTreeMap<(&'a str, &'a Fingerprint), (Vec<&'a str>, Vec<&'a str>)>;
27
28/// Compares two snapshots. Every list in the report is sorted, so the same
29/// snapshots and allowlist always give the same report.
30#[must_use]
31pub fn diff(old: &Snapshot, new: &Snapshot, allowlist: &Allowlist) -> Report {
32    let mut removed = Vec::new();
33    let mut renamed = Vec::new();
34    let mut added = Vec::new();
35    // Each renamed plane's new ID, by its old ID.
36    let mut planes: BTreeMap<&str, &str> = BTreeMap::new();
37    for kind in PAIRING_ORDER {
38        let mut gone: BTreeMap<&str, &Fingerprint> = old
39            .entries(kind)
40            .filter(|(id, _)| !new.contains(kind, id))
41            .collect();
42        let mut fresh: BTreeMap<&str, &Fingerprint> = new
43            .entries(kind)
44            .filter(|(id, _)| !old.contains(kind, id))
45            .collect();
46        let mut pairs = Vec::new();
47        // A declared rename pairs its IDs whenever the new one exists.
48        for from in gone.keys() {
49            if let Some(Intent::Rename(to)) = allowlist.get(kind, from)
50                && new.contains(kind, to)
51            {
52                pairs.push((*from, to, Basis::Declared));
53            }
54        }
55        for (from, to, _) in &pairs {
56            gone.remove(from);
57            fresh.remove(to);
58        }
59        // Otherwise, a removed and an added ID pair when they are the only
60        // two with the same scope and content, for kinds that pair so.
61        if kind.pairs_by_content() {
62            for (from, to) in content_pairs(kind, &gone, &fresh, &planes) {
63                gone.remove(from);
64                fresh.remove(to);
65                pairs.push((from, to, Basis::Content));
66            }
67        }
68        if kind == Kind::Plane {
69            planes = pairs.iter().map(|(from, to, _)| (*from, *to)).collect();
70        }
71        removed.extend(gone.into_keys().map(|id| Removed {
72            kind,
73            id: id.to_owned(),
74            allowed: allowed(kind, id, allowlist, old, new),
75        }));
76        renamed.extend(pairs.into_iter().map(|(from, to, basis)| Renamed {
77            kind,
78            from: from.to_owned(),
79            to: to.to_owned(),
80            basis,
81            allowed: allowed(kind, from, allowlist, old, new),
82        }));
83        added.extend(fresh.into_keys().map(|id| Added {
84            kind,
85            id: id.to_owned(),
86        }));
87    }
88    removed.sort();
89    renamed.sort();
90    added.sort();
91    let unused = allowlist
92        .allowances()
93        .filter_map(|allowance| {
94            let kind = allowance.kind();
95            let reason =
96                if !old.contains(kind, allowance.id()) || new.contains(kind, allowance.id()) {
97                    Reason::NotRemoved
98                } else {
99                    match &allowance {
100                        Allowance::Rename { to, .. } if !new.contains(kind, to) => {
101                            Reason::TargetMissing
102                        }
103                        _ => return None,
104                    }
105                };
106            Some(Unused { allowance, reason })
107        })
108        .collect();
109    Report {
110        old: old.side().clone(),
111        new: new.side().clone(),
112        removed,
113        renamed,
114        added,
115        unused,
116    }
117}
118
119/// The removed and added IDs of `kind` that are the only two with their
120/// scope and content. `planes` maps renamed planes to their new IDs, so the
121/// IDs of a renamed plane are in its new plane.
122fn content_pairs<'a>(
123    kind: Kind,
124    gone: &BTreeMap<&'a str, &'a Fingerprint>,
125    fresh: &BTreeMap<&'a str, &'a Fingerprint>,
126    planes: &BTreeMap<&'a str, &'a str>,
127) -> Vec<(&'a str, &'a str)> {
128    let mut groups = Groups::new();
129    for (id, fingerprint) in gone {
130        let scope = kind.scope(id);
131        let scope = if kind.in_plane() {
132            planes.get(scope).copied().unwrap_or(scope)
133        } else {
134            scope
135        };
136        groups.entry((scope, fingerprint)).or_default().0.push(id);
137    }
138    for (id, fingerprint) in fresh {
139        groups
140            .entry((kind.scope(id), fingerprint))
141            .or_default()
142            .1
143            .push(id);
144    }
145    groups
146        .into_values()
147        .filter_map(|group| match group {
148            (from, to) if from.len() == 1 && to.len() == 1 => Some((from[0], to[0])),
149            _ => None,
150        })
151        .collect()
152}
153
154/// Whether the allowlist accepts the removal of `id`: an entry removes it,
155/// or renames it to an ID of the new world; or, for a zone, anchor or
156/// stairwell of a removed plane, the plane's entry removes the plane, or
157/// renames it to a plane of the new world that has the same local ID; or,
158/// for an object uid whose object was on a removed plane, the plane's entry
159/// removes the plane.
160fn allowed(kind: Kind, id: &str, allowlist: &Allowlist, old: &Snapshot, new: &Snapshot) -> bool {
161    match allowlist.get(kind, id) {
162        Some(Intent::Remove) => return true,
163        Some(Intent::Rename(to)) if new.contains(kind, to) => return true,
164        _ => {}
165    }
166    if kind == Kind::Object {
167        // A uid is the world's, not its plane's, so a renamed plane keeps
168        // its objects' uids and accepts no removal of one.
169        return old.object_plane(id).is_some_and(|plane| {
170            !new.contains(Kind::Plane, plane)
171                && matches!(allowlist.get(Kind::Plane, plane), Some(Intent::Remove))
172        });
173    }
174    let Some((plane, local)) = id.split_once('/').filter(|_| kind.in_plane()) else {
175        return false;
176    };
177    if new.contains(Kind::Plane, plane) {
178        return false;
179    }
180    match allowlist.get(Kind::Plane, plane) {
181        Some(Intent::Remove) => true,
182        Some(Intent::Rename(to)) => {
183            new.contains(Kind::Plane, to) && new.contains(kind, &format!("{to}/{local}"))
184        }
185        None => false,
186    }
187}
tilewright_diff/compare.rs

tilewright_diff/
compare.rs
