diffy_fork_filenames/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(_), Some(_), None)
457        | (Some(_), None, Some(_))
458        | (Some(_), None, None)
459        | (None, None, None) => None,
460    }
461}
462
463#[allow(clippy::needless_lifetimes)]
464fn cleanup_conflicts<'ancestor, 'ours, 'theirs, T: ?Sized + SliceLike + PartialEq>(
465    solution: &mut [MergeRange<'ancestor, 'ours, 'theirs, T>],
466) {
467    let mut pointer = 0;
468
469    // TODO this could probably be more sophisticated:
470    // e.g. run the diff algorithm on the conflict area
471    while let Some(&merge) = solution.get(pointer) {
472        if let MergeRange::Conflict(ancestor, ours, theirs) = merge {
473            // If the ranges in the conflict end up being the same on both sides then we can
474            // eliminate the conflict
475            if ours.as_slice() == theirs.as_slice() {
476                solution[pointer] = MergeRange::Both(ours, theirs);
477            // If either ours or theirs exactly matches ancestor then we can also eliminate the
478            // conflict
479            } else if ancestor.as_slice() == ours.as_slice() {
480                solution[pointer] = MergeRange::Theirs(theirs);
481            } else if ancestor.as_slice() == theirs.as_slice() {
482                solution[pointer] = MergeRange::Ours(ours);
483            }
484        }
485        pointer += 1;
486    }
487}
488
489fn output_result<'a, T: ?Sized>(
490    ancestor: &[&'a str],
491    ours: &[&'a str],
492    theirs: &[&'a str],
493    merge: &[MergeRange<T>],
494    marker_len: usize,
495    style: ConflictStyle,
496) -> Result<String, String> {
497    let mut conflicts = 0;
498    let mut output = String::new();
499
500    for merge_range in merge {
501        match merge_range {
502            MergeRange::Equal(range, ..) => {
503                output.extend(ancestor[range.range()].iter().copied());
504            }
505            MergeRange::Conflict(ancestor_range, ours_range, theirs_range) => {
506                add_conflict_marker(&mut output, '<', marker_len, Some("ours"));
507                output.extend(ours[ours_range.range()].iter().copied());
508
509                if let ConflictStyle::Diff3 = style {
510                    add_conflict_marker(&mut output, '|', marker_len, Some("original"));
511                    output.extend(ancestor[ancestor_range.range()].iter().copied());
512                }
513
514                add_conflict_marker(&mut output, '=', marker_len, None);
515                output.extend(theirs[theirs_range.range()].iter().copied());
516                add_conflict_marker(&mut output, '>', marker_len, Some("theirs"));
517                conflicts += 1;
518            }
519            MergeRange::Ours(range) => {
520                output.extend(ours[range.range()].iter().copied());
521            }
522            MergeRange::Theirs(range) => {
523                output.extend(theirs[range.range()].iter().copied());
524            }
525            MergeRange::Both(range, _) => {
526                output.extend(ours[range.range()].iter().copied());
527            }
528        }
529    }
530
531    if conflicts != 0 {
532        Err(output)
533    } else {
534        Ok(output)
535    }
536}
537
538fn add_conflict_marker(
539    output: &mut String,
540    marker: char,
541    marker_len: usize,
542    filename: Option<&str>,
543) {
544    for _ in 0..marker_len {
545        output.push(marker);
546    }
547
548    if let Some(filename) = filename {
549        output.push(' ');
550        output.push_str(filename);
551    }
552    output.push('\n');
553}
554
555fn output_result_bytes<'a, T: ?Sized>(
556    ancestor: &[&'a [u8]],
557    ours: &[&'a [u8]],
558    theirs: &[&'a [u8]],
559    merge: &[MergeRange<T>],
560    marker_len: usize,
561    style: ConflictStyle,
562) -> Result<Vec<u8>, Vec<u8>> {
563    let mut conflicts = 0;
564    let mut output: Vec<u8> = Vec::new();
565
566    for merge_range in merge {
567        match merge_range {
568            MergeRange::Equal(range, ..) => {
569                ancestor[range.range()]
570                    .iter()
571                    .for_each(|line| output.extend_from_slice(line));
572            }
573            MergeRange::Conflict(ancestor_range, ours_range, theirs_range) => {
574                add_conflict_marker_bytes(&mut output, b'<', marker_len, Some(b"ours"));
575                ours[ours_range.range()]
576                    .iter()
577                    .for_each(|line| output.extend_from_slice(line));
578
579                if let ConflictStyle::Diff3 = style {
580                    add_conflict_marker_bytes(&mut output, b'|', marker_len, Some(b"original"));
581                    ancestor[ancestor_range.range()]
582                        .iter()
583                        .for_each(|line| output.extend_from_slice(line));
584                }
585
586                add_conflict_marker_bytes(&mut output, b'=', marker_len, None);
587                theirs[theirs_range.range()]
588                    .iter()
589                    .for_each(|line| output.extend_from_slice(line));
590                add_conflict_marker_bytes(&mut output, b'>', marker_len, Some(b"theirs"));
591                conflicts += 1;
592            }
593            MergeRange::Ours(range) => {
594                ours[range.range()]
595                    .iter()
596                    .for_each(|line| output.extend_from_slice(line));
597            }
598            MergeRange::Theirs(range) => {
599                theirs[range.range()]
600                    .iter()
601                    .for_each(|line| output.extend_from_slice(line));
602            }
603            MergeRange::Both(range, _) => {
604                ours[range.range()]
605                    .iter()
606                    .for_each(|line| output.extend_from_slice(line));
607            }
608        }
609    }
610
611    if conflicts != 0 {
612        Err(output)
613    } else {
614        Ok(output)
615    }
616}
617
618fn add_conflict_marker_bytes(
619    output: &mut Vec<u8>,
620    marker: u8,
621    marker_len: usize,
622    filename: Option<&[u8]>,
623) {
624    for _ in 0..marker_len {
625        output.push(marker);
626    }
627
628    if let Some(filename) = filename {
629        output.push(b' ');
630        output.extend_from_slice(filename);
631    }
632    output.push(b'\n');
633}
diffy_fork_filenames/merge/mod.rs

diffy_fork_filenames/merge/
mod.rs
