diffy/merge/
mod.rs

1use crate::{
2    diff::DiffOptions,
3    range::{DiffRange, Range, SliceLike},
4    utils::Classifier,
5};
6use std::{cmp, fmt};
7
8#[cfg(test)]
9mod tests;
10
11const DEFAULT_CONFLICT_MARKER_LENGTH: usize = 7;
12
13enum Diff3Range<'ancestor, 'ours, 'theirs, T: ?Sized> {
14    Equal(Range<'ancestor, T>, Range<'ours, T>, Range<'theirs, T>),
15    Ancestor(Range<'ancestor, T>),
16    AncestorOurs(Range<'ancestor, T>, Range<'ours, T>),
17    AncestorTheirs(Range<'ancestor, T>, Range<'theirs, T>),
18    Ours(Range<'ours, T>),
19    Theirs(Range<'theirs, T>),
20}
21
22impl<T: ?Sized + fmt::Debug + SliceLike> fmt::Debug for Diff3Range<'_, '_, '_, T> {
23    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
24        match self {
25            Diff3Range::Equal(range, ..) => write!(f, "Equal: {:?}", range.as_slice()),
26            Diff3Range::Ancestor(range) => write!(f, "Ancestor: {:?}", range.as_slice()),
27            Diff3Range::AncestorOurs(range, ..) => {
28                write!(f, "AncestorOurs: {:?}", range.as_slice())
29            }
30            Diff3Range::AncestorTheirs(range, ..) => {
31                write!(f, "AncestorTheirs: {:?}", range.as_slice())
32            }
33            Diff3Range::Ours(range) => write!(f, "Ours: {:?}", range.as_slice()),
34            Diff3Range::Theirs(range) => write!(f, "Theirs: {:?}", range.as_slice()),
35        }
36    }
37}
38
39impl<T: ?Sized> Copy for Diff3Range<'_, '_, '_, T> {}
40
41impl<T: ?Sized> Clone for Diff3Range<'_, '_, '_, T> {
42    fn clone(&self) -> Self {
43        *self
44    }
45}
46
47enum MergeRange<'ancestor, 'ours, 'theirs, T: ?Sized> {
48    Equal(Range<'ancestor, T>, Range<'ours, T>, Range<'theirs, T>),
49    Conflict(Range<'ancestor, T>, Range<'ours, T>, Range<'theirs, T>),
50    Ours(Range<'ours, T>),
51    Theirs(Range<'theirs, T>),
52    Both(Range<'ours, T>, Range<'theirs, T>),
53}
54
55impl<T: ?Sized + fmt::Debug + SliceLike> fmt::Debug for MergeRange<'_, '_, '_, T> {
56    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
57        match self {
58            MergeRange::Equal(range, ..) => write!(f, "Equal: {:?}", range.as_slice()),
59            MergeRange::Conflict(ancestor, ours, theirs) => write!(
60                f,
61                "Conflict: ancestor: {:?} ours: {:?} theirs: {:?}",
62                ancestor.as_slice(),
63                ours.as_slice(),
64                theirs.as_slice()
65            ),
66            MergeRange::Ours(range) => write!(f, "Ours: {:?}", range.as_slice()),
67            MergeRange::Theirs(range) => write!(f, "Theirs: {:?}", range.as_slice()),
68            MergeRange::Both(ours, theirs) => write!(
69                f,
70                "Both: ours: {:?} theirs: {:?}",
71                ours.as_slice(),
72                theirs.as_slice()
73            ),
74        }
75    }
76}
77
78impl<T: ?Sized> Copy for MergeRange<'_, '_, '_, T> {}
79
80impl<T: ?Sized> Clone for MergeRange<'_, '_, '_, T> {
81    fn clone(&self) -> Self {
82        *self
83    }
84}
85
86/// Style used when rendering a conflict
87#[derive(Copy, Clone, Debug)]
88pub enum ConflictStyle {
89    /// Renders conflicting lines from both files, separated by conflict markers.
90    ///
91    /// ```console
92    /// <<<<<<< A
93    /// lines in file A
94    /// =======
95    /// lines in file B
96    /// >>>>>>> B
97    /// ```
98    Merge,
99
100    /// Renders conflicting lines from both files including lines from the original files,
101    /// separated by conflict markers.
102    ///
103    /// ```console
104    /// <<<<<<< A
105    /// lines in file A
106    /// ||||||| Original
107    /// lines in Original file
108    /// =======
109    /// lines in file B
110    /// >>>>>>> B
111    /// ```
112    Diff3,
113}
114
115/// A collection of options for modifying the way a merge is performed
116#[derive(Debug)]
117pub struct MergeOptions {
118    conflict_marker_length: usize,
119    style: ConflictStyle,
120}
121
122impl MergeOptions {
123    /// Constructs a new `MergeOptions` with default settings
124    ///
125    /// ## Defaults
126    /// * conflict_marker_length = 7
127    /// * style = ConflictStyle::Diff3
128    pub fn new() -> Self {
129        Self {
130            conflict_marker_length: DEFAULT_CONFLICT_MARKER_LENGTH,
131            style: ConflictStyle::Diff3,
132        }
133    }
134
135    /// Set the length of the conflict markers used when displaying a merge conflict
136    pub fn set_conflict_marker_length(&mut self, conflict_marker_length: usize) -> &mut Self {
137        self.conflict_marker_length = conflict_marker_length;
138        self
139    }
140
141    /// Set the conflict style used when displaying a merge conflict
142    pub fn set_conflict_style(&mut self, style: ConflictStyle) -> &mut Self {
143        self.style = style;
144        self
145    }
146
147    /// Merge two files, given a common ancestor, based on the configured options
148    pub fn merge<'a>(
149        &self,
150        ancestor: &'a str,
151        ours: &'a str,
152        theirs: &'a str,
153    ) -> Result<String, String> {
154        let mut classifier = Classifier::default();
155        let (ancestor_lines, ancestor_ids) = classifier.classify_lines(ancestor);
156        let (our_lines, our_ids) = classifier.classify_lines(ours);
157        let (their_lines, their_ids) = classifier.classify_lines(theirs);
158
159        let opts = DiffOptions::default();
160        let our_solution = opts.diff_slice(&ancestor_ids, &our_ids);
161        let their_solution = opts.diff_slice(&ancestor_ids, &their_ids);
162
163        let merged = merge_solutions(&our_solution, &their_solution);
164        let mut merge = diff3_range_to_merge_range(&merged);
165
166        cleanup_conflicts(&mut merge);
167
168        output_result(
169            &ancestor_lines,
170            &our_lines,
171            &their_lines,
172            &merge,
173            self.conflict_marker_length,
174            self.style,
175        )
176    }
177
178    /// Perform a 3-way merge between potentially non-utf8 texts
179    pub fn merge_bytes<'a>(
180        &self,
181        ancestor: &'a [u8],
182        ours: &'a [u8],
183        theirs: &'a [u8],
184    ) -> Result<Vec<u8>, Vec<u8>> {
185        let mut classifier = Classifier::default();
186        let (ancestor_lines, ancestor_ids) = classifier.classify_lines(ancestor);
187        let (our_lines, our_ids) = classifier.classify_lines(ours);
188        let (their_lines, their_ids) = classifier.classify_lines(theirs);
189
190        let opts = DiffOptions::default();
191        let our_solution = opts.diff_slice(&ancestor_ids, &our_ids);
192        let their_solution = opts.diff_slice(&ancestor_ids, &their_ids);
193
194        let merged = merge_solutions(&our_solution, &their_solution);
195        let mut merge = diff3_range_to_merge_range(&merged);
196
197        cleanup_conflicts(&mut merge);
198
199        output_result_bytes(
200            &ancestor_lines,
201            &our_lines,
202            &their_lines,
203            &merge,
204            self.conflict_marker_length,
205            self.style,
206        )
207    }
208}
209
210impl Default for MergeOptions {
211    fn default() -> Self {
212        Self::new()
213    }
214}
215
216/// Merge two files given a common ancestor.
217///
218/// Returns `Ok(String)` upon a successful merge.
219/// Returns `Err(String)` if there were conflicts, with the conflicting
220/// regions marked with conflict markers.
221///
222/// ## Merging two files without conflicts
223/// ```
224/// # use diffy::merge;
225/// let original = "\
226/// Devotion
227/// Dominion
228/// Odium
229/// Preservation
230/// Ruin
231/// Cultivation
232/// Honor
233/// Endowment
234/// Autonomy
235/// Ambition
236/// ";
237/// let a = "\
238/// Odium
239/// Preservation
240/// Ruin
241/// Cultivation
242/// Endowment
243/// Autonomy
244/// ";
245/// let b = "\
246/// Devotion
247/// Dominion
248/// Odium
249/// Harmony
250/// Cultivation
251/// Honor
252/// Endowment
253/// Autonomy
254/// Ambition
255/// ";
256///
257/// let expected = "\
258/// Odium
259/// Harmony
260/// Cultivation
261/// Endowment
262/// Autonomy
263/// ";
264///
265/// assert_eq!(merge(original, a, b).unwrap(), expected);
266/// ```
267pub fn merge<'a>(ancestor: &'a str, ours: &'a str, theirs: &'a str) -> Result<String, String> {
268    MergeOptions::default().merge(ancestor, ours, theirs)
269}
270
271/// Perform a 3-way merge between potentially non-utf8 texts
272pub fn merge_bytes<'a>(
273    ancestor: &'a [u8],
274    ours: &'a [u8],
275    theirs: &'a [u8],
276) -> Result<Vec<u8>, Vec<u8>> {
277    MergeOptions::default().merge_bytes(ancestor, ours, theirs)
278}
279
280fn merge_solutions<'ancestor, 'ours, 'theirs, T: ?Sized + SliceLike>(
281    our_solution: &[DiffRange<'ancestor, 'ours, T>],
282    their_solution: &[DiffRange<'ancestor, 'theirs, T>],
283) -> Vec<Diff3Range<'ancestor, 'ours, 'theirs, T>> {
284    let mut our_solution = our_solution.iter().copied();
285    let mut their_solution = their_solution.iter().copied();
286    let mut ours = our_solution.next();
287    let mut theirs = their_solution.next();
288
289    let mut solution = Vec::new();
290
291    while ours.is_some() || theirs.is_some() {
292        let merge_range = match (ours, theirs) {
293            //
294            // Inserts can't easily be checked to see if they match each other
295            //
296            (Some(DiffRange::Insert(range)), _) => {
297                ours.take();
298                Diff3Range::Ours(range)
299            }
300            (_, Some(DiffRange::Insert(range))) => {
301                theirs.take();
302                Diff3Range::Theirs(range)
303            }
304
305            (
306                Some(DiffRange::Equal(ancestor1, our_range)),
307                Some(DiffRange::Equal(ancestor2, their_range)),
308            ) => {
309                assert_eq!(ancestor1.offset(), ancestor2.offset());
310                let len = cmp::min(ancestor1.len(), ancestor2.len());
311
312                shrink_front(&mut ours, len);
313                shrink_front(&mut theirs, len);
314
315                Diff3Range::Equal(
316                    ancestor1.slice(..len),
317                    our_range.slice(..len),
318                    their_range.slice(..len),
319                )
320            }
321
322            (Some(DiffRange::Equal(ancestor1, our_range)), Some(DiffRange::Delete(ancestor2))) => {
323                assert_eq!(ancestor1.offset(), ancestor2.offset());
324                let len = cmp::min(ancestor1.len(), ancestor2.len());
325
326                shrink_front(&mut ours, len);
327                shrink_front(&mut theirs, len);
328
329                Diff3Range::AncestorOurs(ancestor1.slice(..len), our_range.slice(..len))
330            }
331
332            (
333                Some(DiffRange::Delete(ancestor1)),
334                Some(DiffRange::Equal(ancestor2, their_range)),
335            ) => {
336                assert_eq!(ancestor1.offset(), ancestor2.offset());
337                let len = cmp::min(ancestor1.len(), ancestor2.len());
338
339                shrink_front(&mut ours, len);
340                shrink_front(&mut theirs, len);
341
342                Diff3Range::AncestorTheirs(ancestor2.slice(..len), their_range.slice(..len))
343            }
344
345            (Some(DiffRange::Delete(ancestor1)), Some(DiffRange::Delete(ancestor2))) => {
346                assert_eq!(ancestor1.offset(), ancestor2.offset());
347                let len = cmp::min(ancestor1.len(), ancestor2.len());
348
349                shrink_front(&mut ours, len);
350                shrink_front(&mut theirs, len);
351
352                Diff3Range::Ancestor(ancestor1.slice(..len))
353            }
354
355            //
356            // Unreachable cases
357            //
358            (Some(DiffRange::Equal(..)), None)
359            | (Some(DiffRange::Delete(_)), None)
360            | (None, Some(DiffRange::Equal(..)))
361            | (None, Some(DiffRange::Delete(_)))
362            | (None, None) => unreachable!("Equal/Delete should match up"),
363        };
364
365        solution.push(merge_range);
366
367        if ours.map_or(true, |range| range.is_empty()) {
368            ours = our_solution.next();
369        }
370        if theirs.map_or(true, |range| range.is_empty()) {
371            theirs = their_solution.next();
372        }
373    }
374
375    solution
376}
377
378fn shrink_front<T: ?Sized + SliceLike>(maybe_range: &mut Option<DiffRange<T>>, len: usize) {
379    if let Some(range) = maybe_range {
380        range.shrink_front(len)
381    }
382}
383
384fn diff3_range_to_merge_range<'ancestor, 'ours, 'theirs, T: ?Sized + SliceLike>(
385    solution: &[Diff3Range<'ancestor, 'ours, 'theirs, T>],
386) -> Vec<MergeRange<'ancestor, 'ours, 'theirs, T>> {
387    let mut ancestor: Option<Range<'ancestor, T>> = None;
388    let mut ours: Option<Range<'ours, T>> = None;
389    let mut theirs: Option<Range<'theirs, T>> = None;
390
391    let mut merge = Vec::new();
392
393    for &diff3 in solution {
394        match diff3 {
395            Diff3Range::Equal(ancestor_range, our_range, their_range) => {
396                if let Some(merge_range) =
397                    create_merge_range(ancestor.take(), ours.take(), theirs.take())
398                {
399                    merge.push(merge_range);
400                }
401                merge.push(MergeRange::Equal(ancestor_range, our_range, their_range));
402            }
403            Diff3Range::Ancestor(range) => {
404                set_or_merge_range(&mut ancestor, range);
405                set_or_merge_range(&mut ours, Range::empty());
406                set_or_merge_range(&mut theirs, Range::empty());
407            }
408            Diff3Range::AncestorOurs(ancestor_range, our_range) => {
409                set_or_merge_range(&mut ancestor, ancestor_range);
410                set_or_merge_range(&mut ours, our_range);
411            }
412            Diff3Range::AncestorTheirs(ancestor_range, their_range) => {
413                set_or_merge_range(&mut ancestor, ancestor_range);
414                set_or_merge_range(&mut theirs, their_range);
415            }
416            Diff3Range::Ours(range) => set_or_merge_range(&mut ours, range),
417            Diff3Range::Theirs(range) => set_or_merge_range(&mut theirs, range),
418        }
419    }
420
421    if let Some(merge_range) = create_merge_range(ancestor.take(), ours.take(), theirs.take()) {
422        merge.push(merge_range);
423    }
424
425    merge
426}
427
428fn set_or_merge_range<'a, T: ?Sized>(range1: &mut Option<Range<'a, T>>, range2: Range<'a, T>) {
429    if let Some(range1) = range1 {
430        if range1.is_empty() {
431            *range1 = range2;
432        } else if !range2.is_empty() {
433            assert_eq!(range1.offset() + range1.len(), range2.offset());
434            range1.grow_down(range2.len());
435        }
436    } else {
437        *range1 = Some(range2);
438    }
439}
440
441fn create_merge_range<'ancestor, 'ours, 'theirs, T: ?Sized + SliceLike>(
442    ancestor: Option<Range<'ancestor, T>>,
443    ours: Option<Range<'ours, T>>,
444    theirs: Option<Range<'theirs, T>>,
445) -> Option<MergeRange<'ancestor, 'ours, 'theirs, T>> {
446    match (ancestor, ours, theirs) {
447        (Some(ancestor), Some(ours), Some(theirs)) => {
448            Some(MergeRange::Conflict(ancestor, ours, theirs))
449        }
450        (None, Some(ours), Some(theirs)) => {
451            Some(MergeRange::Conflict(Range::empty(), ours, theirs))
452        }
453        (None, Some(ours), None) => Some(MergeRange::Ours(ours)),
454        (None, None, Some(theirs)) => Some(MergeRange::Theirs(theirs)),
455
456        (Some(ancestor), None, Some(theirs)) => {
457            Some(MergeRange::Conflict(ancestor, Range::empty(), theirs))
458        }
459        (Some(ancestor), Some(ours), None) => {
460            Some(MergeRange::Conflict(ancestor, ours, Range::empty()))
461        }
462
463        (Some(_), None, None) | (None, None, None) => None,
464    }
465}
466
467#[allow(clippy::needless_lifetimes)]
468fn cleanup_conflicts<'ancestor, 'ours, 'theirs, T: ?Sized + SliceLike + PartialEq>(
469    solution: &mut [MergeRange<'ancestor, 'ours, 'theirs, T>],
470) {
471    let mut pointer = 0;
472
473    // TODO this could probably be more sophisticated:
474    // e.g. run the diff algorithm on the conflict area
475    while let Some(&merge) = solution.get(pointer) {
476        if let MergeRange::Conflict(ancestor, ours, theirs) = merge {
477            // If the ranges in the conflict end up being the same on both sides then we can
478            // eliminate the conflict
479            if ours.as_slice() == theirs.as_slice() {
480                solution[pointer] = MergeRange::Both(ours, theirs);
481            // If either ours or theirs exactly matches ancestor then we can also eliminate the
482            // conflict
483            } else if ancestor.as_slice() == ours.as_slice() {
484                solution[pointer] = MergeRange::Theirs(theirs);
485            } else if ancestor.as_slice() == theirs.as_slice() {
486                solution[pointer] = MergeRange::Ours(ours);
487            }
488        }
489        pointer += 1;
490    }
491}
492
493fn output_result<'a, T: ?Sized>(
494    ancestor: &[&'a str],
495    ours: &[&'a str],
496    theirs: &[&'a str],
497    merge: &[MergeRange<T>],
498    marker_len: usize,
499    style: ConflictStyle,
500) -> Result<String, String> {
501    let mut conflicts = 0;
502    let mut output = String::new();
503
504    for merge_range in merge {
505        match merge_range {
506            MergeRange::Equal(range, ..) => {
507                output.extend(ancestor[range.range()].iter().copied());
508            }
509            MergeRange::Conflict(ancestor_range, ours_range, theirs_range) => {
510                add_conflict_marker(&mut output, '<', marker_len, Some("ours"));
511                output.extend(ours[ours_range.range()].iter().copied());
512
513                if let ConflictStyle::Diff3 = style {
514                    add_conflict_marker(&mut output, '|', marker_len, Some("original"));
515                    output.extend(ancestor[ancestor_range.range()].iter().copied());
516                }
517
518                add_conflict_marker(&mut output, '=', marker_len, None);
519                output.extend(theirs[theirs_range.range()].iter().copied());
520                add_conflict_marker(&mut output, '>', marker_len, Some("theirs"));
521                conflicts += 1;
522            }
523            MergeRange::Ours(range) => {
524                output.extend(ours[range.range()].iter().copied());
525            }
526            MergeRange::Theirs(range) => {
527                output.extend(theirs[range.range()].iter().copied());
528            }
529            MergeRange::Both(range, _) => {
530                output.extend(ours[range.range()].iter().copied());
531            }
532        }
533    }
534
535    if conflicts != 0 {
536        Err(output)
537    } else {
538        Ok(output)
539    }
540}
541
542fn add_conflict_marker(
543    output: &mut String,
544    marker: char,
545    marker_len: usize,
546    filename: Option<&str>,
547) {
548    for _ in 0..marker_len {
549        output.push(marker);
550    }
551
552    if let Some(filename) = filename {
553        output.push(' ');
554        output.push_str(filename);
555    }
556    output.push('\n');
557}
558
559fn output_result_bytes<'a, T: ?Sized>(
560    ancestor: &[&'a [u8]],
561    ours: &[&'a [u8]],
562    theirs: &[&'a [u8]],
563    merge: &[MergeRange<T>],
564    marker_len: usize,
565    style: ConflictStyle,
566) -> Result<Vec<u8>, Vec<u8>> {
567    let mut conflicts = 0;
568    let mut output: Vec<u8> = Vec::new();
569
570    for merge_range in merge {
571        match merge_range {
572            MergeRange::Equal(range, ..) => {
573                ancestor[range.range()]
574                    .iter()
575                    .for_each(|line| output.extend_from_slice(line));
576            }
577            MergeRange::Conflict(ancestor_range, ours_range, theirs_range) => {
578                add_conflict_marker_bytes(&mut output, b'<', marker_len, Some(b"ours"));
579                ours[ours_range.range()]
580                    .iter()
581                    .for_each(|line| output.extend_from_slice(line));
582
583                if let ConflictStyle::Diff3 = style {
584                    add_conflict_marker_bytes(&mut output, b'|', marker_len, Some(b"original"));
585                    ancestor[ancestor_range.range()]
586                        .iter()
587                        .for_each(|line| output.extend_from_slice(line));
588                }
589
590                add_conflict_marker_bytes(&mut output, b'=', marker_len, None);
591                theirs[theirs_range.range()]
592                    .iter()
593                    .for_each(|line| output.extend_from_slice(line));
594                add_conflict_marker_bytes(&mut output, b'>', marker_len, Some(b"theirs"));
595                conflicts += 1;
596            }
597            MergeRange::Ours(range) => {
598                ours[range.range()]
599                    .iter()
600                    .for_each(|line| output.extend_from_slice(line));
601            }
602            MergeRange::Theirs(range) => {
603                theirs[range.range()]
604                    .iter()
605                    .for_each(|line| output.extend_from_slice(line));
606            }
607            MergeRange::Both(range, _) => {
608                ours[range.range()]
609                    .iter()
610                    .for_each(|line| output.extend_from_slice(line));
611            }
612        }
613    }
614
615    if conflicts != 0 {
616        Err(output)
617    } else {
618        Ok(output)
619    }
620}
621
622fn add_conflict_marker_bytes(
623    output: &mut Vec<u8>,
624    marker: u8,
625    marker_len: usize,
626    filename: Option<&[u8]>,
627) {
628    for _ in 0..marker_len {
629        output.push(marker);
630    }
631
632    if let Some(filename) = filename {
633        output.push(b' ');
634        output.extend_from_slice(filename);
635    }
636    output.push(b'\n');
637}
diffy/merge/mod.rs

diffy/merge/
mod.rs
