gunnar_server/

merge_engine.rs

//! **Gunnar's merge engine** (GUN-MERGE-ENGINE, 2026-11-01): the three-way merge a pull
//! request needs when its branch does not descend from its target.
//!
//! Until this module, `PullRequests.Merge` could only fast-forward, and a pull request
//! whose branch had fallen behind its target was refused with "gunnar has no merge engine
//! yet". This is that engine, and it is deliberately small:
//!
//! * **The merge base** ([`merge_base`]): git's own "paint down to common" walk, ordered by
//!   committer time, with redundant candidates removed. A criss-cross history (more than
//!   one best base) and unrelated histories are refused by name rather than guessed at;
//!   git answers the first with a recursive virtual base, which is a merge of merges and
//!   belongs on a person's machine.
//! * **The tree merge** ([`Merger::merge_trees`]): per path, the side that changed wins;
//!   where both changed a regular file, the file is merged by line ([`merge_text`]); where
//!   both changed anything else differently (modify/delete, file/directory, a symlink, a
//!   submodule, an add/add of different content, a binary file) the path is a **conflict**.
//!   Every conflict is collected, so a refusal names all of them at once.
//! * **The line merge** ([`merge_text`]): diff3 over [`crate::diff::diff_ops`], the same
//!   Myers walk `Refs.Diff` and blame use (one implementation). Changes from the two sides
//!   that overlap or touch are a conflict unless both sides made the same change: the
//!   conservative reading, never a guess.
//!
//! # Why it is written here, not taken from `gix-merge`
//!
//! `gix-merge` has a tree merge, and the serving tier links no gix porcelain: the engine
//! seam (`xtask/src/engine_seam.rs`) keeps `gix`, `gix-object` and their tail out of
//! `gunnar-server`, and `gix-merge` would bring `gix-diff`, `gix-filter`, `gix-worktree`
//! and more back into the appliance. Everything a merge needs from a repository is
//! `GitServe::read`, which every engine has; the objects it makes are git's own formats,
//! written as one pack through the same `put_pack` a push lands through.
//!
//! **Nothing is written by this module.** It answers objects in memory ([`NewObjects`]);
//! the control plane decides whether they are stored, after every gate has run over them
//! through [`Overlay`].

use std::collections::{BTreeMap, BinaryHeap, HashMap, HashSet};

use gix_hash::{Kind as HashKind, ObjectId};
use gunnar_store::git_storage_trait::{
    self as gst, Caps, GcReport, GitOps, GitServe, ObjType, PackStats, ReachSet, RefCas, RefRow,
    RefUpdate, Stored, TxId,
};
use gunnar_store::object::{self, TreeIter};

/// The largest file the line merge reads, per side. Past it the path is a conflict: a
/// line merge of a 16 MiB file is not something a person reviewed line by line either.
pub const MAX_TEXT_MERGE_BYTES: usize = 16 * 1024 * 1024;

/// How many trees and blobs one merge may read before it stops and refuses. Large enough
/// for any honest repository's changed paths (only differing subtrees are opened), small
/// enough that a crafted history cannot keep a control-plane call busy for minutes.
pub const MAX_OBJECT_READS: usize = 500_000;

/// git's `S_IFMT` mask and the four formats a tree entry can have.
const IFMT: u32 = 0o170000;
const IFDIR: u32 = 0o040000;
const IFREG: u32 = 0o100000;

/// A failure that is not a conflict: an object missing, a budget hit, a decode error.
/// The control plane refuses on it, never merges.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct EngineError(pub String);

impl std::fmt::Display for EngineError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.write_str(&self.0)
    }
}

type Result<T> = std::result::Result<T, EngineError>;

fn err(what: impl Into<String>) -> EngineError {
    EngineError(what.into())
}

/// One path both sides changed in a way gunnar will not merge, and why.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Conflict {
    /// The path from the repository root, `/`-separated (lossy UTF-8).
    pub path: String,
    /// One short phrase: "both sides changed the same lines", "deleted on one side,
    /// changed on the other", …
    pub why: &'static str,
}

impl std::fmt::Display for Conflict {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{} ({})", self.path, self.why)
    }
}

/// The objects a merge made, in memory, in the order they must be stored (blobs and
/// trees before the commit that names them). Ids already in the repository are skipped
/// by the writer, not here.
#[derive(Debug, Default)]
pub struct NewObjects {
    order: Vec<ObjectId>,
    objects: HashMap<Vec<u8>, (ObjType, Vec<u8>)>,
}

impl NewObjects {
    fn add(&mut self, hash: HashKind, kind: ObjType, content: Vec<u8>) -> Result<ObjectId> {
        let id = crate::first_commit::object_id(hash, word(kind), &content).map_err(err)?;
        if !self.objects.contains_key(id.as_bytes()) {
            self.order.push(id);
            self.objects.insert(id.as_bytes().to_vec(), (kind, content));
        }
        Ok(id)
    }

    /// One object by id, if this merge made it.
    pub fn get(&self, id: &[u8]) -> Option<&(ObjType, Vec<u8>)> {
        self.objects.get(id)
    }

    /// How many objects the merge made.
    pub fn len(&self) -> usize {
        self.order.len()
    }

    /// Whether the merge made none (a fast-forward, or a result that is a side's tree).
    pub fn is_empty(&self) -> bool {
        self.order.is_empty()
    }

    /// The objects as one version-2 pack in `hash`, leaving out every id `git` already
    /// holds. `None` when nothing is new.
    pub fn pack(&self, hash: HashKind, git: &dyn GitServe) -> Result<Option<Vec<u8>>> {
        let mut items: Vec<(u8, &[u8])> = Vec::new();
        for id in &self.order {
            if git
                .has(id.as_bytes())
                .map_err(|e| err(format!("asking the store for {id}: {e:#}")))?
            {
                continue;
            }
            let (kind, content) = &self.objects[id.as_bytes()];
            items.push((kind.code(), content));
        }
        if items.is_empty() {
            return Ok(None);
        }
        crate::first_commit::pack_of(hash, &items)
            .map(Some)
            .map_err(err)
    }
}

fn word(kind: ObjType) -> &'static str {
    match kind {
        ObjType::Commit => "commit",
        ObjType::Tree => "tree",
        ObjType::Tag => "tag",
        _ => "blob",
    }
}

fn hex(id: &ObjectId) -> String {
    id.to_hex().to_string()
}

/// Read one object, as the type the caller expects.
fn read_as(git: &dyn GitServe, id: &ObjectId, want: ObjType) -> Result<Vec<u8>> {
    match git.read(id.as_bytes()) {
        Ok(Some((kind, bytes))) if kind == want => Ok(bytes),
        Ok(Some((kind, _))) => Err(err(format!(
            "{} is a {kind:?}, not the {want:?} the merge expected",
            hex(id)
        ))),
        Ok(None) => Err(err(format!("{} is not in the repository", hex(id)))),
        Err(e) => Err(err(format!("reading {}: {e:#}", hex(id)))),
    }
}

/// A commit's parents and committer time.
fn commit_facts(git: &dyn GitServe, hash: HashKind, id: &ObjectId) -> Result<(Vec<ObjectId>, i64)> {
    let bytes = read_as(git, id, ObjType::Commit)?;
    let mut parents = Vec::new();
    let (_, at) = object::commit_facts(&bytes, hash, &mut parents)
        .map_err(|e| err(format!("decoding commit {}: {e}", hex(id))))?;
    Ok((parents, at))
}

/// A commit's root tree.
pub fn commit_tree(git: &dyn GitServe, hash: HashKind, id: &ObjectId) -> Result<ObjectId> {
    let bytes = read_as(git, id, ObjType::Commit)?;
    let mut parents = Vec::new();
    object::commit_links(&bytes, hash, &mut parents)
        .map_err(|e| err(format!("decoding commit {}: {e}", hex(id))))
}

// ───────────────────────────── the merge base ────────────────────────────────

const P1: u8 = 1;
const P2: u8 = 2;
const STALE: u8 = 4;
const RESULT: u8 = 8;

/// **The one best common ancestor of `a` and `b`** — `git merge-base a b`, refusing where
/// git would have to invent a virtual base.
///
/// git's paint walk: `a` is painted P1, `b` P2, commits are taken newest first and pass
/// their paint to their parents; a commit holding both paints is a candidate, and its
/// ancestors are painted STALE so the walk stops below it. Candidates that turn out to be
/// ancestors of other candidates are dropped.
///
/// # Errors
///
/// No common ancestor (unrelated histories), more than one best one (criss-cross), a
/// commit missing, or more than `budget` commits walked: each by name.
pub fn merge_base(
    git: &dyn GitServe,
    hash: HashKind,
    a: &ObjectId,
    b: &ObjectId,
    budget: usize,
) -> Result<ObjectId> {
    if a == b {
        return Ok(*a);
    }
    let mut flags: HashMap<ObjectId, u8> = HashMap::new();
    let mut queue: BinaryHeap<(i64, ObjectId)> = BinaryHeap::new();
    let mut facts: HashMap<ObjectId, (Vec<ObjectId>, i64)> = HashMap::new();
    let load =
        |id: &ObjectId, facts: &mut HashMap<ObjectId, (Vec<ObjectId>, i64)>| -> Result<i64> {
            if let Some((_, at)) = facts.get(id) {
                return Ok(*at);
            }
            let f = commit_facts(git, hash, id)?;
            let at = f.1;
            facts.insert(*id, f);
            Ok(at)
        };
    for (id, paint) in [(a, P1), (b, P2)] {
        let at = load(id, &mut facts)?;
        *flags.entry(*id).or_default() |= paint;
        queue.push((at, *id));
    }
    let mut results: Vec<ObjectId> = Vec::new();
    let mut walked = 0usize;
    while queue
        .iter()
        .any(|(_, id)| flags.get(id).copied().unwrap_or(0) & STALE == 0)
    {
        let Some((_, id)) = queue.pop() else { break };
        walked += 1;
        if walked > budget {
            return Err(err(format!(
                "the merge base of {} and {} is more than {budget} commits away; refusing \
                 rather than walking further",
                hex(a),
                hex(b)
            )));
        }
        let mut paint = flags[&id] & (P1 | P2 | STALE);
        if paint == P1 | P2 {
            if flags[&id] & RESULT == 0 {
                *flags.get_mut(&id).expect("painted") |= RESULT;
                results.push(id);
            }
            paint |= STALE;
        }
        load(&id, &mut facts)?;
        let parents = facts[&id].0.clone();
        for parent in parents {
            let have = flags.get(&parent).copied().unwrap_or(0);
            if have & paint == paint {
                continue;
            }
            let at = load(&parent, &mut facts)?;
            *flags.entry(parent).or_default() |= paint;
            queue.push((at, parent));
        }
    }
    // A candidate later painted STALE sits below another candidate.
    results.retain(|id| flags[id] & STALE == 0);
    let mut best: Vec<ObjectId> = Vec::new();
    for candidate in &results {
        let redundant = results.iter().any(|other| {
            other != candidate
                && gunnar_policy::ancestry::is_descendant_of(git, other, candidate, budget)
                    .unwrap_or(false)
        });
        if !redundant {
            best.push(*candidate);
        }
    }
    match best.as_slice() {
        [] => Err(err(format!(
            "{} and {} share no history: there is no merge base to merge from",
            hex(a),
            hex(b)
        ))),
        [one] => Ok(*one),
        many => Err(err(format!(
            "{} and {} have {} best merge bases ({}): a criss-cross history, which gunnar \
             does not merge on the server — merge locally and push the result",
            hex(a),
            hex(b),
            many.len(),
            many.iter()
                .map(|id| hex(id)[..12].to_owned())
                .collect::<Vec<_>>()
                .join(", ")
        ))),
    }
}

// ───────────────────────────── the tree merge ────────────────────────────────

/// One tree entry: its raw mode and the object it names.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Ent {
    mode: u32,
    oid: ObjectId,
}

impl Ent {
    fn is_tree(&self) -> bool {
        self.mode & IFMT == IFDIR
    }
    fn is_regular(&self) -> bool {
        self.mode & IFMT == IFREG
    }
}

/// What a tree merge answers.
#[derive(Debug)]
pub enum TreeMerge {
    /// The merged root tree; its new objects are in the [`Merger`].
    Clean(ObjectId),
    /// Every path that conflicts. Nothing to store.
    Conflicts(Vec<Conflict>),
}

/// The tree merge over one repository.
pub struct Merger<'a> {
    git: &'a dyn GitServe,
    hash: HashKind,
    /// Whether the repository is encrypted: its blobs are ciphertext, and a line merge
    /// of ciphertext is garbage, so a both-sides content change is a conflict there.
    encrypted: bool,
    /// What the merge made.
    pub new: NewObjects,
    conflicts: Vec<Conflict>,
    reads: usize,
}

impl<'a> Merger<'a> {
    /// A merger over `git`, in `hash`.
    pub fn new(git: &'a dyn GitServe, hash: HashKind, encrypted: bool) -> Self {
        Merger {
            git,
            hash,
            encrypted,
            new: NewObjects::default(),
            conflicts: Vec::new(),
            reads: 0,
        }
    }

    fn read(&mut self, id: &ObjectId, want: ObjType) -> Result<Vec<u8>> {
        self.reads += 1;
        if self.reads > MAX_OBJECT_READS {
            return Err(err(format!(
                "the merge read more than {MAX_OBJECT_READS} objects; refusing rather than \
                 reading further"
            )));
        }
        read_as(self.git, id, want)
    }

    fn entries(&mut self, tree: Option<&ObjectId>) -> Result<BTreeMap<Vec<u8>, Ent>> {
        let mut out = BTreeMap::new();
        let Some(tree) = tree else { return Ok(out) };
        let bytes = self.read(tree, ObjType::Tree)?;
        for entry in TreeIter::from_bytes(&bytes, self.hash).named() {
            let entry = entry.map_err(|e| err(format!("decoding tree {}: {e}", hex(tree))))?;
            out.insert(
                entry.name.to_vec(),
                Ent {
                    mode: entry.mode,
                    oid: entry.oid,
                },
            );
        }
        Ok(out)
    }

    /// Write a tree of `entries` (git's order: a subtree sorts as its name plus `/`).
    /// `None` for an empty subtree, which git does not keep.
    fn write_tree(&mut self, entries: &BTreeMap<Vec<u8>, Ent>) -> Result<ObjectId> {
        let mut sorted: Vec<(Vec<u8>, &Ent)> = entries
            .iter()
            .map(|(name, ent)| {
                let mut key = name.clone();
                if ent.is_tree() {
                    key.push(b'/');
                }
                (key, ent)
            })
            .collect();
        sorted.sort_by(|a, b| a.0.cmp(&b.0));
        let mut body = Vec::new();
        for (key, ent) in sorted {
            let name = if ent.is_tree() {
                &key[..key.len() - 1]
            } else {
                &key[..]
            };
            let mode = if ent.is_tree() { IFDIR } else { ent.mode };
            body.extend_from_slice(format!("{mode:o} ").as_bytes());
            body.extend_from_slice(name);
            body.push(0);
            body.extend_from_slice(ent.oid.as_bytes());
        }
        self.new.add(self.hash, ObjType::Tree, body)
    }

    /// **Merge `theirs` into `ours` over `base`** (root trees). `base` is `None` for an
    /// add/add of a whole directory.
    pub fn merge_trees(
        &mut self,
        base: Option<&ObjectId>,
        ours: &ObjectId,
        theirs: &ObjectId,
    ) -> Result<TreeMerge> {
        let root = self.merge_dir(base, Some(ours), Some(theirs), "")?;
        if !self.conflicts.is_empty() {
            return Ok(TreeMerge::Conflicts(std::mem::take(&mut self.conflicts)));
        }
        let root = match root {
            Some(id) => id,
            None => self.write_tree(&BTreeMap::new())?,
        };
        Ok(TreeMerge::Clean(root))
    }

    fn conflict(&mut self, path: String, why: &'static str) {
        self.conflicts.push(Conflict { path, why });
    }

    /// Merge one directory; `None` when the result is empty.
    fn merge_dir(
        &mut self,
        base: Option<&ObjectId>,
        ours: Option<&ObjectId>,
        theirs: Option<&ObjectId>,
        prefix: &str,
    ) -> Result<Option<ObjectId>> {
        let b = self.entries(base)?;
        let o = self.entries(ours)?;
        let t = self.entries(theirs)?;
        let names: std::collections::BTreeSet<&Vec<u8>> =
            b.keys().chain(o.keys()).chain(t.keys()).collect();
        let mut out: BTreeMap<Vec<u8>, Ent> = BTreeMap::new();
        for name in names {
            let path = if prefix.is_empty() {
                String::from_utf8_lossy(name).into_owned()
            } else {
                format!("{prefix}/{}", String::from_utf8_lossy(name))
            };
            let (be, oe, te) = (
                b.get(name).copied(),
                o.get(name).copied(),
                t.get(name).copied(),
            );
            if let Some(ent) = self.merge_entry(be, oe, te, &path)? {
                out.insert(name.clone(), ent);
            }
        }
        if out.is_empty() {
            return Ok(None);
        }
        // A directory that came out exactly as one side had it is that side's tree.
        if ours.is_some() && out == o {
            return Ok(ours.copied());
        }
        if theirs.is_some() && out == t {
            return Ok(theirs.copied());
        }
        self.write_tree(&out).map(Some)
    }

    fn merge_entry(
        &mut self,
        b: Option<Ent>,
        o: Option<Ent>,
        t: Option<Ent>,
        path: &str,
    ) -> Result<Option<Ent>> {
        // The side that changed wins; both the same is that.
        if o == t {
            return Ok(o);
        }
        if b == o {
            return Ok(t);
        }
        if b == t {
            return Ok(o);
        }
        // Both changed, differently.
        match (b, o, t) {
            (b, Some(o), Some(t)) if o.is_tree() && t.is_tree() => {
                let base = b.filter(Ent::is_tree).map(|e| e.oid);
                if b.is_some() && base.is_none() {
                    self.conflict(
                        path.to_owned(),
                        "a file on one side became a directory on both",
                    );
                    return Ok(Some(o));
                }
                let merged = self.merge_dir(base.as_ref(), Some(&o.oid), Some(&t.oid), path)?;
                Ok(merged.map(|oid| Ent { mode: IFDIR, oid }))
            }
            (Some(b), Some(o), Some(t)) if b.is_regular() && o.is_regular() && t.is_regular() => {
                let mode = if o.mode == t.mode || b.mode == t.mode {
                    o.mode
                } else if b.mode == o.mode {
                    t.mode
                } else {
                    self.conflict(path.to_owned(), "both sides changed the file mode");
                    return Ok(Some(o));
                };
                if o.oid == t.oid {
                    return Ok(Some(Ent { mode, oid: o.oid }));
                }
                if b.oid == o.oid {
                    return Ok(Some(Ent { mode, oid: t.oid }));
                }
                if b.oid == t.oid {
                    return Ok(Some(Ent { mode, oid: o.oid }));
                }
                if self.encrypted {
                    self.conflict(
                        path.to_owned(),
                        "both sides changed an encrypted file, which the server cannot read",
                    );
                    return Ok(Some(o));
                }
                let base = self.read(&b.oid, ObjType::Blob)?;
                let ours = self.read(&o.oid, ObjType::Blob)?;
                let theirs = self.read(&t.oid, ObjType::Blob)?;
                match merge_text(&base, &ours, &theirs) {
                    Ok(merged) => {
                        let oid = self.new.add(self.hash, ObjType::Blob, merged)?;
                        Ok(Some(Ent { mode, oid }))
                    }
                    Err(why) => {
                        self.conflict(path.to_owned(), why.phrase());
                        Ok(Some(o))
                    }
                }
            }
            (None, Some(_), Some(_)) => {
                self.conflict(
                    path.to_owned(),
                    "added on both sides with different content",
                );
                Ok(o)
            }
            (Some(_), None, Some(_)) | (Some(_), Some(_), None) => {
                self.conflict(path.to_owned(), "deleted on one side, changed on the other");
                Ok(o)
            }
            (_, Some(o), Some(t)) if o.is_tree() != t.is_tree() => {
                self.conflict(
                    path.to_owned(),
                    "a file on one side, a directory on the other",
                );
                Ok(Some(o))
            }
            _ => {
                self.conflict(
                    path.to_owned(),
                    "both sides changed it, and it is not a regular file (a symlink, a \
                     submodule or a type change)",
                );
                Ok(o)
            }
        }
    }
}

// ───────────────────────────── the line merge ────────────────────────────────

/// Why a file could not be merged by line.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum TextConflict {
    /// Both sides changed the same (or touching) lines differently.
    Overlap,
    /// One of the three versions is binary.
    Binary,
    /// One of the three is larger than [`MAX_TEXT_MERGE_BYTES`].
    TooLarge,
}

impl TextConflict {
    /// The phrase a conflict list shows.
    pub fn phrase(self) -> &'static str {
        match self {
            TextConflict::Overlap => "both sides changed the same lines",
            TextConflict::Binary => "both sides changed a binary file",
            TextConflict::TooLarge => "both sides changed a file too large to merge by line",
        }
    }
}

/// One changed region of a side against the base: base lines `b0..b1` became side lines
/// `s0..s1`.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Hunk {
    b0: usize,
    b1: usize,
    s0: usize,
    s1: usize,
}

fn split_keep(bytes: &[u8]) -> Vec<&[u8]> {
    bytes.split_inclusive(|b| *b == b'\n').collect()
}

/// The hunks that turn `base` into `side`. Common prefix and suffix are stripped first, so
/// a small change to a large file is a small Myers walk.
fn hunks(base: &[&[u8]], side: &[&[u8]]) -> Vec<Hunk> {
    let mut start = 0;
    while start < base.len() && start < side.len() && base[start] == side[start] {
        start += 1;
    }
    let mut end = 0;
    while end < base.len() - start
        && end < side.len() - start
        && base[base.len() - 1 - end] == side[side.len() - 1 - end]
    {
        end += 1;
    }
    let (bm, sm) = (
        &base[start..base.len() - end],
        &side[start..side.len() - end],
    );
    if bm.is_empty() && sm.is_empty() {
        return Vec::new();
    }
    let mut out: Vec<Hunk> = Vec::new();
    let (mut bi, mut si) = (0usize, 0usize);
    let flush = |bi: usize, b_to: usize, si: usize, s_to: usize, out: &mut Vec<Hunk>| {
        if bi < b_to || si < s_to {
            out.push(Hunk {
                b0: start + bi,
                b1: start + b_to,
                s0: start + si,
                s1: start + s_to,
            });
        }
    };
    for op in crate::diff::diff_ops(bm, sm) {
        if let crate::diff::Op::Equal { old, new, count } = op {
            flush(bi, old, si, new, &mut out);
            bi = old + count;
            si = new + count;
        }
    }
    flush(bi, bm.len(), si, sm.len(), &mut out);
    out
}

/// **diff3**: merge `theirs` into `ours` over `base`, line by line.
///
/// Regions only one side changed take that side; regions both changed take the change
/// when both made the same one, and are an [`TextConflict::Overlap`] otherwise. Two
/// changes that merely *touch* (one ends where the other begins) are an overlap too:
/// that is git's reading as well, and the safe one.
pub fn merge_text(
    base: &[u8],
    ours: &[u8],
    theirs: &[u8],
) -> std::result::Result<Vec<u8>, TextConflict> {
    if [base, ours, theirs]
        .iter()
        .any(|b| b.len() > MAX_TEXT_MERGE_BYTES)
    {
        return Err(TextConflict::TooLarge);
    }
    if [base, ours, theirs]
        .iter()
        .any(|b| crate::diff::is_binary(b))
    {
        return Err(TextConflict::Binary);
    }
    let bl = split_keep(base);
    let ol = split_keep(ours);
    let tl = split_keep(theirs);
    let mut all: Vec<(u8, Hunk)> = hunks(&bl, &ol)
        .into_iter()
        .map(|h| (0u8, h))
        .chain(hunks(&bl, &tl).into_iter().map(|h| (1u8, h)))
        .collect();
    all.sort_by_key(|(side, h)| (h.b0, h.b1, *side));
    let sides = [&ol, &tl];
    let mut out: Vec<u8> = Vec::with_capacity(ours.len().max(theirs.len()));
    let mut pos = 0usize;
    let mut i = 0usize;
    while i < all.len() {
        let lo = all[i].1.b0;
        let mut hi = all[i].1.b1;
        // The group: every later hunk, of either side, that overlaps or touches it.
        let mut j = i + 1;
        while j < all.len() && all[j].1.b0 <= hi {
            hi = hi.max(all[j].1.b1);
            j += 1;
        }
        for line in &bl[pos..lo] {
            out.extend_from_slice(line);
        }
        let group = &all[i..j];
        let region = |side: u8| -> Option<(usize, usize)> {
            let mine: Vec<&Hunk> = group
                .iter()
                .filter(|(s, _)| *s == side)
                .map(|(_, h)| h)
                .collect();
            let first = mine.first()?;
            let last = mine.last()?;
            Some((first.s0 - (first.b0 - lo), last.s1 + (hi - last.b1)))
        };
        match (region(0), region(1)) {
            (Some((s0, s1)), None) => {
                for line in &sides[0][s0..s1] {
                    out.extend_from_slice(line);
                }
            }
            (None, Some((s0, s1))) => {
                for line in &sides[1][s0..s1] {
                    out.extend_from_slice(line);
                }
            }
            (Some((o0, o1)), Some((t0, t1))) => {
                if sides[0][o0..o1] != sides[1][t0..t1] {
                    return Err(TextConflict::Overlap);
                }
                for line in &sides[0][o0..o1] {
                    out.extend_from_slice(line);
                }
            }
            (None, None) => unreachable!("a group holds at least one hunk"),
        }
        pos = hi;
        i = j;
    }
    for line in &bl[pos..] {
        out.extend_from_slice(line);
    }
    Ok(out)
}

// ───────────────────────────── commits ───────────────────────────────────────

/// A name and an address, as a commit's `author` / `committer` line spells them.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Ident {
    /// The name.
    pub name: String,
    /// The address, without angle brackets.
    pub email: String,
}

impl Ident {
    /// `name <email>`, with the characters git's grammar forbids taken out.
    pub fn line(&self) -> String {
        let clean = |s: &str| -> String {
            s.chars()
                .filter(|c| !matches!(c, '<' | '>' | '\n' | '\0'))
                .collect::<String>()
                .trim()
                .to_owned()
        };
        format!("{} <{}>", clean(&self.name), clean(&self.email))
    }
}

/// A commit object's bytes.
pub fn commit_bytes(
    tree: &ObjectId,
    parents: &[ObjectId],
    author: &Ident,
    committer: &Ident,
    when_unix: i64,
    message: &str,
) -> Vec<u8> {
    let mut body = format!("tree {}\n", hex(tree));
    for parent in parents {
        body.push_str(&format!("parent {}\n", hex(parent)));
    }
    body.push_str(&format!("author {} {when_unix} +0000\n", author.line()));
    body.push_str(&format!(
        "committer {} {when_unix} +0000\n\n",
        committer.line()
    ));
    body.push_str(message.trim_end());
    body.push('\n');
    body.into_bytes()
}

/// **Sign a commit gunnar wrote** (GUN-MERGE-SIGN): an SSH signature (namespace `git`)
/// over `bytes` by `key`, folded into the header git reads it from (`gpgsig`, or
/// `gpgsig-sha256` in a SHA-256 repository) after the last header, exactly as
/// `git commit -S` with `gpg.format=ssh` writes one.
pub fn sign_commit(
    bytes: &[u8],
    hash: HashKind,
    key: &gunnar_core::ssh_key::PrivateKey,
) -> Result<Vec<u8>> {
    let header = match hash {
        HashKind::Sha256 => "gpgsig-sha256",
        _ => "gpgsig",
    };
    let end = bytes
        .windows(2)
        .position(|w| w == b"\n\n")
        .ok_or_else(|| err("the commit to sign has no end of headers"))?;
    if bytes[..end]
        .split(|&b| b == b'\n')
        .any(|line| line.starts_with(b"gpgsig ") || line.starts_with(b"gpgsig-sha256 "))
    {
        return Err(err("the commit to sign is already signed"));
    }
    let signature = key
        .sign(
            gunnar_policy::signature::GIT_NAMESPACE,
            gunnar_core::ssh_key::HashAlg::Sha512,
            bytes,
        )
        .map_err(|e| err(format!("signing the commit: {e}")))?;
    let armor = signature
        .to_pem(gunnar_core::ssh_key::LineEnding::LF)
        .map_err(|e| err(format!("armouring the commit's signature: {e}")))?;
    let mut folded = header.to_owned();
    for (i, line) in armor.trim_end_matches('\n').split('\n').enumerate() {
        folded.push_str(if i == 0 { " " } else { "\n " });
        folded.push_str(line);
    }
    folded.push('\n');
    let mut out = Vec::with_capacity(bytes.len() + folded.len());
    out.extend_from_slice(&bytes[..=end]);
    out.extend_from_slice(folded.as_bytes());
    out.extend_from_slice(&bytes[end + 1..]);
    Ok(out)
}

impl NewObjects {
    /// Add a commit and answer its id.
    pub fn add_commit(&mut self, hash: HashKind, bytes: Vec<u8>) -> Result<ObjectId> {
        self.add(hash, ObjType::Commit, bytes)
    }
}

// ───────────────────────────── the overlay ───────────────────────────────────

/// **The repository as it would be after the merge**, for the gates: every read sees the
/// merge's new objects on top of the store, and nothing can be written through it.
///
/// The gates (`BranchProtectionGate`, `SignedCommitsGate`, `AiTrailerGate`) read commits
/// through `GitServe::read`; running them here is what lets `CheckMerge` judge a merge
/// commit that does not exist yet — and the real merge judge it before it is stored.
pub struct Overlay<'a> {
    inner: &'a dyn GitServe,
    new: &'a NewObjects,
}

impl<'a> Overlay<'a> {
    /// `inner` with `new` on top.
    pub fn new(inner: &'a dyn GitServe, new: &'a NewObjects) -> Self {
        Overlay { inner, new }
    }
}

fn read_only<T>() -> anyhow::Result<T> {
    anyhow::bail!("the merge overlay is read-only: nothing is written before every gate has run")
}

impl GitOps for Overlay<'_> {
    fn put(&self, _pack: &[u8], _refs: &[RefUpdate]) -> anyhow::Result<TxId> {
        read_only()
    }
    fn put_pack(&self, _bytes: &[u8]) -> anyhow::Result<TxId> {
        read_only()
    }
    fn put_refs(&self, _updates: &[RefUpdate]) -> anyhow::Result<TxId> {
        read_only()
    }
    fn get(&self, oid: gst::Oid<'_>) -> anyhow::Result<Option<Stored>> {
        self.inner.get(oid)
    }
    fn has(&self, oid: gst::Oid<'_>) -> anyhow::Result<bool> {
        Ok(self.new.get(oid).is_some() || self.inner.has(oid)?)
    }
    fn size(&self, oid: gst::Oid<'_>) -> anyhow::Result<Option<u64>> {
        match self.new.get(oid) {
            Some((_, bytes)) => Ok(Some(bytes.len() as u64)),
            None => self.inner.size(oid),
        }
    }
    fn extents(&self, oids: &[gst::Oid<'_>]) -> anyhow::Result<Vec<Option<gst::Extent>>> {
        self.inner.extents(oids)
    }
    fn refs(&self) -> anyhow::Result<Vec<RefRow>> {
        self.inner.refs()
    }
    fn update_ref(
        &self,
        _name: &str,
        _old: Option<gst::Oid<'_>>,
        _new: Option<gst::Oid<'_>>,
    ) -> anyhow::Result<TxId> {
        read_only()
    }
    fn put_refs_cas(&self, _edits: &[RefCas<'_>]) -> anyhow::Result<TxId> {
        read_only()
    }
    fn reachable(
        &self,
        want: &[gst::Oid<'_>],
        have: &[gst::Oid<'_>],
    ) -> anyhow::Result<Vec<Vec<u8>>> {
        self.inner.reachable(want, have)
    }
    fn gc(&self) -> anyhow::Result<GcReport> {
        read_only()
    }
}

impl GitServe for Overlay<'_> {
    fn read(&self, oid: gst::Oid<'_>) -> anyhow::Result<Option<(ObjType, Vec<u8>)>> {
        match self.new.get(oid) {
            Some((kind, bytes)) => Ok(Some((*kind, bytes.clone()))),
            None => self.inner.read(oid),
        }
    }
    fn header(&self, oid: gst::Oid<'_>) -> anyhow::Result<Option<(ObjType, u64)>> {
        match self.new.get(oid) {
            Some((kind, bytes)) => Ok(Some((*kind, bytes.len() as u64))),
            None => self.inner.header(oid),
        }
    }
    fn sizes(&self, oids: &[gst::Oid<'_>]) -> anyhow::Result<Vec<Option<u64>>> {
        oids.iter().map(|oid| self.size(oid)).collect()
    }
    fn head(&self) -> anyhow::Result<Option<RefRow>> {
        self.inner.head()
    }
    fn set_head(&self, _target: &str) -> anyhow::Result<TxId> {
        read_only()
    }
    fn emit_pack(
        &self,
        objects: &[gst::Oid<'_>],
        have: &[gst::Oid<'_>],
        caps: &Caps,
        out: &mut dyn std::io::Write,
    ) -> anyhow::Result<PackStats> {
        self.inner.emit_pack(objects, have, caps, out)
    }
    fn select(
        &self,
        want: &[gst::Oid<'_>],
        have: &[gst::Oid<'_>],
    ) -> anyhow::Result<Option<ReachSet>> {
        self.inner.select(want, have)
    }
}

/// Every commit subject in `commits`, for a squash's message; unreadable ones skipped.
pub fn subjects(git: &dyn GitServe, hash: HashKind, commits: &[ObjectId]) -> Vec<String> {
    let mut out = Vec::new();
    let mut seen = HashSet::new();
    for id in commits {
        if !seen.insert(*id) {
            continue;
        }
        let Ok(bytes) = read_as(git, id, ObjType::Commit) else {
            continue;
        };
        let Ok(commit) = object::commit(&bytes, hash) else {
            continue;
        };
        let subject = String::from_utf8_lossy(&commit.message)
            .lines()
            .next()
            .unwrap_or("")
            .trim()
            .to_owned();
        out.push(subject);
    }
    out
}

#[cfg(test)]
mod tests;