sley_diff_merge/

blob_merge.rs

//! Three-way blob merge (diff3 conflict markers).

use crate::line_diff::{
    canonicalize_line, myers_diff_lines, myers_diff_lines_ws, split_lines, DiffAlgorithm,
    DiffLine, DiffOp, WsIgnore,
};

/// Whether to favour one side wholesale for textual conflicts (`-Xours` /
/// `-Xtheirs`), or to leave conflict markers in place.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum MergeFavor {
    /// Leave conflict markers in place (the default).
    None,
    /// On a textual conflict, take ours' content wholesale.
    Ours,
    /// On a textual conflict, take theirs' content wholesale.
    Theirs,
    /// On a textual conflict, keep BOTH sides' lines (ours then theirs) with no
    /// markers — git's `merge=union` attribute / `--union` (`XDL_MERGE_FAVOR_UNION`).
    Union,
}

/// Which conflict-marker style [`merge_blobs`] emits.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub enum ConflictStyle {
    /// Standard two-section markers (`<<<<<<<` / `=======` / `>>>>>>>`).
    #[default]
    Merge,
    /// `diff3` style: also include the common-ancestor section between `ours`
    /// and the `=======` divider, delimited by `|||||||`.
    Diff3,
}

/// Labels and style controlling [`merge_blobs`] conflict markers.
#[derive(Debug, Clone, Copy)]
pub struct MergeBlobOptions<'a> {
    /// Label after the opening `<<<<<<<` marker (typically the local branch).
    pub ours_label: &'a str,
    /// Label after the closing `>>>>>>>` marker (typically the other branch).
    pub theirs_label: &'a str,
    /// Label after the `|||||||` marker (only used for [`ConflictStyle::Diff3`]).
    pub base_label: &'a str,
    /// Which marker style to emit.
    pub style: ConflictStyle,
    /// How to resolve a textual conflict. [`MergeFavor::Union`] keeps both sides'
    /// lines with no markers (and a non-conflicted result); other values leave
    /// markers (favouring ours/theirs is applied by the caller at the file level).
    pub favor: MergeFavor,
    /// Whitespace-insensitivity for the 3-way line matching, mirroring
    /// `-Xignore-space-change`/`-Xignore-all-space`/`-Xignore-space-at-eol` (git's
    /// `ll_opts.xdl_opts`). When non-empty, regions that differ only by ignored
    /// whitespace are not conflicts, and unchanged spans emit ours' actual bytes
    /// (xdl_merge copies the common parts from file1). Empty (the default) is the
    /// exact, byte-for-byte merge.
    pub ws_ignore: WsIgnore,
    /// Number of marker bytes in `<<<<<<<` / `=======` / `>>>>>>>` lines.
    pub marker_size: usize,
}

impl Default for MergeBlobOptions<'_> {
    fn default() -> Self {
        Self {
            ours_label: "ours",
            theirs_label: "theirs",
            base_label: "base",
            style: ConflictStyle::Merge,
            favor: MergeFavor::None,
            ws_ignore: WsIgnore::EMPTY,
            marker_size: 7,
        }
    }
}

/// The outcome of a 3-way blob merge.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct MergeBlobResult {
    /// The merged blob bytes, including any conflict markers.
    pub content: Vec<u8>,
    /// True when at least one region conflicted and markers were written.
    pub conflicted: bool,
}

/// Perform a 3-way merge of three blobs using the diff3 algorithm.
///
/// `base` is the common ancestor; `ours` and `theirs` are the two sides. The
/// merge diffs base→ours and base→theirs (with [`myers_diff_lines`]) and walks
/// the base in lockstep:
/// - regions unchanged on both sides emit the base lines unchanged;
/// - regions changed on exactly one side take that side's lines;
/// - regions changed on both sides emit the side lines if they are
///   byte-identical, otherwise a conflict (and [`MergeBlobResult::conflicted`]
///   is set).
///
/// An empty `base` is supported: every line is then "added on both sides", so
/// the result is the shared content if `ours == theirs`, else a single
/// conflict (add/add).
pub fn merge_blobs(
    base: &[u8],
    ours: &[u8],
    theirs: &[u8],
    options: &MergeBlobOptions<'_>,
) -> MergeBlobResult {
    let base_lines = split_lines(base);
    let ours_lines = split_lines(ours);
    let theirs_lines = split_lines(theirs);

    // Per-side matched (equal) base regions, paired with the corresponding side
    // ranges, computed via Myers. Under `ws_ignore`, lines that differ only by
    // ignored whitespace match, so whitespace-only changes are absorbed into the
    // stable spans rather than surfacing as conflicts.
    let ours_matches = matching_regions(&base_lines, &ours_lines, options.ws_ignore);
    let theirs_matches = matching_regions(&base_lines, &theirs_lines, options.ws_ignore);

    // Intersect the two match lists to get segments of base that are unchanged
    // on BOTH sides, each carrying the exact aligned side indices. Between these
    // common-stable segments lie the (potentially conflicting) changed regions.
    let stable = common_stable_segments(&ours_matches, &theirs_matches);

    let mut writer = MergeWriter::new(options);
    // Cursors: next unconsumed line in base, ours, theirs.
    let mut base_idx = 0usize;
    let mut our_idx = 0usize;
    let mut their_idx = 0usize;

    for seg in &stable {
        // Unstable (changed) region preceding this stable segment.
        let base_region = &base_lines[base_idx..seg.base_start];
        let our_region = &ours_lines[our_idx..seg.ours_start];
        let their_region = &theirs_lines[their_idx..seg.theirs_start];
        emit_region(
            &mut writer,
            base_region,
            our_region,
            their_region,
            options.ws_ignore,
        );

        // The stable segment matched on both sides. Emit ours' actual bytes
        // (xdl_merge copies common spans from file1): identical to base under an
        // exact match, and ours' whitespace under `ws_ignore`.
        writer.emit_lines(&ours_lines[seg.ours_start..seg.ours_start + seg.len]);

        base_idx = seg.base_start + seg.len;
        our_idx = seg.ours_start + seg.len;
        their_idx = seg.theirs_start + seg.len;
    }

    // Trailing unstable region after the last stable segment (or the whole input
    // when there are no common-stable segments).
    emit_region(
        &mut writer,
        &base_lines[base_idx..],
        &ours_lines[our_idx..],
        &theirs_lines[their_idx..],
        options.ws_ignore,
    );

    writer.finish()
}

/// Resolve and emit one changed region (the gap between two common-stable
/// segments) according to diff3 rules.
fn emit_region(
    writer: &mut MergeWriter<'_>,
    base_region: &[DiffLine<'_>],
    our_region: &[DiffLine<'_>],
    their_region: &[DiffLine<'_>],
    ws_ignore: WsIgnore,
) {
    if our_region.is_empty() && their_region.is_empty() {
        return;
    }
    // Under `ws_ignore`, "changed" means changed beyond ignored whitespace; with
    // the empty default the comparison is exact byte equality.
    let our_changed = !regions_match(our_region, base_region, ws_ignore);
    let their_changed = !regions_match(their_region, base_region, ws_ignore);
    match (our_changed, their_changed) {
        (false, false) => writer.emit_lines(our_region),
        (true, false) => writer.emit_lines(our_region),
        (false, true) => writer.emit_lines(their_region),
        (true, true) => {
            if regions_match(our_region, their_region, ws_ignore) {
                // Both sides made the same change (up to ignored whitespace): no
                // conflict. xdl_merge keeps ours' bytes.
                writer.emit_lines(our_region);
            } else {
                writer.emit_conflict_refined(our_region, base_region, their_region);
            }
        }
    }
}

/// Whether two line slices are equal, exactly when `ws_ignore` is empty and up to
/// the active whitespace-ignore canonicalization otherwise.
fn regions_match(a: &[DiffLine<'_>], b: &[DiffLine<'_>], ws_ignore: WsIgnore) -> bool {
    if ws_ignore.is_empty() {
        return a == b;
    }
    a.len() == b.len()
        && a.iter().zip(b).all(|(x, y)| {
            canonicalize_line(x.content, ws_ignore) == canonicalize_line(y.content, ws_ignore)
        })
}

/// One unit produced by zealous conflict refinement: either context lines shared
/// by both sides (emitted verbatim) or a minimal conflict spanning the named
/// ours/theirs line ranges.
enum RefineItem {
    Context(std::ops::Range<usize>),
    Conflict(std::ops::Range<usize>, std::ops::Range<usize>),
}

/// git's `xdl_refine_conflicts` + `xdl_simplify_non_conflicts` (level
/// `XDL_MERGE_ZEALOUS`): re-diff the two conflicting sides against each other,
/// factor the lines they share out of the conflict as context, and split the
/// remainder into the minimal set of conflicting hunks — then re-merge any two
/// conflicts separated by 3 or fewer context lines (the smaller-output rule).
///
/// Ranges index into `ours`/`theirs`; `Context` ranges are in ours coordinates
/// (the shared lines are identical on both sides).
fn refine_conflict_items(ours: &[DiffLine<'_>], theirs: &[DiffLine<'_>]) -> Vec<RefineItem> {
    // Coalesce the ours-vs-theirs diff into alternating context (equal) and
    // conflict (changed) runs.
    let ops = myers_diff_lines(ours, theirs);
    let mut raw: Vec<RefineItem> = Vec::new();
    let mut oi = 0usize;
    let mut ti = 0usize;
    let mut pending: Option<(usize, usize, usize, usize)> = None; // o0,o1,t0,t1
    for op in ops {
        match op {
            DiffOp::Equal(n) => {
                if let Some((o0, o1, t0, t1)) = pending.take() {
                    raw.push(RefineItem::Conflict(o0..o1, t0..t1));
                }
                raw.push(RefineItem::Context(oi..oi + n));
                oi += n;
                ti += n;
            }
            DiffOp::Delete(n) => {
                let entry = pending.get_or_insert((oi, oi, ti, ti));
                entry.1 = oi + n;
                oi += n;
            }
            DiffOp::Insert(n) => {
                let entry = pending.get_or_insert((oi, oi, ti, ti));
                entry.3 = ti + n;
                ti += n;
            }
        }
    }
    if let Some((o0, o1, t0, t1)) = pending.take() {
        raw.push(RefineItem::Conflict(o0..o1, t0..t1));
    }

    // Merge two conflicts when the context between them is <= 3 lines: the
    // absorbed context lines are identical on both sides, so they fold into the
    // combined conflict's ours and theirs ranges alike.
    let mut out: Vec<RefineItem> = Vec::new();
    let mut idx = 0usize;
    while idx < raw.len() {
        match &raw[idx] {
            RefineItem::Context(range) => {
                let small = range.len() <= 3;
                let prev_conflict = matches!(out.last(), Some(RefineItem::Conflict(..)));
                let next_conflict = matches!(raw.get(idx + 1), Some(RefineItem::Conflict(..)));
                if small && prev_conflict && next_conflict {
                    let Some(RefineItem::Conflict(po, pt)) = out.pop() else {
                        unreachable!()
                    };
                    let RefineItem::Conflict(no, nt) = &raw[idx + 1] else {
                        unreachable!()
                    };
                    out.push(RefineItem::Conflict(po.start..no.end, pt.start..nt.end));
                    idx += 2;
                } else {
                    out.push(RefineItem::Context(range.clone()));
                    idx += 1;
                }
            }
            RefineItem::Conflict(o, t) => {
                out.push(RefineItem::Conflict(o.clone(), t.clone()));
                idx += 1;
            }
        }
    }
    out
}

/// A matched (equal) region between `base` and one side: `base_start..+len`
/// lines of base equal `side_start..+len` lines of that side.
#[derive(Debug, Clone, Copy)]
struct MatchRegion {
    base_start: usize,
    side_start: usize,
    len: usize,
}

/// A run of base lines unchanged on *both* sides, with the aligned side starts.
#[derive(Debug, Clone, Copy)]
struct StableSegment {
    base_start: usize,
    ours_start: usize,
    theirs_start: usize,
    len: usize,
}

/// Compute the matched regions between base and a side using [`myers_diff_lines`].
///
/// Each `Equal(n)` run becomes a [`MatchRegion`]; the regions are returned in
/// increasing base order. (Equal runs are coalesced by the diff, so adjacent
/// regions are already maximal.)
fn matching_regions(
    base: &[DiffLine<'_>],
    side: &[DiffLine<'_>],
    ws_ignore: WsIgnore,
) -> Vec<MatchRegion> {
    let ops = if ws_ignore.is_empty() {
        myers_diff_lines(base, side)
    } else {
        // The 3-way content merge uses the Myers line diff (git's ll-merge xdl
        // default); the whitespace flags affect only the equality test.
        myers_diff_lines_ws(base, side, ws_ignore, DiffAlgorithm::Myers)
    };
    let mut regions = Vec::new();
    let mut base_idx = 0usize;
    let mut side_idx = 0usize;
    for op in ops {
        match op {
            DiffOp::Equal(n) => {
                regions.push(MatchRegion {
                    base_start: base_idx,
                    side_start: side_idx,
                    len: n,
                });
                base_idx += n;
                side_idx += n;
            }
            DiffOp::Delete(n) => base_idx += n,
            DiffOp::Insert(n) => side_idx += n,
        }
    }
    regions
}

/// Intersect the ours/theirs match lists (both in base coordinates) to find the
/// base ranges unchanged on both sides, recording the aligned side indices.
///
/// For each overlapping pair of base ranges `[bs, be)` the ours-side index of
/// `bs` is `o.side_start + (bs - o.base_start)` and likewise for theirs; both
/// map contiguously across the overlap. The returned segments are in increasing
/// base order and never overlap.
fn common_stable_segments(ours: &[MatchRegion], theirs: &[MatchRegion]) -> Vec<StableSegment> {
    let mut segments = Vec::new();
    let mut oi = 0usize;
    let mut ti = 0usize;
    while oi < ours.len() && ti < theirs.len() {
        let o = ours[oi];
        let t = theirs[ti];
        let o_end = o.base_start + o.len;
        let t_end = t.base_start + t.len;
        let lo = o.base_start.max(t.base_start);
        let hi = o_end.min(t_end);
        if lo < hi {
            segments.push(StableSegment {
                base_start: lo,
                ours_start: o.side_start + (lo - o.base_start),
                theirs_start: t.side_start + (lo - t.base_start),
                len: hi - lo,
            });
        }
        // Advance whichever range ends first.
        if o_end <= t_end {
            oi += 1;
        } else {
            ti += 1;
        }
    }
    segments
}

/// Accumulates merged output and renders conflict markers byte-for-byte like
/// upstream git.
struct MergeWriter<'a> {
    out: Vec<u8>,
    conflicted: bool,
    options: &'a MergeBlobOptions<'a>,
}

impl<'a> MergeWriter<'a> {
    fn new(options: &'a MergeBlobOptions<'a>) -> Self {
        Self {
            out: Vec::new(),
            conflicted: false,
            options,
        }
    }

    /// Append raw line bytes (each line already carries its own newline, except
    /// possibly a final no-newline line).
    fn emit_lines(&mut self, lines: &[DiffLine<'_>]) {
        for line in lines {
            self.out.extend_from_slice(line.content);
        }
    }

    /// Emit a conflict hunk. Conflict markers always begin on their own line,
    /// so if the preceding emitted content did not end in a newline (a
    /// no-newline-at-end side), insert one first — matching git, which prints
    /// the "\ No newline at end of file" content followed by a newline before
    /// the next marker.
    fn emit_conflict(
        &mut self,
        ours: &[DiffLine<'_>],
        base: &[DiffLine<'_>],
        theirs: &[DiffLine<'_>],
    ) {
        // Union: keep both sides' lines (ours then theirs) with no markers, and do
        // NOT flag a conflict — git's `XDL_MERGE_FAVOR_UNION`.
        if self.options.favor == MergeFavor::Union {
            self.emit_section(ours);
            self.ensure_newline();
            self.emit_section(theirs);
            return;
        }
        self.conflicted = true;
        self.write_marker(b'<', self.options.ours_label);
        self.emit_section(ours);
        if self.options.style == ConflictStyle::Diff3 {
            self.ensure_newline();
            self.write_marker(b'|', self.options.base_label);
            self.emit_section(base);
        }
        self.ensure_newline();
        self.write_divider();
        self.emit_section(theirs);
        self.ensure_newline();
        self.write_marker(b'>', self.options.theirs_label);
    }

    /// Emit a conflict with git's zealous refinement applied. The default
    /// (non-diff3) merge re-diffs the two sides to shrink the conflict to the
    /// lines that genuinely differ (`xdl_refine_conflicts`); diff3-style output
    /// keeps the conflict whole (the base section straddles it), a favored merge
    /// resolves at a coarser granularity, and an empty side cannot be refined —
    /// all three fall back to a single unrefined conflict hunk.
    fn emit_conflict_refined(
        &mut self,
        ours: &[DiffLine<'_>],
        base: &[DiffLine<'_>],
        theirs: &[DiffLine<'_>],
    ) {
        if self.options.style == ConflictStyle::Diff3
            || self.options.favor != MergeFavor::None
            || ours.is_empty()
            || theirs.is_empty()
        {
            self.emit_conflict(ours, base, theirs);
            return;
        }
        for item in refine_conflict_items(ours, theirs) {
            match item {
                RefineItem::Context(range) => self.emit_lines(&ours[range]),
                RefineItem::Conflict(o, t) => self.emit_conflict(&ours[o], &[], &theirs[t]),
            }
        }
    }

    /// Emit one side's lines inside a conflict, preserving their exact bytes.
    fn emit_section(&mut self, lines: &[DiffLine<'_>]) {
        for line in lines {
            self.out.extend_from_slice(line.content);
        }
    }

    /// Ensure the buffer ends with a newline before writing the next marker, so
    /// markers always start a fresh line even after a no-newline final line.
    fn ensure_newline(&mut self) {
        if !self.out.is_empty() && self.out.last() != Some(&b'\n') {
            self.out.push(b'\n');
        }
    }

    /// Write a marker line: N copies of `ch`, then (if the label is non-empty)
    /// a space and the label, then a newline. No trailing space for an empty
    /// label — byte-for-byte with upstream git.
    fn write_marker(&mut self, ch: u8, label: &str) {
        for _ in 0..self.options.marker_size {
            self.out.push(ch);
        }
        if !label.is_empty() {
            self.out.push(b' ');
            self.out.extend_from_slice(label.as_bytes());
        }
        self.out.push(b'\n');
    }

    /// Write the `=======` divider line (never labelled).
    fn write_divider(&mut self) {
        for _ in 0..self.options.marker_size {
            self.out.push(b'=');
        }
        self.out.push(b'\n');
    }

    fn finish(self) -> MergeBlobResult {
        MergeBlobResult {
            content: self.out,
            conflicted: self.conflicted,
        }
    }
}