Skip to main content

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}