tilewright_diff/
snapshot.rs

1// Copyright 2026 Seraphina Studios
2// SPDX-License-Identifier: MIT
3
4//! What a comparison reads of one world: every ID, with a fingerprint of the
5//! content that the rename rule of `docs/spec/DIFF.md` compares.
6
7use crate::{Error, Kind, Limits, is_identifier};
8use sha2::{Digest, Sha256};
9use std::{
10    collections::{BTreeMap, BTreeSet},
11    fmt::Write as _,
12    ops::Bound,
13};
14use tilewright_jsonc::{Document, Limits as ParseLimits, write_json_string};
15use tilewright_pack::{Identity, Pack};
16use tilewright_source::World;
17
18/// SHA-256 of the content an ID's rename rule compares.
19pub(crate) type Fingerprint = [u8; 32];
20
21/// What a side of a comparison was read from.
22#[derive(Clone, Copy, Debug, Eq, PartialEq)]
23pub enum Input {
24    Source,
25    Pack,
26}
27
28impl Input {
29    #[must_use]
30    pub const fn as_str(self) -> &'static str {
31        match self {
32            Self::Source => "source",
33            Self::Pack => "pack",
34        }
35    }
36}
37
38/// Where a snapshot came from.
39#[derive(Clone, Debug, Eq, PartialEq)]
40pub struct Side {
41    pub input: Input,
42    /// The profile's `id`.
43    pub profile: String,
44    /// The profile's `version`.
45    pub profile_version: String,
46    /// Lowercase hex SHA-256 over the source files, as `docs/spec/PACK.md`
47    /// defines it, so a source tree and the pack compiled from it agree.
48    pub source_digest: String,
49}
50
51/// The IDs of one world, each with a fingerprint of its content.
52#[derive(Clone, Debug, Eq, PartialEq)]
53pub struct Snapshot {
54    pub(crate) side: Side,
55    pub(crate) ids: BTreeMap<Kind, BTreeMap<String, Fingerprint>>,
56    /// The plane each object uid's object is on, so that removing a plane
57    /// can accept the removal of its objects' uids.
58    pub(crate) object_planes: BTreeMap<String, String>,
59}
60
61impl Snapshot {
62    /// The snapshot of a loaded source tree. The world is already in
63    /// memory, so `limits` bound the snapshot built from it.
64    ///
65    /// # Errors
66    /// Returns [`Error::TooManyIds`] if the world has more IDs than
67    /// `limits` allow, or [`Error::Invalid`] if a document of the world
68    /// cannot be read again, which a world that loaded never has.
69    pub fn from_world(world: &World, limits: &Limits) -> Result<Self, Error> {
70        let profile = world.profile();
71        let mut builder = Builder::new(*limits);
72        let mut read = || -> Result<(), String> {
73            for (position, name) in profile.render_layers.iter().enumerate() {
74                builder.render_layer(name, position)?;
75            }
76            for (id, plane) in world.planes() {
77                builder.plane(id, &plane.canonical)?;
78                for (zone, entry) in &plane.zones {
79                    builder.zone(id, zone, &entry.canonical)?;
80                }
81                for (anchor, entry) in &plane.anchors {
82                    builder.anchor(id, anchor, entry.layer, entry.at)?;
83                }
84                for (stairwell, entry) in &plane.stairwells {
85                    builder.stairwell(id, stairwell, &entry.canonical)?;
86                }
87                for (layer, cx, cy) in plane.chunks.keys() {
88                    builder.chunk(id, *layer, *cx, *cy)?;
89                }
90            }
91            for (uid, location) in world.object_uids() {
92                builder.object(uid, &location.plane)?;
93            }
94            for ((kind, id), definition) in world.definitions() {
95                builder.definition(kind, id, &definition.canonical)?;
96            }
97            Ok(())
98        };
99        let read = read();
100        builder.check()?;
101        read.map_err(Error::Invalid)?;
102        Ok(builder.finish(Side {
103            input: Input::Source,
104            profile: profile.id.clone(),
105            profile_version: profile.version.clone(),
106            source_digest: hex(&world.source_digest()),
107        }))
108    }
109
110    /// The snapshot of a content pack. The pack is fully verified first,
111    /// as [`Pack::verify`] does, and its IDs are then read through
112    /// [`Pack::visit_identities`] one row at a time; reading stops as soon
113    /// as the pack has more IDs than `limits` allow.
114    ///
115    /// # Errors
116    /// Returns [`Error::TooManyIds`] past the limit, or [`Error::Pack`] if
117    /// the pack does not verify or SQLite fails.
118    pub fn from_pack(pack: &Pack, limits: &Limits) -> Result<Self, Error> {
119        let mut builder = Builder::new(*limits);
120        // The visit checks the stored profile before anything else, and
121        // with it the profile ID and version read below.
122        let read = pack.visit_identities(&mut |identity| {
123            match identity {
124                Identity::RenderLayer { name, position } => builder.render_layer(name, position),
125                Identity::Plane { id, document } => builder.plane(id, document),
126                Identity::Zone {
127                    plane,
128                    id,
129                    document,
130                } => builder.zone(plane, id, document),
131                Identity::Anchor {
132                    plane,
133                    id,
134                    layer,
135                    at,
136                } => builder.anchor(plane, id, layer, at),
137                Identity::Stairwell {
138                    plane,
139                    id,
140                    document,
141                } => builder.stairwell(plane, id, document),
142                Identity::Definition { kind, id, document } => {
143                    builder.definition(kind, id, document)
144                }
145                Identity::Chunk {
146                    plane,
147                    layer,
148                    cx,
149                    cy,
150                } => builder.chunk(plane, layer, cx, cy),
151                Identity::Object { uid, plane, .. } => builder.object(uid, plane),
152            }
153            .map_err(tilewright_pack::Error::Invalid)
154        });
155        builder.check()?;
156        read.map_err(Error::Pack)?;
157        let meta = |key: &str| -> Result<String, Error> {
158            pack.meta(key).map_err(Error::Pack)?.ok_or_else(|| {
159                Error::Pack(tilewright_pack::Error::Invalid(format!(
160                    "the pack has no {key}"
161                )))
162            })
163        };
164        Ok(builder.finish(Side {
165            input: Input::Pack,
166            profile: meta("profile_id")?,
167            profile_version: meta("profile_version")?,
168            source_digest: meta("source_digest")?,
169        }))
170    }
171
172    /// Where the snapshot came from.
173    #[must_use]
174    pub const fn side(&self) -> &Side {
175        &self.side
176    }
177
178    /// Whether the world has ID `id` of `kind`.
179    #[must_use]
180    pub fn contains(&self, kind: Kind, id: &str) -> bool {
181        self.ids.get(&kind).is_some_and(|ids| ids.contains_key(id))
182    }
183
184    /// The plane the object with `uid` is on.
185    #[must_use]
186    pub fn object_plane(&self, uid: &str) -> Option<&str> {
187        self.object_planes.get(uid).map(String::as_str)
188    }
189
190    /// The IDs of `kind`, in byte order.
191    pub fn ids(&self, kind: Kind) -> impl Iterator<Item = &str> {
192        self.ids
193            .get(&kind)
194            .into_iter()
195            .flat_map(|ids| ids.keys().map(String::as_str))
196    }
197
198    /// The IDs of `kind` with their fingerprints, in byte order.
199    pub(crate) fn entries(&self, kind: Kind) -> impl Iterator<Item = (&str, &Fingerprint)> {
200        self.ids.get(&kind).into_iter().flat_map(|ids| {
201            ids.iter()
202                .map(|(id, fingerprint)| (id.as_str(), fingerprint))
203        })
204    }
205}
206
207/// Collects a snapshot. A plane's fingerprint covers its zones, anchors and
208/// stairwells, so it is finished once everything has been read.
209struct Builder {
210    ids: BTreeMap<Kind, BTreeMap<String, Fingerprint>>,
211    /// Each plane's document fingerprint and a hash of its chunk addresses,
212    /// fed in `(layer, cx, cy)` order.
213    planes: BTreeMap<String, (Fingerprint, Sha256)>,
214    /// The plane of each object uid.
215    object_planes: BTreeMap<String, String>,
216    /// The most IDs the snapshot may hold, and how many it holds.
217    maximum: usize,
218    count: usize,
219}
220
221impl Builder {
222    const fn new(limits: Limits) -> Self {
223        Self {
224            ids: BTreeMap::new(),
225            planes: BTreeMap::new(),
226            object_planes: BTreeMap::new(),
227            maximum: limits.maximum_ids,
228            count: 0,
229        }
230    }
231
232    /// Counts one more ID before anything of it is kept, failing once the
233    /// count passes the limit.
234    fn admit(&mut self) -> Result<(), String> {
235        self.count = self.count.saturating_add(1);
236        if self.count > self.maximum {
237            return Err(format!("more than {} IDs", self.maximum));
238        }
239        Ok(())
240    }
241
242    /// [`Error::TooManyIds`] if reading stopped at the limit.
243    const fn check(&self) -> Result<(), Error> {
244        if self.count > self.maximum {
245            Err(Error::TooManyIds(self.maximum))
246        } else {
247            Ok(())
248        }
249    }
250
251    fn insert(&mut self, kind: Kind, id: String, fingerprint: Fingerprint) -> Result<(), String> {
252        let ids = self.ids.entry(kind).or_default();
253        if ids.contains_key(&id) {
254            return Err(format!("{kind} {id} is listed twice"));
255        }
256        ids.insert(id, fingerprint);
257        Ok(())
258    }
259
260    /// A render layer stands in for its content with its position in the
261    /// profile's list.
262    fn render_layer(&mut self, name: &str, position: usize) -> Result<(), String> {
263        self.admit()?;
264        if !is_identifier(name) {
265            return Err("a render layer is not an identifier".into());
266        }
267        let fingerprint = Sha256::digest(position.to_string()).into();
268        self.insert(Kind::RenderLayer, name.to_owned(), fingerprint)
269    }
270
271    fn plane(&mut self, id: &str, document: &str) -> Result<(), String> {
272        self.admit()?;
273        let fingerprint = document_fingerprint(document, &["id", "title"])?;
274        if self
275            .planes
276            .insert(id.to_owned(), (fingerprint, Sha256::new()))
277            .is_some()
278        {
279            return Err(format!("plane {id} is listed twice"));
280        }
281        Ok(())
282    }
283
284    fn zone(&mut self, plane: &str, id: &str, document: &str) -> Result<(), String> {
285        self.admit()?;
286        let fingerprint = document_fingerprint(document, &["id", "name"])?;
287        self.insert(Kind::Zone, format!("{plane}/{id}"), fingerprint)
288    }
289
290    fn anchor(&mut self, plane: &str, id: &str, layer: i32, at: [i64; 2]) -> Result<(), String> {
291        self.admit()?;
292        let content = format!("{{\"layer\":{layer},\"at\":[{},{}]}}", at[0], at[1]);
293        self.insert(
294            Kind::Anchor,
295            format!("{plane}/{id}"),
296            Sha256::digest(content).into(),
297        )
298    }
299
300    fn stairwell(&mut self, plane: &str, id: &str, document: &str) -> Result<(), String> {
301        self.admit()?;
302        let fingerprint = document_fingerprint(document, &["id"])?;
303        self.insert(Kind::Stairwell, format!("{plane}/{id}"), fingerprint)
304    }
305
306    fn definition(&mut self, kind: &str, id: &str, document: &str) -> Result<(), String> {
307        self.admit()?;
308        let fingerprint = document_fingerprint(document, &["id"])?;
309        self.insert(Kind::Definition, format!("{kind}/{id}"), fingerprint)
310    }
311
312    /// Object uids are never paired by content (see [`Kind::pairs_by_content`]),
313    /// so an object's fingerprint is the same for every object. Its plane is
314    /// kept, so that removing the plane can accept the removal of its uid.
315    fn object(&mut self, uid: &str, plane: &str) -> Result<(), String> {
316        self.admit()?;
317        if !is_identifier(uid) || !is_identifier(plane) {
318            return Err("an object uid or its plane is not an identifier".into());
319        }
320        self.insert(Kind::Object, uid.to_owned(), [0; 32])?;
321        self.object_planes.insert(uid.to_owned(), plane.to_owned());
322        Ok(())
323    }
324
325    fn chunk(&mut self, plane: &str, layer: i32, cx: i64, cy: i64) -> Result<(), String> {
326        let (_, chunks) = self
327            .planes
328            .get_mut(plane)
329            .ok_or_else(|| format!("a chunk names unknown plane {plane}"))?;
330        chunks.update(layer.to_le_bytes());
331        chunks.update(cx.to_le_bytes());
332        chunks.update(cy.to_le_bytes());
333        Ok(())
334    }
335
336    fn finish(self, side: Side) -> Snapshot {
337        let Self {
338            mut ids,
339            planes,
340            object_planes,
341            ..
342        } = self;
343        let mut fingerprints = BTreeMap::new();
344        for (plane, (document, chunks)) in planes {
345            let mut hasher = Sha256::new();
346            hasher.update(document);
347            hasher.update(chunks.finalize());
348            let prefix = format!("{plane}/");
349            for kind in [Kind::Anchor, Kind::Stairwell, Kind::Zone] {
350                let Some(children) = ids.get(&kind) else {
351                    continue;
352                };
353                let range = children
354                    .range::<str, _>((Bound::Included(prefix.as_str()), Bound::Unbounded))
355                    .take_while(|(id, _)| id.starts_with(&prefix));
356                for (id, fingerprint) in range {
357                    feed(&mut hasher, kind.as_str().as_bytes());
358                    feed(&mut hasher, &id.as_bytes()[prefix.len()..]);
359                    hasher.update(fingerprint);
360                }
361            }
362            fingerprints.insert(plane, hasher.finalize().into());
363        }
364        ids.insert(Kind::Plane, fingerprints);
365        Snapshot {
366            side,
367            ids,
368            object_planes,
369        }
370    }
371}
372
373/// Feeds `bytes` to `hasher`, prefixed with their length, so consecutive
374/// fields cannot run together.
375fn feed(hasher: &mut Sha256, bytes: &[u8]) {
376    hasher.update(u64::try_from(bytes.len()).unwrap_or(u64::MAX).to_le_bytes());
377    hasher.update(bytes);
378}
379
380/// Limits for reading back canonical JSON, which is one line: the format's
381/// limits, with the line limit raised to the input limit.
382fn canonical_limits() -> ParseLimits {
383    let limits = ParseLimits::default();
384    ParseLimits {
385        max_line_bytes: limits.max_input_bytes,
386        ..limits
387    }
388}
389
390/// SHA-256 of a canonical JSON object without the members named `without`,
391/// as canonical JSON.
392fn document_fingerprint(document: &str, without: &[&str]) -> Result<Fingerprint, String> {
393    let parsed = Document::parse(document, &canonical_limits())
394        .map_err(|error| format!("a stored document cannot be read again: {error}"))?;
395    let members = parsed
396        .root()
397        .as_object()
398        .ok_or("a stored document is not an object")?;
399    let excluded: BTreeSet<&str> = without.iter().copied().collect();
400    let mut hasher = Sha256::new();
401    hasher.update(b"{");
402    let mut first = true;
403    let mut key = String::new();
404    for member in members
405        .iter()
406        .filter(|member| !excluded.contains(member.key.as_str()))
407    {
408        if !first {
409            hasher.update(b",");
410        }
411        first = false;
412        key.clear();
413        write_json_string(&member.key, &mut key);
414        hasher.update(key.as_bytes());
415        hasher.update(b":");
416        hasher.update(parsed.canonical(&member.value).as_bytes());
417    }
418    hasher.update(b"}");
419    Ok(hasher.finalize().into())
420}
421
422fn hex(bytes: &[u8]) -> String {
423    bytes.iter().fold(String::new(), |mut output, byte| {
424        let _ = write!(output, "{byte:02x}");
425        output
426    })
427}
tilewright_diff/snapshot.rs

tilewright_diff/
snapshot.rs
