git-ents.gitmain
⌘K
foforge

crates/kernel/ents-sync/src/merge.rs

merge.rs246 lines · 9.1 KB · rusthistorycomment on this file
1//! The schema-aware three-way merge over typed trees — the one hard part
2//! of sync (`sync.divergence-merge`).
3//!
4//! A meta-ref's tip is a git tree that `facet-git-tree` mapped directly
5//! from a `#[derive(Facet)]` struct (`meta-ref.typed-tree`): a struct's
6//! fields are tree entries, a nested struct or collection is a sub-tree,
7//! and a scalar or string is a blob. Because the tree *is* the schema, a
8//! structural three-way merge over the tree is a field-by-field merge over
9//! the entity — never a textual merge over serialized bytes, which
10//! `sync.divergence-merge` forbids.
11//!
12//! The merge is content-addressed, so it needs no diff heuristics: two
13//! sides agree exactly when their object ids are equal. For each entry
14//! (each field, each collection element) the classic three-way rule
15//! applies against the merge-base tree `base`:
16//!
17//! - both sides equal → keep it (includes both-deleted and both-made-the-
18//! same-change);
19//! - one side equals `base` → the *other* side changed it, so take the
20//! other (a deletion included);
21//! - both sides changed it differently → recurse if both are sub-trees
22//! (a nested struct or collection merges field-by-field), otherwise it
23//! is a genuine conflict at that path.
24//!
25//! The result is either a clean merged tree (a new [`ObjectId`], ready to
26//! become a merge tip whose signature makes it satisfy the tip invariant)
27//! or the set of conflicting paths for a human to resolve.
28
29use std::collections::{BTreeSet, HashMap};
30
31use gix::bstr::{BString, ByteVec as _};
32use gix_hash::ObjectId;
33use gix_object::tree::{Entry as TreeEntry, EntryKind, EntryMode};
34use gix_object::{Find, TreeRef, Write};
35
36use crate::error::{Error, Result};
37
38/// The outcome of a schema-aware three-way merge ([`three_way`]).
39#[derive(Debug, Clone, PartialEq, Eq)]
40pub enum Merge {
41 /// The two sides merged cleanly into this tree. A merge tip recording
42 /// it, signed by an authorized member, satisfies the tip invariant
43 /// (`sync.divergence-merge`).
44 Clean(ObjectId),
45 /// The two sides changed the same leaf differently. Each entry is a
46 /// slash-joined path into the typed tree — a field name, or a field
47 /// name and a collection index, exactly as `facet-git-tree` names
48 /// them — so a caller can report *which* piece of the entity clashed.
49 Conflict(Vec<BString>),
50}
51
52impl Merge {
53 /// The clean merged tree, or `None` if the merge conflicted.
54 #[must_use]
55 pub fn tree(&self) -> Option<ObjectId> {
56 match self {
57 Merge::Clean(oid) => Some(*oid),
58 Merge::Conflict(_) => None,
59 }
60 }
61}
62
63/// One entry of a tree, reduced to what the merge compares: its object id
64/// and whether it is a sub-tree (so recursion is possible) or a leaf.
65#[derive(Debug, Clone, Copy, PartialEq, Eq)]
66struct Slot {
67 oid: ObjectId,
68 mode: EntryMode,
69}
70
71impl Slot {
72 fn is_tree(self) -> bool {
73 self.mode.is_tree()
74 }
75}
76
77/// Schema-aware three-way merge of two typed trees against their merge
78/// base (`sync.divergence-merge`).
79///
80/// `base` is the tree of the merge-base commit — `None` when the two heads
81/// share no common ancestor, which the merge treats as an empty base (every
82/// entry looks added on both sides, so any difference is a conflict rather
83/// than a silent pick). `ours` and `theirs` are the two divergent trees;
84/// the merge is commutative, so their roles are symmetric.
85///
86/// Merged sub-trees and blobs are written into `objects`; the returned
87/// [`Merge::Clean`] id is the root of the new tree.
88///
89/// # Errors
90///
91/// [`Error::Decode`] if a purported tree does not decode, [`Error::Object`]
92/// or [`Error::Missing`] if one cannot be read, [`Error::Write`] if the
93/// merged tree cannot be stored.
94///
95/// # Examples
96///
97/// A one-sided change is adopted wholesale — the field-level analogue of a
98/// fast-forward:
99///
100/// ```
101/// use ents_sync::merge::{Merge, three_way};
102/// use ents_testutil::ObjectStore;
103///
104/// // A stand-in for `ents-forge`'s `Issue` (this crate cannot depend on
105/// // `ents-forge`): any Facet-derived entity exercises the merge.
106/// # #[derive(facet::Facet, Clone)]
107/// # struct Issue { title: String, body: String, state: String }
108/// #
109/// let objects = ObjectStore::default();
110/// let issue = Issue {
111/// title: "t".into(), body: "b".into(), state: "open".into(),
112/// };
113/// let base = facet_git_tree::serialize_into(&issue, &objects).expect("ser");
114/// let mut closed = issue.clone();
115/// closed.state = "closed".into();
116/// let theirs = facet_git_tree::serialize_into(&closed, &objects).expect("ser");
117///
118/// // ours == base (we changed nothing); theirs advanced.
119/// let merged = three_way(&objects, Some(base), base, theirs).expect("merges");
120/// assert_eq!(merged, Merge::Clean(theirs));
121/// ```
122// @relation(sync.divergence-merge, scope=function)
123pub fn three_way(
124 objects: &(impl Find + Write),
125 base: Option<ObjectId>,
126 ours: ObjectId,
127 theirs: ObjectId,
128) -> Result<Merge> {
129 // Content addressing makes the fast path exact: equal ids are equal
130 // subtrees, so identical sides need no walk at all.
131 if ours == theirs {
132 return Ok(Merge::Clean(ours));
133 }
134
135 let base_entries = match base {
136 Some(oid) => read_tree(objects, oid)?,
137 None => HashMap::new(),
138 };
139 let ours_entries = read_tree(objects, ours)?;
140 let theirs_entries = read_tree(objects, theirs)?;
141
142 let mut names: BTreeSet<&BString> = BTreeSet::new();
143 names.extend(base_entries.keys());
144 names.extend(ours_entries.keys());
145 names.extend(theirs_entries.keys());
146
147 let mut merged: Vec<TreeEntry> = Vec::new();
148 let mut conflicts: Vec<BString> = Vec::new();
149
150 for name in names {
151 let o = ours_entries.get(name).copied();
152 let t = theirs_entries.get(name).copied();
153 let b = base_entries.get(name).copied();
154
155 if o == t {
156 // Both sides agree, including both-absent and both-identical-
157 // change. Keep it when present.
158 push_slot(&mut merged, name, o);
159 } else if o == b {
160 // Ours is unchanged from base, so theirs owns this entry —
161 // a deletion included (`t == None`).
162 push_slot(&mut merged, name, t);
163 } else if t == b {
164 // Symmetric: theirs is unchanged, ours owns this entry.
165 push_slot(&mut merged, name, o);
166 } else {
167 // Both sides changed the same entry differently. A sub-tree on
168 // both sides is a nested struct or collection that can itself
169 // be merged field-by-field; anything else is a leaf conflict.
170 match (o, t) {
171 (Some(so), Some(st)) if so.is_tree() && st.is_tree() => {
172 let sub_base = b.filter(|s| s.is_tree()).map(|s| s.oid);
173 match three_way(objects, sub_base, so.oid, st.oid)? {
174 Merge::Clean(sub) => merged.push(TreeEntry {
175 mode: EntryKind::Tree.into(),
176 filename: name.clone(),
177 oid: sub,
178 }),
179 Merge::Conflict(paths) => {
180 for p in paths {
181 conflicts.push(join(name, &p));
182 }
183 }
184 }
185 }
186 _ => conflicts.push(name.clone()),
187 }
188 }
189 }
190
191 if conflicts.is_empty() {
192 // git tree entries are canonically sorted; `TreeEntry`'s own `Ord`
193 // is that order, matching how `facet-git-tree` writes trees.
194 merged.sort();
195 let oid = objects.write(&gix_object::Tree { entries: merged })?;
196 Ok(Merge::Clean(oid))
197 } else {
198 conflicts.sort();
199 Ok(Merge::Conflict(conflicts))
200 }
201}
202
203/// Read the entries of the tree at `oid` into a name-keyed map.
204fn read_tree(objects: &impl Find, oid: ObjectId) -> Result<HashMap<BString, Slot>> {
205 let mut buf = Vec::new();
206 let data = objects
207 .try_find(&oid, &mut buf)
208 .map_err(|source| Error::Object { oid, source })?
209 .ok_or(Error::Missing { oid })?;
210 let tree = TreeRef::from_bytes(data.data, oid.kind()).map_err(|e| Error::Decode {
211 oid,
212 detail: e.to_string(),
213 })?;
214 let mut map = HashMap::with_capacity(tree.entries.len());
215 for entry in &tree.entries {
216 map.insert(
217 entry.filename.to_owned(),
218 Slot {
219 oid: entry.oid.to_owned(),
220 mode: entry.mode,
221 },
222 );
223 }
224 Ok(map)
225}
226
227/// Append `slot` to `merged` under `name`, if it is present (a `None` slot
228/// is an entry deleted on the winning side, so nothing is written).
229fn push_slot(merged: &mut Vec<TreeEntry>, name: &BString, slot: Option<Slot>) {
230 if let Some(slot) = slot {
231 merged.push(TreeEntry {
232 mode: slot.mode,
233 filename: name.clone(),
234 oid: slot.oid,
235 });
236 }
237}
238
239/// Join a parent entry name and a child path with `/`, the separator
240/// `facet-git-tree` uses for nested tree paths.
241fn join(parent: &BString, child: &BString) -> BString {
242 let mut path = parent.clone();
243 path.push_char('/');
244 path.push_str(child);
245 path
246}