blockworx/log/
encode.rs

1//! The persisted encoding.
2//!
3//! JSON, via serde. A change log is a thing people need to read while this
4//! editor is being built, and legibility is worth more right now than the bytes
5//! a compact format would save — the storage layer compresses anyway.
6//!
7//! Two properties matter more than the choice of format, and both come from
8//! elsewhere:
9//!
10//! - **Tags are names, not positions.** A self-describing format writes
11//!   `"Parent"`, so reordering [`PropWrite`](crate::log::PropWrite) is
12//!   harmless. A compact format such as bincode or postcard writes the
13//!   variant's *declaration index* instead, which is why one is not used here:
14//!   it would make variant order a silent part of the format.
15//! - **Shape is frozen by version.** [`Change`] is an enum over `ChangeV1`, so
16//!   a change's encoding — and therefore the hash identifying it — cannot drift
17//!   as the code grows. A newer build's `V2` fails to deserialize rather than
18//!   being reinterpreted.
19//!
20//! What is still owned here is the one thing to be careful with: [`to_bytes`]
21//! is what every change is *identified* by, forever and across peers. That it
22//! is canonical is a property of what a change can contain — no floats, so no
23//! formatting choices; ordered collections, so no iteration-order choices; a
24//! frozen shape, so no field-list choices — not something `serde_json` promises.
25
26use crate::log::change::Change;
27use crate::log::state::DocState;
28
29/// Why a log could not be read. Every variant means "stop", never "continue
30/// without this part": half-loading a log written by a newer build would fork
31/// the document silently.
32#[derive(Debug, thiserror::Error)]
33pub enum DecodeError {
34    #[error("the log could not be read: {0}")]
35    Malformed(#[from] serde_json::Error),
36}
37
38/// The bytes a change is identified by.
39pub fn to_bytes(change: &Change) -> Vec<u8> {
40    // Serialization of a `Change` cannot fail — every type in it is an ordinary
41    // value with a derived impl — and a hash of nothing would be worse than a
42    // hash of an empty document, so there is no error to propagate.
43    serde_json::to_vec(change).unwrap_or_default()
44}
45
46pub fn from_bytes(bytes: &[u8]) -> Result<Change, DecodeError> {
47    Ok(serde_json::from_slice(bytes)?)
48}
49
50/// A folded state as bytes: the snapshot payload, and how two replicas are
51/// compared.
52///
53/// "Converged" has to mean byte-identical rather than structurally equal — a
54/// state holding an `f32` label offset would compare unequal to itself under
55/// `PartialEq` if that offset were ever NaN.
56pub fn state_to_bytes(state: &DocState) -> Vec<u8> {
57    serde_json::to_vec(state).unwrap_or_default()
58}
59
60/// The document as a reader sees it: live elements and the register values they
61/// actually hold, with every write order dropped.
62///
63/// Undo is why this exists. Undoing an edit appends the inverse rather than
64/// rewinding, so a register that was cleared and written again ends up holding
65/// its original value under a *later* order — the document reads as it did
66/// before, while [`state_to_bytes`] rightly says the history moved on.
67pub fn state_values_to_bytes(state: &DocState) -> Vec<u8> {
68    let visible: Vec<_> = state
69        .iter()
70        .filter(|(_, element)| element.is_live())
71        .map(|(id, element)| {
72            let set: Vec<_> = element
73                .registers()
74                .filter_map(|(tag, register)| register.value.as_ref().map(|value| (tag, value)))
75                .collect();
76            (id, element.kind(), set)
77        })
78        .collect();
79    serde_json::to_vec(&visible).unwrap_or_default()
80}
81
82#[cfg(test)]
83mod tests {
84    use uuid::Uuid;
85
86    use super::*;
87    use crate::log::change::{SemanticLabel, WallTime};
88    use crate::log::command::{Command, ElementKind, PropChange, PropSet, PropWrite};
89    use crate::log::id::{ActorId, ChangeHash, ElementId, Lamport, Stamp};
90    use crate::log::state::Element;
91
92    fn actor() -> ActorId {
93        ActorId::from_uuid(Uuid::from_bytes([0xA1; 16]))
94    }
95
96    fn element(byte: u8) -> ElementId {
97        ElementId::from_uuid(Uuid::from_bytes([byte; 16]))
98    }
99
100    fn stamp(lamport: u64) -> Stamp {
101        Stamp {
102            lamport: Lamport::new(lamport),
103            actor: actor(),
104        }
105    }
106
107    fn a_change() -> Change {
108        Change::new(
109            stamp(9),
110            [
111                ChangeHash::from_bytes([1; 32]),
112                ChangeHash::from_bytes([2; 32]),
113            ],
114            SemanticLabel::new("Moved 2 blocks"),
115            vec![
116                Command::Create {
117                    id: element(5),
118                    kind: ElementKind::Route,
119                    parent: element(6),
120                    init: PropSet::new()
121                        .with(PropWrite::Name("net 7".into()))
122                        .with(PropWrite::Accent(2)),
123                },
124                Command::SetProp {
125                    id: element(5),
126                    change: PropChange::Accent {
127                        old: Some(2),
128                        new: Some(3),
129                    },
130                },
131                Command::SetProp {
132                    id: element(5),
133                    change: PropChange::Name {
134                        old: Some("net 7".into()),
135                        new: None,
136                    },
137                },
138                Command::Delete { id: element(7) },
139                Command::Restore { id: element(7) },
140            ],
141        )
142    }
143
144    fn text_of(change: &Change) -> String {
145        String::from_utf8(to_bytes(change)).expect("json is utf-8")
146    }
147
148    /// The format's fixed point.
149    ///
150    /// More necessary with serde than without it: `serde_json` does not promise
151    /// byte-stable output across releases, and these bytes are what every change
152    /// is *identified* by. A dependency upgrade that reformatted anything would
153    /// silently re-identify every change in every stored log — this is what
154    /// turns that unpromised property into a checked one. If it fails, the fix
155    /// is not to regenerate the literal.
156    #[test]
157    fn golden_bytes_pin_the_encoding() {
158        assert_eq!(
159            text_of(&a_change()),
160            concat!(
161                r#"{"V1":{"parents":["0101010101010101010101010101010101010101010101010101010101010101","0202020202020202020202020202020202020202020202020202020202020202"],"actor":"a1a1a1a1-a1a1-a1a1-a1a1-a1a1a1a1a1a1","lamport":9,"wall_time":0,"scope":null,"label":"Moved 2 blocks","commands":[{"Create":{"id":"05050505-0505-0505-0505-050505050505","kind":"Route","parent":"06060606-0606-0606-0606-060606060606","init":[{"Name":"net 7"},"#,
162                r#"{"Accent":2}]}},"#,
163                r#"{"SetProp":{"id":"05050505-0505-0505-0505-050505050505","change":{"Accent":{"old":2,"new":3}}}},"#,
164                r#"{"SetProp":{"id":"05050505-0505-0505-0505-050505050505","change":{"Name":{"old":"net 7","new":null}}}},"#,
165                r#"{"Delete":{"id":"07070707-0707-0707-0707-070707070707"}},"#,
166                r#"{"Restore":{"id":"07070707-0707-0707-0707-070707070707"}}]}}"#,
167            )
168        );
169    }
170
171    #[test]
172    fn a_whole_change_round_trips() {
173        let change = a_change();
174        let back = from_bytes(&to_bytes(&change)).expect("it just wrote this");
175        assert_eq!(back, change);
176        assert_eq!(back.hash(), change.hash());
177    }
178
179    /// Legibility is the reason for choosing JSON, so it is worth a test.
180    #[test]
181    fn a_change_encodes_as_readable_json() {
182        let text = text_of(&a_change());
183        assert!(text.contains(r#""V1""#), "the envelope version is visible");
184        assert!(
185            text.contains(r#""Accent""#),
186            "registers are named, not numbered: {text}"
187        );
188        assert!(
189            text.contains(&"01".repeat(32)),
190            "hashes are hex, not arrays of numbers: {text}"
191        );
192    }
193
194    /// What a content address depends on: one change, one encoding. Parents are
195    /// a set and a create's registers are a map, so no ordering a caller chose
196    /// can reach the bytes.
197    #[test]
198    fn one_change_has_one_encoding() {
199        let build = |parents: [ChangeHash; 2], init: PropSet| {
200            Change::new(
201                stamp(1),
202                parents,
203                SemanticLabel::new("x"),
204                vec![Command::Create {
205                    id: element(1),
206                    kind: ElementKind::Block,
207                    parent: ElementId::DOCUMENT,
208                    init,
209                }],
210            )
211        };
212        let (one, two) = (
213            ChangeHash::from_bytes([1; 32]),
214            ChangeHash::from_bytes([2; 32]),
215        );
216        let forwards = build(
217            [one, two],
218            PropSet::new()
219                .with(PropWrite::Accent(1))
220                .with(PropWrite::Name("a".into())),
221        );
222        let backwards = build(
223            [two, one],
224            PropSet::new()
225                .with(PropWrite::Name("a".into()))
226                .with(PropWrite::Accent(1)),
227        );
228
229        assert_eq!(to_bytes(&forwards), to_bytes(&backwards));
230        assert_eq!(forwards.hash(), backwards.hash());
231    }
232
233    /// A newer build's envelope must fail rather than be read as a `V1`.
234    #[test]
235    fn an_unknown_envelope_version_is_refused() {
236        let text = text_of(&a_change()).replacen(r#""V1""#, r#""V2""#, 1);
237        assert!(from_bytes(text.as_bytes()).is_err());
238    }
239
240    /// Likewise a register this build has never heard of. This is the property
241    /// a positional encoding could not give: the tag is a name, so an unknown
242    /// one is unknown rather than being read as whichever variant sits at that
243    /// index.
244    #[test]
245    fn an_unknown_register_is_refused() {
246        let text = text_of(&a_change()).replacen(r#""Accent""#, r#""Sparkle""#, 1);
247        assert!(from_bytes(text.as_bytes()).is_err());
248    }
249
250    /// Reordering `PropWrite`'s variants must not change what a stored log
251    /// means — the whole reason for a self-describing format. Renaming one is
252    /// the change that would, which is what `an_unknown_register_is_refused`
253    /// pins from the other side.
254    #[test]
255    fn a_register_is_tagged_by_name_not_by_position() {
256        let text = text_of(&a_change());
257        assert!(
258            !text.contains(r#""17""#) && !text.contains(":17,"),
259            "a positional tag leaked into the encoding: {text}"
260        );
261    }
262
263    /// A create naming one register twice would give one value two encodings,
264    /// so it is refused rather than silently deduplicated.
265    #[test]
266    fn a_create_naming_one_register_twice_is_refused() {
267        let text = text_of(&a_change());
268        let doubled = text.replacen(r#"{"Accent":2}"#, r#"{"Accent":2},{"Accent":9}"#, 1);
269        assert_ne!(
270            doubled, text,
271            "the fixture must contain the register it doubles"
272        );
273        assert!(from_bytes(doubled.as_bytes()).is_err());
274    }
275
276    #[test]
277    fn truncation_is_refused() {
278        let bytes = to_bytes(&a_change());
279        assert!(from_bytes(&bytes[..bytes.len() - 4]).is_err());
280    }
281
282    /// Two states that differ only in *when* an element was tombstoned must
283    /// encode differently. The hand-written encoder this replaced wrote every
284    /// register's write order but not liveness's, so a snapshot could not
285    /// reconstruct it and a delete/restore race resolved differently after a
286    /// snapshot restore than after a full replay. A derive cannot forget a
287    /// field.
288    #[test]
289    fn the_snapshot_encoding_covers_when_liveness_changed() {
290        use crate::log::id::{BatchIndex, WriteOrder};
291        use crate::log::state::Liveness;
292
293        let order = |lamport: u64| WriteOrder::new(stamp(lamport), BatchIndex::FIRST);
294        let deleted_at = |lamport: u64| {
295            let mut state = DocState::new();
296            state.ensure(element(1), ElementKind::Block, order(1));
297            state.set_liveness(element(1), Liveness::Deleted, order(lamport));
298            state
299        };
300
301        let (early, late) = (deleted_at(5), deleted_at(9));
302        assert_eq!(
303            early.element(element(1)).map(Element::is_live),
304            late.element(element(1)).map(Element::is_live),
305            "the two states must agree on liveness, or the order is not what is being tested"
306        );
307        assert_ne!(state_to_bytes(&early), state_to_bytes(&late));
308    }
309
310    #[test]
311    fn the_hash_covers_the_whole_envelope() {
312        let base = Change::new(stamp(1), [], SemanticLabel::new("a"), vec![]);
313        let relabelled = Change::new(stamp(1), [], SemanticLabel::new("b"), vec![]);
314        assert_ne!(base.hash(), relabelled.hash());
315
316        let mut later = base.clone();
317        later.set_wall_time(WallTime::from_millis(1));
318        assert_ne!(base.hash(), later.hash());
319
320        assert_eq!(base.hash(), base.clone().hash());
321    }
322}
blockworx/log/encode.rs

blockworx/log/
encode.rs
