| 1 | //! Encoding a whole document as one update, and checking that the |
| 2 | //! result is the document it claims to be. |
| 3 | //! |
| 4 | //! The call below is `encode_state_as_update_v1` against an EMPTY state |
| 5 | //! vector, and which call this is matters more than anything else in |
| 6 | //! this file. Against the empty vector it encodes every block, the |
| 7 | //! entire delete set, and — through yrs's own `merge_pending_v1` — the |
| 8 | //! pending queue, meaning updates whose dependencies never arrived and |
| 9 | //! which `apply_update` accepted and parked. That makes the result |
| 10 | //! merge-equivalent to the log it replaces, not merely |
| 11 | //! render-equivalent: every clock range and every tombstone survives, |
| 12 | //! so a later concurrent merge integrates against a snapshot exactly as |
| 13 | //! it would against the full history. |
| 14 | //! |
| 15 | //! Two neighbours are traps, and both look like this one: |
| 16 | //! |
| 17 | //! - `encode_diff_v1(&StateVector::default())` silently drops the |
| 18 | //! pending queue (its own doc comment says so). A document holding an |
| 19 | //! update whose dependency arrives later heals under a full replay and |
| 20 | //! does NOT heal under a diff-built snapshot — and no render |
| 21 | //! comparison can see the difference, because pending content is |
| 22 | //! invisible in both documents. |
| 23 | //! - yrs's own `Snapshot` type and `encode_state_from_snapshot` are a |
| 24 | //! different feature (historical views, requiring `skip_gc`) that |
| 25 | //! happens to share this module's name. |
| 26 | use yrs::updates::decoder::Decode; |
| 27 | use yrs::{Doc, Options, ReadTxn, StateVector, Transact}; |
| 28 | |
| 29 | /// The whole document, as one update. |
| 30 | pub fn snapshot_bytes(doc: &Doc) -> Vec<u8> { |
| 31 | doc.transact() |
| 32 | .encode_state_as_update_v1(&StateVector::default()) |
| 33 | } |
| 34 | |
| 35 | /// True when `candidate`, replayed into an empty document, is the same |
| 36 | /// document as `doc`. |
| 37 | /// |
| 38 | /// Three comparisons, none of them on encoded bytes: update encoding is |
| 39 | /// not canonical (merge boundaries vary), so byte equality would report |
| 40 | /// false mismatches and no cheap byte-level proof exists. State vector |
| 41 | /// equality says both documents saw the same clock ranges from the same |
| 42 | /// clients; delete set equality says they agree on every deletion; |
| 43 | /// `fragment_json` equality says they render to the same structure, |
| 44 | /// which catches formatting-only divergence that a text comparison |
| 45 | /// misses at identical cost. |
| 46 | /// |
| 47 | /// This is deliberately not a proof. What survives all three is "yrs |
| 48 | /// corrupted content while preserving every clock range, every deletion |
| 49 | /// and the full structural render", and that is a narrow enough residual |
| 50 | /// to accept. |
| 51 | /// |
| 52 | /// What it CANNOT catch, stated because the temptation is to believe it |
| 53 | /// can: a snapshot taken from a stale state verifies perfectly, because |
| 54 | /// it is compared against the very document that produced it. That |
| 55 | /// failure is closed by taking the snapshot from the replayed state |
| 56 | /// (the spec's D3), not here. |
| 57 | /// |
| 58 | /// Nor can it catch `snapshot_bytes` being built from the wrong call. |
| 59 | /// `ReadTxn::snapshot()` reads only `Store::blocks` — `pending` and |
| 60 | /// `pending_ds` are separate `Store` fields it never touches — and |
| 61 | /// `fragment_json` cannot render pending content either, so a candidate |
| 62 | /// built by `encode_diff_v1` (which drops the pending queue; see this |
| 63 | /// module's header) verifies as a perfect match against a document that |
| 64 | /// is still holding data the candidate lost. This verifier is exactly |
| 65 | /// as blind to that substitution as a render comparison would be. What |
| 66 | /// actually guards it is `core/tests/snapshot.rs`'s |
| 67 | /// `a_snapshot_with_a_parked_update_heals_once_its_dependency_arrives`, |
| 68 | /// which parks an update, snapshots around it, and asserts the replay |
| 69 | /// heals once the dependency arrives — a property only the correct call |
| 70 | /// has. |
| 71 | /// |
| 72 | /// guid/client_id are the caller's, never generated here — the clippy |
| 73 | /// disallowed-methods rule against drawing entropy from the CRDT library |
| 74 | /// applies to this throwaway document exactly as it does to a real one. |
| 75 | /// |
| 76 | /// Note on the state-vector/delete-set comparison: `doc.transact()` |
| 77 | /// returns the read-only `Transaction`, which — unlike `TransactionMut` |
| 78 | /// — has no `delete_set()` of its own (that method tracks only the |
| 79 | /// current transaction's deletions, not the document's whole history). |
| 80 | /// `ReadTxn::snapshot()` is what exposes the document-wide state vector |
| 81 | /// and delete set together (as `Snapshot { state_map, delete_set }`) on |
| 82 | /// either transaction kind, so both comparisons go through it. |
| 83 | pub fn verify_snapshot(doc: &Doc, candidate: &[u8], guid: &str, client_id: u64) -> bool { |
| 84 | let update = match yrs::Update::decode_v1(candidate) { |
| 85 | Ok(u) => u, |
| 86 | Err(_) => return false, |
| 87 | }; |
| 88 | let rebuilt = Doc::with_options(Options::with_guid_and_client_id(guid.into(), client_id)); |
| 89 | { |
| 90 | let mut txn = rebuilt.transact_mut(); |
| 91 | if txn.apply_update(update).is_err() { |
| 92 | return false; |
| 93 | } |
| 94 | } |
| 95 | // The state-vector/delete-set comparison is scoped to its own block |
| 96 | // so both read-only transactions (`a`, `b`) are dropped before |
| 97 | // `fragment_json` runs below. The hazard is not two overlapping |
| 98 | // reads — yrs's own docs say concurrent readers are fine, and |
| 99 | // that's not what this is anyway. `fragment_json` calls `root(doc)` |
| 100 | // (`get_or_insert_xml_fragment`) BEFORE it opens its own read |
| 101 | // transaction, and that helper goes through `doc.transact_mut()` — |
| 102 | // a WRITE acquisition — internally. Calling `fragment_json(doc)` |
| 103 | // while `a` (a read guard from `doc.transact()`) is still alive |
| 104 | // means that write acquisition blocks on the outstanding reader on |
| 105 | // this same thread, and since `a` is never going to be dropped |
| 106 | // while the very call it's blocking on hasn't returned, the thread |
| 107 | // deadlocks itself. Dropping `a`/`b` first, before calling |
| 108 | // `fragment_json` on either document, is what avoids it — the rule |
| 109 | // is "never hold a transaction guard across a call that opens one |
| 110 | // of its own," not "never overlap two reads." |
| 111 | let same_state = { |
| 112 | let (a, b) = (doc.transact(), rebuilt.transact()); |
| 113 | let (a_snapshot, b_snapshot) = (a.snapshot(), b.snapshot()); |
| 114 | a_snapshot.state_map == b_snapshot.state_map |
| 115 | && a_snapshot.delete_set == b_snapshot.delete_set |
| 116 | }; |
| 117 | same_state && crate::fragment_json(doc) == crate::fragment_json(&rebuilt) |
| 118 | } |
| 119 | |
amadan