crates/kernel/ents-sync/tests/merge.rs
merge.rshistorycomment on this file
| 1 | //! Property tests for the schema-aware three-way merge (`sync.divergence-merge`). |
| 2 | //! |
| 3 | //! Strategy: **proptest** — the spec states an algebraic invariant (a merge |
| 4 | //! that respects the typed tree's schema, field by field) over an |
| 5 | //! unenumerable input space, so example rows cannot stand in for it. The |
| 6 | //! properties pinned here are the ones a schema-aware merge must uphold: |
| 7 | //! disjoint field edits combine (never conflict), the same field changed |
| 8 | //! two ways conflicts, and the merge is commutative in its two sides. |
| 9 | |
| 10 | #![expect(clippy::unwrap_used, clippy::expect_used, reason = "tests")] |
| 11 | |
| 12 | use ents_model::MemberId; |
| 13 | use ents_sync::merge::{Merge, three_way}; |
| 14 | use ents_testutil::ObjectStore; |
| 15 | use proptest::prelude::*; |
| 16 | |
| 17 | /// A stand-in for `ents-forge`'s `Issue` (this crate cannot depend on |
| 18 | /// `ents-forge`, which itself depends on `ents-sync`'s sibling kernel |
| 19 | /// crates): a rich, multi-field entity — two scalar strings, a |
| 20 | /// restricted-value string, and two collections — covering every field |
| 21 | /// shape the schema-aware merge must handle field-by-field. |
| 22 | #[derive(Debug, Clone, PartialEq, Eq, facet::Facet)] |
| 23 | struct Issue { |
| 24 | title: String, |
| 25 | body: String, |
| 26 | state: String, |
| 27 | assignees: Vec<MemberId>, |
| 28 | labels: Vec<String>, |
| 29 | } |
| 30 | |
| 31 | /// A base issue with room to edit every field independently. |
| 32 | fn issue_strategy() -> impl Strategy<Value = Issue> { |
| 33 | ( |
| 34 | "[a-z]{1,8}", |
| 35 | "[a-z]{1,8}", |
| 36 | prop::sample::select(vec!["open", "closed"]), |
| 37 | prop::collection::vec("[a-z]{1,5}", 0..3), |
| 38 | prop::collection::vec("[a-z]{1,5}", 0..3), |
| 39 | ) |
| 40 | .prop_map(|(title, body, state, assignees, labels)| Issue { |
| 41 | title, |
| 42 | body, |
| 43 | state: state.to_string(), |
| 44 | assignees: assignees.into_iter().map(MemberId::new).collect(), |
| 45 | labels, |
| 46 | }) |
| 47 | } |
| 48 | |
| 49 | /// Apply a deterministic, value-changing edit to field `i` (0..5). |
| 50 | fn edit_field(issue: &mut Issue, i: usize) { |
| 51 | match i { |
| 52 | 0 => issue.title.push_str("-edit"), |
| 53 | 1 => issue.body.push_str("-edit"), |
| 54 | 2 => { |
| 55 | issue.state = if issue.state == "open" { |
| 56 | "closed" |
| 57 | } else { |
| 58 | "open" |
| 59 | } |
| 60 | .to_string() |
| 61 | } |
| 62 | 3 => issue.assignees.push(MemberId::new("added")), |
| 63 | _ => issue.labels.push("added".to_string()), |
| 64 | } |
| 65 | } |
| 66 | |
| 67 | fn ser(objects: &ObjectStore, issue: &Issue) -> gix_hash::ObjectId { |
| 68 | facet_git_tree::serialize_into(issue, objects).unwrap() |
| 69 | } |
| 70 | |
| 71 | fn de(objects: &ObjectStore, tree: gix_hash::ObjectId) -> Issue { |
| 72 | facet_git_tree::deserialize(&tree, objects).unwrap() |
| 73 | } |
| 74 | |
| 75 | proptest! { |
| 76 | /// Each side changes a *disjoint* set of fields, so the merge must fold |
| 77 | /// both sets in with no conflict — the concrete meaning of "schema-aware |
| 78 | /// three-way merge over the typed tree" (`sync.divergence-merge`): the |
| 79 | /// merged entity carries every field's winning value, resolved per field. |
| 80 | // @relation(sync.divergence-merge, scope=function, role=Verifies) |
| 81 | #[test] |
| 82 | fn disjoint_field_edits_merge_field_by_field( |
| 83 | base in issue_strategy(), |
| 84 | owners in prop::collection::vec(0u8..3, 5), |
| 85 | ) { |
| 86 | let objects = ObjectStore::default(); |
| 87 | let mut ours = base.clone(); |
| 88 | let mut theirs = base.clone(); |
| 89 | let mut expected = base.clone(); |
| 90 | for (i, &owner) in owners.iter().enumerate() { |
| 91 | match owner { |
| 92 | 1 => { edit_field(&mut ours, i); edit_field(&mut expected, i); } |
| 93 | 2 => { edit_field(&mut theirs, i); edit_field(&mut expected, i); } |
| 94 | _ => {} |
| 95 | } |
| 96 | } |
| 97 | |
| 98 | let b = ser(&objects, &base); |
| 99 | let o = ser(&objects, &ours); |
| 100 | let t = ser(&objects, &theirs); |
| 101 | |
| 102 | let merged = three_way(&objects, Some(b), o, t).unwrap(); |
| 103 | let tree = merged.tree().expect("disjoint edits never conflict"); |
| 104 | prop_assert_eq!(de(&objects, tree), expected); |
| 105 | } |
| 106 | |
| 107 | /// Both sides change the *same* scalar field to different values: no |
| 108 | /// content-addressed pick is possible, so the merge must report that |
| 109 | /// field as a conflict rather than silently choose one. |
| 110 | // @relation(sync.divergence-merge, scope=function, role=Verifies) |
| 111 | #[test] |
| 112 | fn same_field_divergent_edits_conflict(base in issue_strategy()) { |
| 113 | let objects = ObjectStore::default(); |
| 114 | let mut ours = base.clone(); |
| 115 | ours.title.push_str("-ours"); |
| 116 | let mut theirs = base.clone(); |
| 117 | theirs.title.push_str("-theirs"); |
| 118 | |
| 119 | let b = ser(&objects, &base); |
| 120 | let o = ser(&objects, &ours); |
| 121 | let t = ser(&objects, &theirs); |
| 122 | |
| 123 | let merged = three_way(&objects, Some(b), o, t).unwrap(); |
| 124 | prop_assert_eq!(merged, Merge::Conflict(vec!["title".into()])); |
| 125 | } |
| 126 | |
| 127 | /// The merge is commutative in its two sides: swapping `ours` and |
| 128 | /// `theirs` yields the identical clean tree, or the identical conflict |
| 129 | /// set. A resolution that depended on argument order would silently |
| 130 | /// disagree with itself across two machines. |
| 131 | // @relation(sync.divergence-merge, scope=function, role=Verifies) |
| 132 | #[test] |
| 133 | fn merge_is_commutative( |
| 134 | base in issue_strategy(), |
| 135 | ours in issue_strategy(), |
| 136 | theirs in issue_strategy(), |
| 137 | ) { |
| 138 | let objects = ObjectStore::default(); |
| 139 | let b = ser(&objects, &base); |
| 140 | let o = ser(&objects, &ours); |
| 141 | let t = ser(&objects, &theirs); |
| 142 | |
| 143 | let forward = three_way(&objects, Some(b), o, t).unwrap(); |
| 144 | let backward = three_way(&objects, Some(b), t, o).unwrap(); |
| 145 | |
| 146 | match (forward, backward) { |
| 147 | (Merge::Clean(x), Merge::Clean(y)) => prop_assert_eq!(x, y), |
| 148 | (Merge::Conflict(a), Merge::Conflict(bb)) => prop_assert_eq!(a, bb), |
| 149 | (f, bk) => prop_assert!(false, "clean-ness must match: {:?} vs {:?}", f, bk), |
| 150 | } |
| 151 | } |
| 152 | |
| 153 | /// A side that did not move is a no-op: `three_way(base, base, theirs)` |
| 154 | /// adopts `theirs` wholesale — the field-level analogue of a |
| 155 | /// fast-forward, and the trivial-merge case adoption relies on. |
| 156 | // @relation(sync.divergence-merge, scope=function, role=Verifies) |
| 157 | #[test] |
| 158 | fn one_sided_change_adopts_the_other( |
| 159 | base in issue_strategy(), |
| 160 | theirs in issue_strategy(), |
| 161 | ) { |
| 162 | let objects = ObjectStore::default(); |
| 163 | let b = ser(&objects, &base); |
| 164 | let t = ser(&objects, &theirs); |
| 165 | |
| 166 | prop_assert_eq!(three_way(&objects, Some(b), b, t).unwrap(), Merge::Clean(t)); |
| 167 | prop_assert_eq!(three_way(&objects, Some(b), b, b).unwrap(), Merge::Clean(b)); |
| 168 | } |
| 169 | } |