diffy_imara/merge/

mod.rs

use imara_diff::sources::{byte_lines_with_terminator, lines_with_terminator};

use crate::{
    diff::DiffOptions,
    range::{DiffRange, Range, SliceLike},
    utils::InternedMergeInput,
    Algorithm,
};
use std::{cmp, fmt};

#[cfg(test)]
mod tests;

const DEFAULT_CONFLICT_MARKER_LENGTH: usize = 7;

enum Diff3Range<'ancestor, 'ours, 'theirs, T: ?Sized> {
    Equal(Range<'ancestor, T>, Range<'ours, T>, Range<'theirs, T>),
    Ancestor(Range<'ancestor, T>),
    AncestorOurs(Range<'ancestor, T>, Range<'ours, T>),
    AncestorTheirs(Range<'ancestor, T>, Range<'theirs, T>),
    Ours(Range<'ours, T>),
    Theirs(Range<'theirs, T>),
}

impl<T: ?Sized + fmt::Debug + SliceLike> fmt::Debug for Diff3Range<'_, '_, '_, T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Diff3Range::Equal(range, ..) => write!(f, "Equal: {:?}", range.as_slice()),
            Diff3Range::Ancestor(range) => write!(f, "Ancestor: {:?}", range.as_slice()),
            Diff3Range::AncestorOurs(range, ..) => {
                write!(f, "AncestorOurs: {:?}", range.as_slice())
            }
            Diff3Range::AncestorTheirs(range, ..) => {
                write!(f, "AncestorTheirs: {:?}", range.as_slice())
            }
            Diff3Range::Ours(range) => write!(f, "Ours: {:?}", range.as_slice()),
            Diff3Range::Theirs(range) => write!(f, "Theirs: {:?}", range.as_slice()),
        }
    }
}

impl<T: ?Sized> Copy for Diff3Range<'_, '_, '_, T> {}

impl<T: ?Sized> Clone for Diff3Range<'_, '_, '_, T> {
    fn clone(&self) -> Self {
        *self
    }
}

enum MergeRange<'ancestor, 'ours, 'theirs, T: ?Sized> {
    Equal(Range<'ancestor, T>, Range<'ours, T>, Range<'theirs, T>),
    Conflict(Range<'ancestor, T>, Range<'ours, T>, Range<'theirs, T>),
    Ours(Range<'ours, T>),
    Theirs(Range<'theirs, T>),
    Both(Range<'ours, T>, Range<'theirs, T>),
}

impl<T: ?Sized + fmt::Debug + SliceLike> fmt::Debug for MergeRange<'_, '_, '_, T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            MergeRange::Equal(range, ..) => write!(f, "Equal: {:?}", range.as_slice()),
            MergeRange::Conflict(ancestor, ours, theirs) => write!(
                f,
                "Conflict: ancestor: {:?} ours: {:?} theirs: {:?}",
                ancestor.as_slice(),
                ours.as_slice(),
                theirs.as_slice()
            ),
            MergeRange::Ours(range) => write!(f, "Ours: {:?}", range.as_slice()),
            MergeRange::Theirs(range) => write!(f, "Theirs: {:?}", range.as_slice()),
            MergeRange::Both(ours, theirs) => write!(
                f,
                "Both: ours: {:?} theirs: {:?}",
                ours.as_slice(),
                theirs.as_slice()
            ),
        }
    }
}

impl<T: ?Sized> Copy for MergeRange<'_, '_, '_, T> {}

impl<T: ?Sized> Clone for MergeRange<'_, '_, '_, T> {
    fn clone(&self) -> Self {
        *self
    }
}

/// Style used when rendering a conflict
#[derive(Copy, Clone, Debug, Default)]
pub enum ConflictStyle {
    /// Renders conflicting lines from both files, separated by conflict markers.
    ///
    /// ```console
    /// <<<<<<< A
    /// lines in file A
    /// =======
    /// lines in file B
    /// >>>>>>> B
    /// ```
    Merge,

    /// Renders conflicting lines from both files including lines from the original files,
    /// separated by conflict markers.
    ///
    /// ```console
    /// <<<<<<< A
    /// lines in file A
    /// ||||||| Original
    /// lines in Original file
    /// =======
    /// lines in file B
    /// >>>>>>> B
    /// ```
    #[default]
    Diff3,
}

/// A collection of options for modifying the way a merge is performed
#[derive(Debug)]
pub struct MergeOptions {
    /// The length of the conflict markers used when displaying a merge conflict
    pub conflict_marker_length: usize,
    /// The conflict style used when displaying a merge conflict
    pub style: ConflictStyle,
    pub algorithm: Algorithm,
}

impl MergeOptions {
    /// Constructs a new `MergeOptions` with default settings
    ///
    /// ## Defaults
    /// * conflict_marker_length = 7
    /// * style = ConflictStyle::Diff3
    pub fn new() -> Self {
        Self {
            conflict_marker_length: DEFAULT_CONFLICT_MARKER_LENGTH,
            style: ConflictStyle::Diff3,
            algorithm: Algorithm::Histogram,
        }
    }

    /// Merge two files, given a common ancestor, based on the configured options
    /// The algorithm set in [`Self::algorithm`] is used for computing the diff between `ancestor`
    /// and `ours`, and between `ancestor` and `theirs`
    pub fn merge<'a>(
        &self,
        ancestor: &'a str,
        ours: &'a str,
        theirs: &'a str,
    ) -> Result<String, String> {
        let input = InternedMergeInput::new(ancestor, ours, theirs);
        let ancestor_lines: Vec<_> = lines_with_terminator(ancestor).collect();
        let our_lines: Vec<_> = lines_with_terminator(ours).collect();
        let their_lines: Vec<_> = lines_with_terminator(theirs).collect();

        let opts = DiffOptions {
            algorithm: self.algorithm,
            ..Default::default()
        };

        let our_solution = opts.diff_tokens(&input.base, &input.left, input.interner.num_tokens());
        let their_solution =
            opts.diff_tokens(&input.base, &input.right, input.interner.num_tokens());

        let merged = merge_solutions(&our_solution, &their_solution);
        let mut merge = diff3_range_to_merge_range(&merged);

        cleanup_conflicts(&mut merge);

        output_result(
            &ancestor_lines,
            &our_lines,
            &their_lines,
            &merge,
            self.conflict_marker_length,
            self.style,
        )
    }

    /// Perform a 3-way merge between potentially non-utf8 texts
    pub fn merge_bytes<'a>(
        &self,
        ancestor: &'a [u8],
        ours: &'a [u8],
        theirs: &'a [u8],
    ) -> Result<Vec<u8>, Vec<u8>> {
        let input = InternedMergeInput::new(ancestor, ours, theirs);
        let ancestor_lines: Vec<_> = byte_lines_with_terminator(ancestor).collect();
        let our_lines: Vec<_> = byte_lines_with_terminator(ours).collect();
        let their_lines: Vec<_> = byte_lines_with_terminator(theirs).collect();

        let opts = DiffOptions {
            algorithm: self.algorithm,
            ..Default::default()
        };

        let our_solution = opts.diff_tokens(&input.base, &input.left, input.interner.num_tokens());
        let their_solution =
            opts.diff_tokens(&input.base, &input.right, input.interner.num_tokens());

        let merged = merge_solutions(&our_solution, &their_solution);
        let mut merge = diff3_range_to_merge_range(&merged);

        cleanup_conflicts(&mut merge);

        output_result_bytes(
            &ancestor_lines,
            &our_lines,
            &their_lines,
            &merge,
            self.conflict_marker_length,
            self.style,
        )
    }
}

impl Default for MergeOptions {
    fn default() -> Self {
        Self::new()
    }
}

/// Merge two files given a common ancestor.
///
/// Returns `Ok(String)` upon a successful merge.
/// Returns `Err(String)` if there were conflicts, with the conflicting
/// regions marked with conflict markers.
///
/// ## Merging two files without conflicts
/// ```
/// # use diffy_imara::merge;
/// let original = "\
/// Devotion
/// Dominion
/// Odium
/// Preservation
/// Ruin
/// Cultivation
/// Honor
/// Endowment
/// Autonomy
/// Ambition
/// ";
/// let a = "\
/// Odium
/// Preservation
/// Ruin
/// Cultivation
/// Endowment
/// Autonomy
/// ";
/// let b = "\
/// Devotion
/// Dominion
/// Odium
/// Harmony
/// Cultivation
/// Honor
/// Endowment
/// Autonomy
/// Ambition
/// ";
///
/// let expected = "\
/// Odium
/// Harmony
/// Cultivation
/// Endowment
/// Autonomy
/// ";
///
/// assert_eq!(merge(original, a, b).unwrap(), expected);
/// ```
pub fn merge<'a>(ancestor: &'a str, ours: &'a str, theirs: &'a str) -> Result<String, String> {
    MergeOptions::default().merge(ancestor, ours, theirs)
}

/// Perform a 3-way merge between potentially non-utf8 texts
pub fn merge_bytes<'a>(
    ancestor: &'a [u8],
    ours: &'a [u8],
    theirs: &'a [u8],
) -> Result<Vec<u8>, Vec<u8>> {
    MergeOptions::default().merge_bytes(ancestor, ours, theirs)
}

fn merge_solutions<'ancestor, 'ours, 'theirs, T: ?Sized + SliceLike>(
    our_solution: &[DiffRange<'ancestor, 'ours, T>],
    their_solution: &[DiffRange<'ancestor, 'theirs, T>],
) -> Vec<Diff3Range<'ancestor, 'ours, 'theirs, T>> {
    let mut our_solution = our_solution.iter().copied();
    let mut their_solution = their_solution.iter().copied();
    let mut ours = our_solution.next();
    let mut theirs = their_solution.next();

    let mut solution = Vec::new();

    while ours.is_some() || theirs.is_some() {
        use DiffRange as DR;
        let merge_range = match (ours, theirs) {
            //
            // Inserts can't easily be checked to see if they match each other
            //
            (Some(DR::Insert(range)), _) => {
                ours.take();
                Diff3Range::Ours(range)
            }
            (_, Some(DR::Insert(range))) => {
                theirs.take();
                Diff3Range::Theirs(range)
            }

            (Some(DR::Equal(ancestor1, our_range)), Some(DR::Equal(ancestor2, their_range))) => {
                assert_eq!(ancestor1.offset(), ancestor2.offset());
                let len = cmp::min(ancestor1.len(), ancestor2.len());

                shrink_front(&mut ours, len);
                shrink_front(&mut theirs, len);

                Diff3Range::Equal(
                    ancestor1.slice(..len),
                    our_range.slice(..len),
                    their_range.slice(..len),
                )
            }

            (Some(DR::Equal(ancestor1, our_range)), Some(DR::Delete(ancestor2))) => {
                assert_eq!(ancestor1.offset(), ancestor2.offset());
                let len = cmp::min(ancestor1.len(), ancestor2.len());

                shrink_front(&mut ours, len);
                shrink_front(&mut theirs, len);

                Diff3Range::AncestorOurs(ancestor1.slice(..len), our_range.slice(..len))
            }

            (Some(DR::Delete(ancestor1)), Some(DR::Equal(ancestor2, their_range))) => {
                assert_eq!(ancestor1.offset(), ancestor2.offset());
                let len = cmp::min(ancestor1.len(), ancestor2.len());

                shrink_front(&mut ours, len);
                shrink_front(&mut theirs, len);

                Diff3Range::AncestorTheirs(ancestor2.slice(..len), their_range.slice(..len))
            }

            (Some(DR::Delete(ancestor1)), Some(DR::Delete(ancestor2))) => {
                assert_eq!(ancestor1.offset(), ancestor2.offset());
                let len = cmp::min(ancestor1.len(), ancestor2.len());

                shrink_front(&mut ours, len);
                shrink_front(&mut theirs, len);

                Diff3Range::Ancestor(ancestor1.slice(..len))
            }

            //
            // Unreachable cases
            //
            (Some(DR::Equal(..) | DR::Delete(..)), None)
            | (None, Some(DR::Equal(..) | DR::Delete(_)))
            | (None, None) => unreachable!("Equal/Delete should match up"),
        };

        solution.push(merge_range);

        if ours.map_or(true, |range| range.is_empty()) {
            ours = our_solution.next();
        }
        if theirs.map_or(true, |range| range.is_empty()) {
            theirs = their_solution.next();
        }
    }

    solution
}

fn shrink_front<T: ?Sized + SliceLike>(maybe_range: &mut Option<DiffRange<T>>, len: usize) {
    if let Some(range) = maybe_range {
        range.shrink_front(len)
    }
}

fn diff3_range_to_merge_range<'ancestor, 'ours, 'theirs, T: ?Sized + SliceLike>(
    solution: &[Diff3Range<'ancestor, 'ours, 'theirs, T>],
) -> Vec<MergeRange<'ancestor, 'ours, 'theirs, T>> {
    let mut ancestor: Option<Range<'ancestor, T>> = None;
    let mut ours: Option<Range<'ours, T>> = None;
    let mut theirs: Option<Range<'theirs, T>> = None;

    let mut merge = Vec::new();

    for &diff3 in solution {
        match diff3 {
            Diff3Range::Equal(ancestor_range, our_range, their_range) => {
                if let Some(merge_range) =
                    create_merge_range(ancestor.take(), ours.take(), theirs.take())
                {
                    merge.push(merge_range);
                }
                merge.push(MergeRange::Equal(ancestor_range, our_range, their_range));
            }
            Diff3Range::Ancestor(range) => {
                set_or_merge_range(&mut ancestor, range);
                set_or_merge_range(&mut ours, Range::empty());
                set_or_merge_range(&mut theirs, Range::empty());
            }
            Diff3Range::AncestorOurs(ancestor_range, our_range) => {
                set_or_merge_range(&mut ancestor, ancestor_range);
                set_or_merge_range(&mut ours, our_range);
            }
            Diff3Range::AncestorTheirs(ancestor_range, their_range) => {
                set_or_merge_range(&mut ancestor, ancestor_range);
                set_or_merge_range(&mut theirs, their_range);
            }
            Diff3Range::Ours(range) => set_or_merge_range(&mut ours, range),
            Diff3Range::Theirs(range) => set_or_merge_range(&mut theirs, range),
        }
    }

    if let Some(merge_range) = create_merge_range(ancestor.take(), ours.take(), theirs.take()) {
        merge.push(merge_range);
    }

    merge
}

fn set_or_merge_range<'a, T: ?Sized>(range1: &mut Option<Range<'a, T>>, range2: Range<'a, T>) {
    if let Some(range1) = range1 {
        if range1.is_empty() {
            *range1 = range2;
        } else if !range2.is_empty() {
            assert_eq!(range1.offset() + range1.len(), range2.offset());
            range1.grow_down(range2.len());
        }
    } else {
        *range1 = Some(range2);
    }
}

fn create_merge_range<'ancestor, 'ours, 'theirs, T: ?Sized + SliceLike>(
    ancestor: Option<Range<'ancestor, T>>,
    ours: Option<Range<'ours, T>>,
    theirs: Option<Range<'theirs, T>>,
) -> Option<MergeRange<'ancestor, 'ours, 'theirs, T>> {
    match (ancestor, ours, theirs) {
        (_, None, None) => None,

        (None, Some(ours), None) => Some(MergeRange::Ours(ours)),
        (None, None, Some(theirs)) => Some(MergeRange::Theirs(theirs)),

        (ancestor, ours, theirs) => Some(MergeRange::Conflict(
            ancestor.unwrap_or_default(),
            ours.unwrap_or_default(),
            theirs.unwrap_or_default(),
        )),
    }
}

#[allow(clippy::needless_lifetimes)]
fn cleanup_conflicts<'ancestor, 'ours, 'theirs, T: ?Sized + SliceLike + PartialEq>(
    solution: &mut [MergeRange<'ancestor, 'ours, 'theirs, T>],
) {
    // TODO this could probably be more sophisticated:
    // e.g. run the diff algorithm on the conflict area
    for merge in solution {
        if let MergeRange::Conflict(ancestor, ours, theirs) = *merge {
            // If the ranges in the conflict end up being the same on both sides then we can
            // eliminate the conflict
            if ours.as_slice() == theirs.as_slice() {
                *merge = MergeRange::Both(ours, theirs);
            // If either ours or theirs exactly matches ancestor then we can also eliminate the
            // conflict
            } else if ancestor.as_slice() == ours.as_slice() {
                *merge = MergeRange::Theirs(theirs);
            } else if ancestor.as_slice() == theirs.as_slice() {
                *merge = MergeRange::Ours(ours);
            }
        }
    }
}

fn output_result<'a, T: ?Sized>(
    ancestor: &[&'a str],
    ours: &[&'a str],
    theirs: &[&'a str],
    merge: &[MergeRange<T>],
    marker_len: usize,
    style: ConflictStyle,
) -> Result<String, String> {
    let mut conflicts = 0;
    let mut output = String::new();

    for (range_idx, merge_range) in merge.iter().enumerate() {
        match merge_range {
            MergeRange::Equal(range, ..) => {
                add_lines(&mut output, &ancestor[range.range()]);
            }
            MergeRange::Conflict(ancestor_range, ours_range, theirs_range) => {
                let ancestor = &ancestor[ancestor_range.range()];
                let ours = &ours[ours_range.range()];
                let theirs = &theirs[theirs_range.range()];

                if range_idx == merge.len() - 1 {
                    let ancestor_last_ends_with_newline =
                        ancestor.last().map_or(false, |l| l.ends_with('\n'));
                    let ours_last_ends_with_newline =
                        ours.last().map_or(false, |l| l.ends_with('\n'));
                    let theirs_last_ends_with_newline =
                        theirs.last().map_or(false, |l| l.ends_with('\n'));

                    let (add_after_lines, add_after_right_marker) =
                        if ancestor_last_ends_with_newline
                            && ours_last_ends_with_newline
                            && theirs_last_ends_with_newline
                        {
                            (false, true)
                        } else {
                            (true, false)
                        };

                    add_conflict_marker(&mut output, '<', marker_len, Some("ours"));
                    add_lines(&mut output, ours);
                    if add_after_lines {
                        output.push('\n');
                    }

                    if let ConflictStyle::Diff3 = style {
                        add_conflict_marker(&mut output, '|', marker_len, Some("original"));
                        add_lines(&mut output, ancestor);
                        if add_after_lines {
                            output.push('\n');
                        }
                    }

                    add_conflict_marker(&mut output, '=', marker_len, None);

                    add_lines(&mut output, theirs);
                    if add_after_lines {
                        output.push('\n');
                    }
                    add_conflict_marker(&mut output, '>', marker_len, Some("theirs"));
                    if !add_after_right_marker {
                        output
                            .pop()
                            .expect("a `\n` is always added by the `add_conflict_marker` above");
                    }
                } else {
                    add_conflict_marker(&mut output, '<', marker_len, Some("ours"));
                    add_lines(&mut output, ours);

                    if let ConflictStyle::Diff3 = style {
                        add_conflict_marker(&mut output, '|', marker_len, Some("original"));
                        add_lines(&mut output, ancestor);
                    }

                    add_conflict_marker(&mut output, '=', marker_len, None);
                    add_lines(&mut output, theirs);
                    add_conflict_marker(&mut output, '>', marker_len, Some("theirs"));
                }

                conflicts += 1;
            }
            MergeRange::Ours(range) => {
                add_lines(&mut output, &ours[range.range()]);
            }
            MergeRange::Theirs(range) => {
                add_lines(&mut output, &theirs[range.range()]);
            }
            MergeRange::Both(range, _) => {
                add_lines(&mut output, &ours[range.range()]);
            }
        }
    }

    if conflicts != 0 {
        Err(output)
    } else {
        Ok(output)
    }
}

fn add_lines(dest: &mut String, lines: &[&str]) {
    dest.extend(lines.iter().copied());
}

fn add_conflict_marker(
    output: &mut String,
    marker: char,
    marker_len: usize,
    filename: Option<&str>,
) {
    for _ in 0..marker_len {
        output.push(marker);
    }

    if let Some(filename) = filename {
        output.push(' ');
        output.push_str(filename);
    }
    output.push('\n');
}

fn output_result_bytes<'a, T: ?Sized>(
    ancestor: &[&'a [u8]],
    ours: &[&'a [u8]],
    theirs: &[&'a [u8]],
    merge: &[MergeRange<T>],
    marker_len: usize,
    style: ConflictStyle,
) -> Result<Vec<u8>, Vec<u8>> {
    let mut conflicts = 0;
    let mut output: Vec<u8> = Vec::new();

    for (range_idx, merge_range) in merge.iter().enumerate() {
        match merge_range {
            MergeRange::Equal(range, ..) => {
                add_lines_bytes(&mut output, &ancestor[range.range()]);
            }
            MergeRange::Conflict(ancestor_range, ours_range, theirs_range) => {
                let ancestor = &ancestor[ancestor_range.range()];
                let ours = &ours[ours_range.range()];
                let theirs = &theirs[theirs_range.range()];

                if range_idx == merge.len() - 1 {
                    let ancestor_last_ends_with_newline =
                        ancestor.last().map_or(false, |l| l.ends_with(b"\n"));
                    let ours_last_ends_with_newline =
                        ours.last().map_or(false, |l| l.ends_with(b"\n"));
                    let theirs_last_ends_with_newline =
                        theirs.last().map_or(false, |l| l.ends_with(b"\n"));

                    let (add_after_lines, add_after_right_marker) =
                        if ancestor_last_ends_with_newline
                            && ours_last_ends_with_newline
                            && theirs_last_ends_with_newline
                        {
                            (false, true)
                        } else {
                            (true, false)
                        };

                    add_conflict_marker_bytes(&mut output, b'<', marker_len, Some(b"ours"));
                    add_lines_bytes(&mut output, ours);
                    if add_after_lines {
                        output.push(b'\n');
                    }

                    if let ConflictStyle::Diff3 = style {
                        add_conflict_marker_bytes(&mut output, b'|', marker_len, Some(b"original"));
                        add_lines_bytes(&mut output, ancestor);
                        if add_after_lines {
                            output.push(b'\n');
                        }
                    }

                    add_conflict_marker_bytes(&mut output, b'=', marker_len, None);

                    add_lines_bytes(&mut output, theirs);
                    if add_after_lines {
                        output.push(b'\n');
                    }
                    add_conflict_marker_bytes(&mut output, b'>', marker_len, Some(b"theirs"));
                    if !add_after_right_marker {
                        output.pop().expect(
                            "a `\n` is always added by the `add_conflict_marker_bytes` above",
                        );
                    }
                } else {
                    add_conflict_marker_bytes(&mut output, b'<', marker_len, Some(b"ours"));
                    add_lines_bytes(&mut output, ours);

                    if let ConflictStyle::Diff3 = style {
                        add_conflict_marker_bytes(&mut output, b'|', marker_len, Some(b"original"));
                        add_lines_bytes(&mut output, ancestor);
                    }

                    add_conflict_marker_bytes(&mut output, b'=', marker_len, None);
                    add_lines_bytes(&mut output, theirs);
                    add_conflict_marker_bytes(&mut output, b'>', marker_len, Some(b"theirs"));
                }

                conflicts += 1;
            }
            MergeRange::Ours(range) => {
                add_lines_bytes(&mut output, &ours[range.range()]);
            }
            MergeRange::Theirs(range) => {
                add_lines_bytes(&mut output, &theirs[range.range()]);
            }
            MergeRange::Both(range, _) => {
                add_lines_bytes(&mut output, &ours[range.range()]);
            }
        }
    }

    if conflicts != 0 {
        Err(output)
    } else {
        Ok(output)
    }
}

fn add_lines_bytes(output: &mut Vec<u8>, lines: &[&[u8]]) {
    lines.iter().for_each(|line| output.extend_from_slice(line));
}

fn add_conflict_marker_bytes(
    output: &mut Vec<u8>,
    marker: u8,
    marker_len: usize,
    filename: Option<&[u8]>,
) {
    for _ in 0..marker_len {
        output.push(marker);
    }

    if let Some(filename) = filename {
        output.push(b' ');
        output.extend_from_slice(filename);
    }
    output.push(b'\n');
}