git-ents.gitmain
⌘K
foforge

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

resolve.rs242 lines · 10.3 KB · rusthistorycomment on this file
1//! One merge machinery for every same-tip reconciliation sync performs:
2//! same-actor divergence (`sync.divergence-merge`,
3//! `gate.same-actor-divergence`) and adoption — a maintainer folding an
4//! inbox entity onto its canonical ref, or a member's self-run results onto
5//! the canonical results ref (`sync.adoption-machinery`,
6//! `gate.adoption-merge`).
7//!
8//! All three are the same operation: take the authorized side's current tip
9//! (`ours`) and the head being folded in (`theirs`), merge their typed trees
10//! three-way against the merge base ([`crate::merge::three_way`]), and record
11//! the result as a two-parent merge commit signed by the placing member.
12//! There is deliberately no separate adoption code path
13//! (`sync.adoption-machinery`), and deliberately no cherry-pick: `theirs`
14//! stays a parent, so the contributor's original signed commit — and its
15//! attribution — remains in ancestry (`sync.adoption-no-cherry-pick`). A
16//! cherry-pick would instead create a fresh commit by the placer and destroy
17//! the author's signature, which no gate could detect after the fact, so this
18//! property is the machinery's to keep, not the gate's.
19
20use std::collections::HashSet;
21
22use gix::bstr::BString;
23use gix::refs::FullName;
24use gix_hash::ObjectId;
25use gix_object::{Commit, Find, Kind, Write, WriteTo as _};
26
27use crate::error::{Error, Result};
28use crate::merge::{Merge, three_way};
29use crate::objects::{commit_tree, parents};
30
31/// The two heads a merge reconciles onto one ref.
32///
33/// `ours` is the tip of the authorized side — the canonical ref the merge
34/// tip will advance, or `None` when that ref does not exist yet (adopting a
35/// contributor's brand-new entity onto a canonical ref that has no prior
36/// tip). `theirs` is the head being folded in: the other machine's tip in a
37/// divergence, or the contributor's inbox / self-run tip in an adoption.
38#[derive(Debug, Clone)]
39pub struct Heads {
40 /// The ref the resulting merge tip advances; the gate recomputes this
41 /// name from the merge's signed content (`gate.identity-binding`).
42 pub refname: FullName,
43 /// The authorized side's current tip, or `None` if the ref is new.
44 pub ours: Option<ObjectId>,
45 /// The head being folded in — always kept as a parent, never
46 /// cherry-picked (`sync.adoption-no-cherry-pick`).
47 pub theirs: ObjectId,
48}
49
50/// The result of [`merge_heads`].
51#[derive(Debug, Clone, PartialEq, Eq)]
52pub enum Merged {
53 /// A signed merge tip that advances [`Heads::refname`]. It descends from
54 /// both parents, so an authorized signature makes it satisfy the tip
55 /// invariant (`sync.divergence-merge`); `theirs` is in its ancestry with
56 /// attribution intact (`sync.adoption-no-cherry-pick`).
57 Tip(ObjectId),
58 /// The two heads changed the same leaf of the typed tree differently.
59 /// Each path is a field (and, for a collection, an index) into the
60 /// entity — a human resolves it before the merge can complete.
61 Conflict(Vec<BString>),
62}
63
64/// Resolve two divergent heads into one signed merge tip, or report the
65/// conflicting paths — the single machinery divergence and adoption share
66/// (`sync.divergence-merge`, `sync.adoption-machinery`).
67///
68/// The typed trees of `ours` and `theirs` are merged three-way against
69/// their merge base; a clean merge is recorded as a merge commit whose
70/// parents are `[ours, theirs]` (just `[theirs]` when the canonical ref is
71/// new), authored and committed by `author`, and signed by `sign`; the
72/// merge names no ref of its own, and the gate recomputes the binding for
73/// [`Heads::refname`] from the merged content. `sign` returns the
74/// armored SSHSIG PEM for the commit's payload — exactly what git stores in
75/// the `gpgsig` header — so the composition root injects the placing
76/// member's key without this crate ever holding one.
77///
78/// Because `theirs` is always a parent, the contributor's original signed
79/// commit stays in ancestry: this is a merge, never a cherry-pick
80/// (`sync.adoption-no-cherry-pick`). The placer signs the *tip*, which is
81/// what makes an authorized member's merge the legitimate adoption mechanism
82/// (`gate.adoption-merge`) rather than a direct fast-forward to an
83/// unauthorized signature (`gate.adoption-no-fast-forward`).
84///
85/// # Errors
86///
87/// Propagates object read/decode/write failures from the merge and from
88/// building the commit.
89///
90/// # Examples
91///
92/// ```
93/// use ents_model::{Provenance, namespace};
94/// use ents_sync::resolve::{Heads, Merged, merge_heads};
95/// use ents_testutil::{Keypair, MemRefStore, ObjectStore, enroll_member, write_meta_entity};
96///
97/// // A stand-in for `ents-forge`'s `Issue` (this crate cannot depend on
98/// // `ents-forge`): any Facet-derived entity exercises the merge.
99/// # #[derive(facet::Facet, Clone)]
100/// # struct Issue { title: String, body: String, state: String }
101/// #
102/// let refs = MemRefStore::default();
103/// let objects = ObjectStore::default();
104/// let key = Keypair::from_seed(1);
105/// enroll_member(&refs, &objects, "jdc", &key, Provenance::AdminRegistered, 100);
106///
107/// // Two of jdc's machines diverged on the same single-writer ref.
108/// let name: gix::refs::FullName = "refs/meta/issues/1".try_into().expect("valid");
109/// let issue = Issue {
110/// title: "t".into(), body: "b".into(), state: "open".into(),
111/// };
112/// let ours = write_meta_entity(&refs, &objects, name.clone(), &issue, Some(&key), 200);
113/// let mut other = issue.clone();
114/// other.state = "closed".into();
115/// let theirs = write_meta_entity(&refs, &objects, name.clone(), &other, Some(&key), 300);
116///
117/// let author = gix::actor::Signature {
118/// name: "jdc".into(), email: "jdc@ents.test".into(),
119/// time: gix::date::Time { seconds: 400, offset: 0 },
120/// };
121/// let heads = Heads { refname: name, ours: Some(ours), theirs };
122/// let merged = merge_heads(&objects, &heads, &author, "Merge divergent heads",
123/// |payload| key.sign(payload)).expect("merges");
124/// assert!(matches!(merged, Merged::Tip(_)));
125/// ```
126// @relation(sync.divergence-merge, sync.adoption-machinery, sync.adoption-no-cherry-pick, scope=function)
127pub fn merge_heads(
128 objects: &(impl Find + Write),
129 heads: &Heads,
130 author: &gix::actor::Signature,
131 summary: &str,
132 sign: impl FnOnce(&[u8]) -> String,
133) -> Result<Merged> {
134 let theirs_tree = commit_tree(objects, heads.theirs)?;
135
136 let (tree, parents) = match heads.ours {
137 // Adopting onto a ref with no prior tip: nothing to merge, but
138 // `theirs` still becomes the sole parent so attribution survives —
139 // a degenerate merge, never a cherry-pick.
140 None => (theirs_tree, vec![heads.theirs]),
141 Some(ours) => {
142 let base = merge_base(objects, ours, heads.theirs)?;
143 let base_tree = base.map(|b| commit_tree(objects, b)).transpose()?;
144 let ours_tree = commit_tree(objects, ours)?;
145 match three_way(objects, base_tree, ours_tree, theirs_tree)? {
146 Merge::Clean(tree) => (tree, vec![ours, heads.theirs]),
147 Merge::Conflict(paths) => return Ok(Merged::Conflict(paths)),
148 }
149 }
150 };
151
152 let tip = seal(objects, tree, parents, author, summary, sign)?;
153 Ok(Merged::Tip(tip))
154}
155
156/// Build and sign the merge commit — the tip whose signature, not any tree
157/// content, is what satisfies the tip invariant. The commit names no ref
158/// of its own; the gate recomputes the binding from the merged content and
159/// the all-roots walk (`gate.identity-binding`), which holds across this
160/// merge because both parents descend from the same genesis.
161fn seal(
162 objects: &impl Write,
163 tree: ObjectId,
164 parents: Vec<ObjectId>,
165 author: &gix::actor::Signature,
166 summary: &str,
167 sign: impl FnOnce(&[u8]) -> String,
168) -> Result<ObjectId> {
169 let message = summary.to_owned();
170 let mut commit = Commit {
171 tree,
172 parents: parents.into(),
173 author: author.clone(),
174 committer: author.clone(),
175 encoding: None,
176 message: message.into(),
177 extra_headers: Vec::new(),
178 };
179
180 // Sign exactly as `git commit -S` does: SSHSIG over the commit
181 // serialized *without* its gpgsig header, stored back as that header —
182 // so the signature is repository data that verifies offline
183 // (`gate.signature-artifact`).
184 let mut payload = Vec::new();
185 commit.write_to(&mut payload).map_err(|e| Error::Decode {
186 oid: tree,
187 detail: format!("serializing merge commit failed: {e}"),
188 })?;
189 let pem = sign(&payload);
190 commit
191 .extra_headers
192 .push(("gpgsig".into(), pem.trim_end().into()));
193
194 let mut raw = Vec::new();
195 commit.write_to(&mut raw).map_err(|e| Error::Decode {
196 oid: tree,
197 detail: format!("serializing signed merge commit failed: {e}"),
198 })?;
199 Ok(objects.write_buf(Kind::Commit, &raw)?)
200}
201
202/// The nearest common ancestor of `a` and `b` by parent edges, or `None`
203/// when they share no ancestor (each is then merged against an empty base).
204///
205/// This is a breadth-first nearest-ancestor search: it collects every
206/// ancestor of `a`, then walks `b`'s ancestry breadth-first and returns the
207/// first commit already seen from `a`. For the divergence and adoption
208/// shapes sync produces — two lines splitting from one common tip — that is
209/// the true merge base. It does not resolve the multiple-merge-base
210/// criss-cross case optimally; a stricter base would only ever *reduce*
211/// spurious conflicts, never admit a wrong clean merge, since the three-way
212/// rule keeps a field only when at least one side matches the base.
213fn merge_base(objects: &impl Find, a: ObjectId, b: ObjectId) -> Result<Option<ObjectId>> {
214 let ancestors_of_a = ancestors(objects, a)?;
215 let mut queue = std::collections::VecDeque::from([b]);
216 let mut seen = HashSet::new();
217 while let Some(oid) = queue.pop_front() {
218 if !seen.insert(oid) {
219 continue;
220 }
221 if ancestors_of_a.contains(&oid) {
222 return Ok(Some(oid));
223 }
224 for parent in parents(objects, oid)? {
225 queue.push_back(parent);
226 }
227 }
228 Ok(None)
229}
230
231/// Every commit reachable from `oid` by parent edges, inclusive.
232fn ancestors(objects: &impl Find, oid: ObjectId) -> Result<HashSet<ObjectId>> {
233 let mut seen = HashSet::new();
234 let mut stack = vec![oid];
235 while let Some(oid) = stack.pop() {
236 if !seen.insert(oid) {
237 continue;
238 }
239 stack.extend(parents(objects, oid)?);
240 }
241 Ok(seen)
242}