git2db/merge.rs
1//! In-memory candidate merge composition (epic #1427, issue #1428).
2//!
3//! [`CandidateComposer`] is a pure-library wrapper over
4//! `git2::Repository::merge_trees` that produces **detached** merge
5//! candidates — trees and commits materialised into the object database
6//! without ever moving HEAD or touching the working tree. This is the M1
7//! building block for deterministic sequential candidate composition
8//! (M1, M1+2, …): each `merge_trees` step is a pure function of three trees,
9//! so the same inputs always yield the same tree OID.
10//!
11//! # Scope
12//!
13//! This module deliberately stops at *candidate* materialisation. It does not:
14//! - perform network clone/fetch (B4's job),
15//! - talk to any forge API (B4),
16//! - dispatch workflows (#989),
17//! - decide merge authority, or
18//! - land/merge a candidate onto a branch.
19//!
20//! # Design note — detached commits
21//!
22//! The issue spec names `commit_create_buffer`, but that primitive yields a
23//! commit *content buffer* (for signing flows) rather than a `CommitOid`. The
24//! return contract here is a real, addressable `CommitOid`, so we use
25//! [`git2::Repository::commit`] with `update_ref = None`, which writes the
26//! commit into the object database without updating any ref and without
27//! moving HEAD — satisfying the "detached commit does not move HEAD"
28//! acceptance criterion directly.
29
30use crate::errors::{Git2DBError, Git2DBResult};
31use git2::{Index, Oid, Repository, Tree};
32use std::fmt;
33
34/// Which side of a three-way merge a conflicted path belongs to.
35///
36/// A single [`Index`](git2::Index) conflict can carry entries on multiple
37/// sides (e.g. a modify/delete conflict has `Ours` and `Theirs` but no
38/// `Ancestor`), so one conflict typically yields several [`ConflictEntry`]
39/// records.
40#[derive(Debug, Clone, Copy, PartialEq, Eq)]
41pub enum ConflictSide {
42 /// The merge-base (common-ancestor) stage.
43 Ancestor,
44 /// The "ours" stage — the accumulator/tree we are merging into.
45 Ours,
46 /// The "their" stage — the head currently being incorporated.
47 Theirs,
48}
49
50impl fmt::Display for ConflictSide {
51 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
52 match self {
53 ConflictSide::Ancestor => f.write_str("ancestor"),
54 ConflictSide::Ours => f.write_str("ours"),
55 ConflictSide::Theirs => f.write_str("theirs"),
56 }
57 }
58}
59
60/// A single conflicted path entry captured from [`git2::Index::conflicts`].
61///
62/// Git paths are raw bytes (conventionally UTF-8, but not guaranteed to be),
63/// so the entry stores both the exact [`path_bytes`](Self::path_bytes) — used
64/// for identity/dedup — and a lossy [`path`](Self::path) display string.
65#[derive(Debug, Clone, PartialEq, Eq)]
66pub struct ConflictEntry {
67 /// Raw repository-relative path bytes, as libgit2 reports them.
68 pub path_bytes: Vec<u8>,
69 /// Lossy UTF-8 display form of [`path_bytes`](Self::path_bytes). Two
70 /// distinct non-UTF-8 paths may share this display string, so use
71 /// [`path_bytes`](Self::path_bytes) for identity comparisons.
72 pub path: String,
73 /// Which stage of the three-way merge this entry represents.
74 pub side: ConflictSide,
75}
76
77/// Structured capture of merge conflicts from an in-memory `merge_trees`.
78///
79/// Returned from [`CandidateComposer::merge_trees`] whenever the produced
80/// [`git2::Index`] carries conflict stages. This is the structured
81/// replacement for the string-only `"Merge conflicts detected"` error raised
82/// by the legacy in-place [`RepositoryHandle::merge`][super::RepositoryHandle].
83#[derive(Debug, Clone, Default)]
84pub struct ConflictReport {
85 /// One entry per (conflicted path, present side).
86 pub entries: Vec<ConflictEntry>,
87}
88
89impl ConflictReport {
90 /// Build a report by walking the conflict stages of an index.
91 ///
92 /// Pure read: does not mutate the index. Returns an empty report when the
93 /// index has no conflicts.
94 pub fn from_index(index: &Index) -> Git2DBResult<Self> {
95 let mut entries = Vec::new();
96 for conflict in index.conflicts().map_err(Git2DBError::from)? {
97 let conflict = conflict.map_err(Git2DBError::from)?;
98 if let Some(a) = conflict.ancestor {
99 entries.push(ConflictEntry {
100 path_bytes: a.path.clone(),
101 path: String::from_utf8_lossy(&a.path).into_owned(),
102 side: ConflictSide::Ancestor,
103 });
104 }
105 if let Some(o) = conflict.our {
106 entries.push(ConflictEntry {
107 path_bytes: o.path.clone(),
108 path: String::from_utf8_lossy(&o.path).into_owned(),
109 side: ConflictSide::Ours,
110 });
111 }
112 if let Some(t) = conflict.their {
113 entries.push(ConflictEntry {
114 path_bytes: t.path.clone(),
115 path: String::from_utf8_lossy(&t.path).into_owned(),
116 side: ConflictSide::Theirs,
117 });
118 }
119 }
120 Ok(Self { entries })
121 }
122
123 /// `true` when no conflicts were captured.
124 pub fn is_empty(&self) -> bool {
125 self.entries.is_empty()
126 }
127
128 /// Number of **distinct conflicted paths**.
129 ///
130 /// This is the meaningful "conflict count": a modify/modify conflict on
131 /// one file is one conflict, even though it contributes two stage entries
132 /// (`Ours` and `Theirs`). For the raw per-side entry count, use
133 /// [`entry_count`](Self::entry_count).
134 pub fn len(&self) -> usize {
135 self.paths().len()
136 }
137
138 /// Raw number of `(path, side)` entries captured — one per present stage,
139 /// so a single conflicted path typically counts as 2–3.
140 pub fn entry_count(&self) -> usize {
141 self.entries.len()
142 }
143
144 /// Iterate over the captured entries.
145 pub fn iter(&self) -> std::slice::Iter<'_, ConflictEntry> {
146 self.entries.iter()
147 }
148
149 /// Distinct conflicted paths' display strings, in first-seen order.
150 ///
151 /// Dedup is by raw [`ConflictEntry::path_bytes`], **not** the lossy
152 /// `path` string: two distinct non-UTF-8 git paths that happen to share
153 /// a lossy display string are counted separately (a `String`-keyed dedup
154 /// would undercount them). The returned display strings may therefore
155 /// contain visually-duplicate values; use
156 /// [`path_keys`](Self::path_keys) for exact byte identity.
157 pub fn paths(&self) -> Vec<&str> {
158 let mut seen_keys: Vec<&[u8]> = Vec::new();
159 let mut out: Vec<&str> = Vec::new();
160 for e in &self.entries {
161 if !seen_keys.contains(&e.path_bytes.as_slice()) {
162 seen_keys.push(e.path_bytes.as_slice());
163 out.push(e.path.as_str());
164 }
165 }
166 out
167 }
168
169 /// Distinct conflicted paths' raw byte keys, in first-seen order.
170 ///
171 /// This is the identity-stable view: two paths are the same path iff
172 /// their byte keys are equal, regardless of UTF-8 validity.
173 pub fn path_keys(&self) -> Vec<&[u8]> {
174 let mut seen: Vec<&[u8]> = Vec::new();
175 for e in &self.entries {
176 if !seen.contains(&e.path_bytes.as_slice()) {
177 seen.push(e.path_bytes.as_slice());
178 }
179 }
180 seen
181 }
182}
183
184impl fmt::Display for ConflictReport {
185 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
186 // Count distinct paths, not raw stage entries: one conflicted file is
187 // one conflict regardless of how many sides are present.
188 let paths = self.paths();
189 write!(f, "{} conflict(s)", paths.len())?;
190 for path in paths.iter().take(8) {
191 write!(f, "; {path}")?;
192 }
193 if paths.len() > 8 {
194 write!(f, "; …(+{} more)", paths.len() - 8)?;
195 }
196 Ok(())
197 }
198}
199
200impl std::error::Error for ConflictReport {}
201
202/// Result of an in-memory three-way tree merge.
203///
204/// `tree` is [`None`] when [`ConflictReport`] is non-empty — libgit2 refuses
205/// to write a tree from an index that still carries conflict stages.
206#[derive(Debug, Clone)]
207pub struct MergeTreesResult {
208 /// Materialised tree OID, present only for a clean (conflict-free) merge.
209 pub tree: Option<Oid>,
210 /// Structured conflict capture; empty for a clean merge.
211 pub conflicts: ConflictReport,
212}
213
214impl MergeTreesResult {
215 /// `true` if the merge produced any conflicts.
216 pub fn has_conflicts(&self) -> bool {
217 !self.conflicts.is_empty()
218 }
219}
220
221/// A detached candidate commit + its tree, produced by
222/// [`CandidateComposer::compose_candidate`].
223///
224/// The commit lives in the object database but is referenced by no ref; HEAD
225/// is unchanged. Callers land the candidate explicitly (out of scope here).
226#[derive(Debug, Clone, Copy)]
227pub struct Candidate {
228 /// OID of the detached commit object.
229 pub commit: Oid,
230 /// OID of the candidate's tree.
231 pub tree: Oid,
232}
233
234/// In-memory, HEAD-preserving merge composition.
235///
236/// Wraps a borrowed [`git2::Repository`] and exposes the small surface needed
237/// to compose sequential merge candidates without mutating HEAD or the working
238/// tree. Obtain a `&Repository` via the existing escape hatch
239/// ([`RepositoryHandle::open_repo`][super::RepositoryHandle::open_repo]) and
240/// construct a composer over it:
241///
242/// ```rust,no_run
243/// # use git2db::merge::CandidateComposer;
244/// # fn example(
245/// # repo: &git2::Repository,
246/// # oid_a: git2::Oid,
247/// # oid_b: git2::Oid,
248/// # ) -> Result<(), Box<dyn std::error::Error>> {
249/// let composer = CandidateComposer::new(repo);
250/// let mb = composer.merge_base(oid_a, oid_b)?;
251/// # Ok(())
252/// # }
253/// ```
254pub struct CandidateComposer<'a> {
255 repo: &'a Repository,
256}
257
258impl<'a> CandidateComposer<'a> {
259 /// Wrap a borrowed repository.
260 pub fn new(repo: &'a Repository) -> Self {
261 Self { repo }
262 }
263
264 /// Compute the best common ancestor of two commits (`git merge-base`).
265 ///
266 /// Thin, pure-read wrapper over [`git2::Repository::merge_base`]. Returns
267 /// [`Git2DBError::InvalidOperation`] when the two commits share no history
268 /// (libgit2's `NotFound`), matching the "no common ancestor" semantics of
269 /// [`merge_bases`](Self::merge_bases).
270 pub fn merge_base(&self, one: Oid, two: Oid) -> Git2DBResult<Oid> {
271 match self.repo.merge_base(one, two) {
272 Ok(oid) => Ok(oid),
273 Err(e) if e.code() == git2::ErrorCode::NotFound => Err(Git2DBError::invalid_operation(
274 format!("no merge base found for {one} and {two} (unrelated histories)"),
275 )),
276 Err(e) => Err(Git2DBError::internal(format!("merge_base failed: {e}"))),
277 }
278 }
279
280 /// Compute all merge bases of two commits (`git merge-base --all`).
281 ///
282 /// Thin, pure-read wrapper over [`git2::Repository::merge_bases`]. Returns
283 /// an empty `Vec` when the commits share no history (libgit2's `NotFound`
284 /// is mapped to the empty set, since "no common ancestor" is a well-defined
285 /// answer rather than an error here).
286 pub fn merge_bases(&self, one: Oid, two: Oid) -> Git2DBResult<Vec<Oid>> {
287 match self.repo.merge_bases(one, two) {
288 Ok(arr) => Ok(arr.iter().copied().collect()),
289 Err(e) if e.code() == git2::ErrorCode::NotFound => Ok(Vec::new()),
290 Err(e) => Err(Git2DBError::internal(format!("merge_bases failed: {e}"))),
291 }
292 }
293
294 /// Three-way merge of trees, fully in memory.
295 ///
296 /// Wraps [`git2::Repository::merge_trees`] → [`git2::Index`] → tree OID.
297 /// On conflict, `tree` is [`None`] and `conflicts` carries a structured
298 /// [`ConflictReport`] (path + side), replacing the legacy string-only
299 /// `"Merge conflicts detected"` error.
300 ///
301 /// Neither HEAD nor the working tree is touched.
302 pub fn merge_trees(
303 &self,
304 ancestor: &Tree<'_>,
305 ours: &Tree<'_>,
306 theirs: &Tree<'_>,
307 ) -> Git2DBResult<MergeTreesResult> {
308 let mut index = self
309 .repo
310 .merge_trees(ancestor, ours, theirs, None)
311 .map_err(|e| Git2DBError::internal(format!("merge_trees failed: {e}")))?;
312 let conflicts = ConflictReport::from_index(&index)?;
313 let tree = if conflicts.is_empty() {
314 // `write_tree_to` materialises against the owning repo's object
315 // database — the in-memory index from `merge_trees` is not the
316 // repo's working index, so be explicit about the destination.
317 Some(
318 index
319 .write_tree_to(self.repo)
320 .map_err(|e| Git2DBError::internal(format!("write_tree failed: {e}")))?,
321 )
322 } else {
323 None
324 };
325 Ok(MergeTreesResult { tree, conflicts })
326 }
327
328 /// Deterministically compose a sequential candidate from `base` + `heads`.
329 ///
330 /// Performs an octopus-style cumulative merge: starting from `base`'s tree
331 /// as the accumulator, each head is folded in with a three-way
332 /// `merge_trees` step whose **ancestor is the merge base of the
333 /// accumulator and the head** — `merge_base(current_tip, head)` — not
334 /// `merge_base(base, head)`. Folding against the *evolving* accumulator
335 /// (not a fixed `base`) is what keeps a stacked head (one built on top of
336 /// an earlier head) from producing a false add/add conflict, and keeps a
337 /// revert head from silently losing its revert: the ancestor reflects
338 /// what the head actually diverged from given everything folded so far.
339 ///
340 /// To give git a commit to resolve `merge_base` against mid-fold, each
341 /// step anchors an **unreachable intermediate commit** (no ref) over the
342 /// accumulated tree; the next iteration resolves its merge base from that
343 /// tip. The returned candidate is the final **octopus** commit with
344 /// parents `[base, ...heads]` — the intermediates are scaffolding only.
345 ///
346 /// Because each `merge_trees` step is a pure function of its three trees,
347 /// the resulting tree OID is stable across reruns for the same inputs.
348 ///
349 /// # Errors
350 ///
351 /// Returns [`Git2DBError::MergeConflictReport`] if any step conflicts,
352 /// carrying the structured [`ConflictReport`] for that step. Returns
353 /// [`Git2DBError::InvalidOperation`] if `heads` is empty, if `base`
354 /// appears in `heads`, or if a head shares no merge base with the
355 /// accumulator (unrelated history).
356 ///
357 /// # Garbage collection
358 ///
359 /// Each fold step writes an unreachable intermediate commit, and the
360 /// returned candidate is detached (referenced by no ref). All become
361 /// GC-eligible under git's default prune window unless the caller lands
362 /// the candidate onto a ref.
363 ///
364 /// # Duplicate heads
365 ///
366 /// Folding the same head twice is harmless: the second fold's
367 /// `merge_base(current_tip, head)` resolves to `head` (already absorbed),
368 /// so `merge_trees` is a no-op. Callers need not deduplicate.
369 pub fn compose_candidate(
370 &self,
371 base: Oid,
372 heads: &[Oid],
373 message: &str,
374 ) -> Git2DBResult<Candidate> {
375 if heads.is_empty() {
376 return Err(Git2DBError::invalid_operation(
377 "compose_candidate requires at least one head",
378 ));
379 }
380 if heads.contains(&base) {
381 return Err(Git2DBError::invalid_operation(
382 "compose_candidate: base must not appear in heads",
383 ));
384 }
385
386 let base_commit = self.commit_of(base)?;
387 let mut accumulator = base_commit.tree()?;
388 let sig = self.signature_or_fallback()?;
389
390 // `current_tip` is the evolving accumulator's commit identity. It
391 // starts at `base` and is updated to an unreachable intermediate
392 // commit after each head so the NEXT head's merge-base resolves
393 // against the accumulated state, not against `base`.
394 let mut current_tip = base;
395 let mut head_commits: Vec<git2::Commit<'a>> = Vec::with_capacity(heads.len());
396
397 for &h in heads {
398 let head_commit = self.commit_of(h)?;
399 let head_tree = head_commit.tree()?;
400
401 // Merge base of the *current accumulator* and this head. This is
402 // the fix for stacked/revert heads: resolving against the evolved
403 // accumulator (not `base`) avoids false conflicts and lost reverts.
404 // A NotFound (unrelated history) surfaces as InvalidOperation.
405 let ancestor_oid = self.merge_base(current_tip, h)?;
406 let ancestor_tree = self.tree_of(ancestor_oid)?;
407
408 let step = self.merge_trees(&ancestor_tree, &accumulator, &head_tree)?;
409 let merged_tree = match step.tree {
410 Some(t) => t,
411 None => return Err(Git2DBError::MergeConflictReport(step.conflicts)),
412 };
413 accumulator = self
414 .repo
415 .find_tree(merged_tree)
416 .map_err(Git2DBError::from)?;
417
418 // Anchor an unreachable intermediate commit so the next iteration
419 // can resolve merge_base against the evolved accumulator. Parents
420 // = [current_tip, head] reflect the true merge ancestry.
421 let tip_commit = self.commit_of(current_tip)?;
422 let inter_parents = [&tip_commit, &head_commit];
423 current_tip = self
424 .repo
425 .commit(
426 None,
427 &sig,
428 &sig,
429 "git2db-merge: intermediate (unreachable)",
430 &accumulator,
431 &inter_parents,
432 )
433 .map_err(|e| Git2DBError::internal(format!("intermediate commit failed: {e}")))?;
434
435 head_commits.push(head_commit);
436 }
437
438 // Final octopus commit: parents = [base, ...heads]. update_ref = None
439 // → no ref update, HEAD unchanged. base as first parent makes the
440 // candidate a descendant of base (fast-forwardable).
441 let mut parents: Vec<&git2::Commit<'_>> = Vec::with_capacity(head_commits.len() + 1);
442 parents.push(&base_commit);
443 for hc in &head_commits {
444 parents.push(hc);
445 }
446 let commit_oid = self
447 .repo
448 .commit(None, &sig, &sig, message, &accumulator, &parents)
449 .map_err(|e| Git2DBError::internal(format!("detached commit failed: {e}")))?;
450
451 Ok(Candidate {
452 commit: commit_oid,
453 tree: accumulator.id(),
454 })
455 }
456
457 /// Resolve a signature for candidate/intermediate commits, falling back to
458 /// a static identity when the repo has no configured git identity (e.g. a
459 /// fresh test repository). The fallback uses `Signature::now`, so its
460 /// timestamp is **not** stable across runs — but it only affects commit
461 /// OIDs, never tree OIDs (which are content-addressed and deterministic).
462 fn signature_or_fallback(&self) -> Git2DBResult<git2::Signature<'static>> {
463 self.repo
464 .signature()
465 .or_else(|_| git2::Signature::now("git2db-merge", "git2db@local"))
466 .map_err(|e| Git2DBError::internal(format!("signature resolution failed: {e}")))
467 }
468
469 fn tree_of(&self, oid: Oid) -> Git2DBResult<Tree<'a>> {
470 self.repo
471 .find_tree(oid)
472 .or_else(|_| {
473 // Treat `oid` as a commit-ish and peel to its tree.
474 let commit = self.repo.find_commit(oid)?;
475 commit.tree()
476 })
477 .map_err(|e| {
478 Git2DBError::reference(oid.to_string(), format!("not a tree or commit OID: {e}"))
479 })
480 }
481
482 fn commit_of(&self, oid: Oid) -> Git2DBResult<git2::Commit<'a>> {
483 self.repo
484 .find_commit(oid)
485 .map_err(|e| Git2DBError::reference(oid.to_string(), format!("not a commit: {e}")))
486 }
487}
488
489#[cfg(test)]
490mod tests {
491 //! Internal sanity tests; the causal acceptance suite lives in
492 //! `tests/merge.rs`.
493
494 use super::*;
495
496 #[test]
497 fn conflict_report_default_is_empty() {
498 let r = ConflictReport::default();
499 assert!(r.is_empty());
500 assert_eq!(r.len(), 0);
501 assert!(r.paths().is_empty());
502 assert!(r.path_keys().is_empty());
503 }
504
505 /// Helper: build an entry from raw path bytes (lossy display derived).
506 fn entry(bytes: &[u8], side: ConflictSide) -> ConflictEntry {
507 ConflictEntry {
508 path_bytes: bytes.to_vec(),
509 path: String::from_utf8_lossy(bytes).into_owned(),
510 side,
511 }
512 }
513
514 #[test]
515 fn conflict_report_paths_dedups() {
516 let r = ConflictReport {
517 entries: vec![
518 entry(b"a", ConflictSide::Ours),
519 entry(b"a", ConflictSide::Theirs),
520 entry(b"b", ConflictSide::Ours),
521 ],
522 };
523 // len() counts distinct conflicted paths (2), not stage entries (3).
524 assert_eq!(r.len(), 2);
525 assert_eq!(r.entry_count(), 3);
526 assert_eq!(r.paths(), vec!["a", "b"]);
527 assert_eq!(r.path_keys(), vec![b"a".as_slice(), b"b".as_slice()]);
528 }
529
530 #[test]
531 fn conflict_report_dedups_by_raw_bytes_not_lossy_string() {
532 // Two distinct non-UTF-8 byte paths that both lossy-convert to the
533 // same display string (one U+FFFD). A String-keyed dedup would
534 // collapse them and undercount; byte-keyed dedup keeps them apart.
535 let lossy_a = String::from_utf8_lossy(b"\x80").into_owned();
536 let lossy_b = String::from_utf8_lossy(b"\xfe").into_owned();
537 assert_eq!(
538 lossy_a, lossy_b,
539 "test precondition: both lossy strings must be equal"
540 );
541 let r = ConflictReport {
542 entries: vec![
543 entry(b"\x80", ConflictSide::Ours),
544 entry(b"\xfe", ConflictSide::Theirs),
545 ],
546 };
547 assert_eq!(
548 r.len(),
549 2,
550 "distinct raw-byte paths must not collide via the lossy String"
551 );
552 assert_eq!(r.entry_count(), 2);
553 assert_eq!(r.path_keys().len(), 2);
554 // paths() returns one display representative per distinct byte key,
555 // so its length matches the byte-keyed count even though the two
556 // display strings are visually identical.
557 assert_eq!(r.paths().len(), 2);
558 }
559
560 #[test]
561 fn conflict_side_display() {
562 assert_eq!(ConflictSide::Ancestor.to_string(), "ancestor");
563 assert_eq!(ConflictSide::Ours.to_string(), "ours");
564 assert_eq!(ConflictSide::Theirs.to_string(), "theirs");
565 }
566}