jj_lib/
files.rs

1// Copyright 2020 The Jujutsu Authors
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// https://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#![expect(missing_docs)]
16
17use std::borrow::Borrow;
18use std::collections::VecDeque;
19use std::iter;
20use std::mem;
21
22use bstr::BStr;
23use bstr::BString;
24use either::Either;
25use itertools::Itertools as _;
26
27use crate::diff::ContentDiff;
28use crate::diff::DiffHunk;
29use crate::diff::DiffHunkKind;
30use crate::merge::Merge;
31use crate::merge::SameChange;
32use crate::tree_merge::MergeOptions;
33
34/// A diff line which may contain small hunks originating from both sides.
35#[derive(PartialEq, Eq, Clone, Debug)]
36pub struct DiffLine<'a> {
37    pub line_number: DiffLineNumber,
38    pub hunks: Vec<(DiffLineHunkSide, &'a BStr)>,
39}
40
41impl DiffLine<'_> {
42    pub fn has_left_content(&self) -> bool {
43        self.hunks
44            .iter()
45            .any(|&(side, _)| side != DiffLineHunkSide::Right)
46    }
47
48    pub fn has_right_content(&self) -> bool {
49        self.hunks
50            .iter()
51            .any(|&(side, _)| side != DiffLineHunkSide::Left)
52    }
53
54    pub fn is_unmodified(&self) -> bool {
55        self.hunks
56            .iter()
57            .all(|&(side, _)| side == DiffLineHunkSide::Both)
58    }
59
60    fn take(&mut self) -> Self {
61        Self {
62            line_number: self.line_number,
63            hunks: mem::take(&mut self.hunks),
64        }
65    }
66}
67
68#[derive(Clone, Copy, Debug, Eq, PartialEq)]
69pub struct DiffLineNumber {
70    pub left: u32,
71    pub right: u32,
72}
73
74/// Which side a `DiffLine` hunk belongs to?
75#[derive(Clone, Copy, Debug, Eq, PartialEq)]
76pub enum DiffLineHunkSide {
77    Both,
78    Left,
79    Right,
80}
81
82pub struct DiffLineIterator<'a, I> {
83    diff_hunks: iter::Fuse<I>,
84    current_line: DiffLine<'a>,
85    queued_lines: VecDeque<DiffLine<'a>>,
86}
87
88impl<'a, I> DiffLineIterator<'a, I>
89where
90    I: Iterator,
91    I::Item: Borrow<DiffHunk<'a>>,
92{
93    /// Iterates `diff_hunks` by line. Each hunk should have exactly two inputs.
94    pub fn new(diff_hunks: I) -> Self {
95        let line_number = DiffLineNumber { left: 1, right: 1 };
96        Self::with_line_number(diff_hunks, line_number)
97    }
98
99    /// Iterates `diff_hunks` by line. Each hunk should have exactly two inputs.
100    /// Hunk's line numbers start from the given `line_number`.
101    pub fn with_line_number(diff_hunks: I, line_number: DiffLineNumber) -> Self {
102        let current_line = DiffLine {
103            line_number,
104            hunks: vec![],
105        };
106        Self {
107            diff_hunks: diff_hunks.fuse(),
108            current_line,
109            queued_lines: VecDeque::new(),
110        }
111    }
112}
113
114impl<I> DiffLineIterator<'_, I> {
115    /// Returns line number of the next hunk. After all hunks are consumed, this
116    /// returns the next line number if the last hunk ends with newline.
117    pub fn next_line_number(&self) -> DiffLineNumber {
118        let next_line = self.queued_lines.front().unwrap_or(&self.current_line);
119        next_line.line_number
120    }
121}
122
123impl<'a, I> Iterator for DiffLineIterator<'a, I>
124where
125    I: Iterator,
126    I::Item: Borrow<DiffHunk<'a>>,
127{
128    type Item = DiffLine<'a>;
129
130    fn next(&mut self) -> Option<Self::Item> {
131        // TODO: Should we attempt to interpret as utf-8 and otherwise break only at
132        // newlines?
133        while self.queued_lines.is_empty() {
134            let Some(hunk) = self.diff_hunks.next() else {
135                break;
136            };
137            let hunk = hunk.borrow();
138            match hunk.kind {
139                DiffHunkKind::Matching => {
140                    // TODO: add support for unmatched contexts?
141                    debug_assert!(hunk.contents.iter().all_equal());
142                    let text = hunk.contents[0];
143                    let lines = text.split_inclusive(|b| *b == b'\n').map(BStr::new);
144                    for line in lines {
145                        self.current_line.hunks.push((DiffLineHunkSide::Both, line));
146                        if line.ends_with(b"\n") {
147                            self.queued_lines.push_back(self.current_line.take());
148                            self.current_line.line_number.left += 1;
149                            self.current_line.line_number.right += 1;
150                        }
151                    }
152                }
153                DiffHunkKind::Different => {
154                    let [left_text, right_text] = hunk.contents[..]
155                        .try_into()
156                        .expect("hunk should have exactly two inputs");
157                    let left_lines = left_text.split_inclusive(|b| *b == b'\n').map(BStr::new);
158                    for left_line in left_lines {
159                        self.current_line
160                            .hunks
161                            .push((DiffLineHunkSide::Left, left_line));
162                        if left_line.ends_with(b"\n") {
163                            self.queued_lines.push_back(self.current_line.take());
164                            self.current_line.line_number.left += 1;
165                        }
166                    }
167                    let mut right_lines =
168                        right_text.split_inclusive(|b| *b == b'\n').map(BStr::new);
169                    // Omit blank right line if matching hunk of the same line
170                    // number has already been queued. Here we only need to
171                    // check the first queued line since the other lines should
172                    // be created in the left_lines loop above.
173                    if right_text.starts_with(b"\n")
174                        && self.current_line.hunks.is_empty()
175                        && self
176                            .queued_lines
177                            .front()
178                            .is_some_and(|queued| queued.has_right_content())
179                    {
180                        let blank_line = right_lines.next().unwrap();
181                        assert_eq!(blank_line, b"\n");
182                        self.current_line.line_number.right += 1;
183                    }
184                    for right_line in right_lines {
185                        self.current_line
186                            .hunks
187                            .push((DiffLineHunkSide::Right, right_line));
188                        if right_line.ends_with(b"\n") {
189                            self.queued_lines.push_back(self.current_line.take());
190                            self.current_line.line_number.right += 1;
191                        }
192                    }
193                }
194            }
195        }
196
197        if let Some(line) = self.queued_lines.pop_front() {
198            return Some(line);
199        }
200
201        if !self.current_line.hunks.is_empty() {
202            return Some(self.current_line.take());
203        }
204
205        None
206    }
207}
208
209/// Diff hunk that may be unresolved conflicts.
210#[derive(Clone, Debug, Eq, PartialEq)]
211pub struct ConflictDiffHunk<'input> {
212    pub kind: DiffHunkKind,
213    pub lefts: Merge<&'input BStr>,
214    pub rights: Merge<&'input BStr>,
215}
216
217/// Iterator adaptor that translates non-conflict hunks to resolved `Merge`.
218///
219/// Trivial conflicts in the diff inputs should have been resolved by caller.
220pub fn conflict_diff_hunks<'input, I>(
221    diff_hunks: I,
222    num_lefts: usize,
223) -> impl Iterator<Item = ConflictDiffHunk<'input>>
224where
225    I: IntoIterator,
226    I::Item: Borrow<DiffHunk<'input>>,
227{
228    fn to_merge<'input>(contents: &[&'input BStr]) -> Merge<&'input BStr> {
229        // Not using trivial_merge() so that the original content can be
230        // reproduced by concatenating hunks.
231        if contents.iter().all_equal() {
232            Merge::resolved(contents[0])
233        } else {
234            Merge::from_vec(contents)
235        }
236    }
237
238    diff_hunks.into_iter().map(move |hunk| {
239        let hunk = hunk.borrow();
240        let (lefts, rights) = hunk.contents.split_at(num_lefts);
241        if let ([left], [right]) = (lefts, rights) {
242            // Non-conflicting diff shouldn't have identical contents
243            ConflictDiffHunk {
244                kind: hunk.kind,
245                lefts: Merge::resolved(left),
246                rights: Merge::resolved(right),
247            }
248        } else {
249            let lefts = to_merge(lefts);
250            let rights = to_merge(rights);
251            let kind = match hunk.kind {
252                DiffHunkKind::Matching => DiffHunkKind::Matching,
253                DiffHunkKind::Different if lefts == rights => DiffHunkKind::Matching,
254                DiffHunkKind::Different => DiffHunkKind::Different,
255            };
256            ConflictDiffHunk {
257                kind,
258                lefts,
259                rights,
260            }
261        }
262    })
263}
264
265/// Granularity of hunks when merging files.
266#[derive(Clone, Copy, Debug, Eq, PartialEq, serde::Deserialize)]
267#[serde(rename_all = "kebab-case")]
268pub enum FileMergeHunkLevel {
269    /// Splits into line hunks.
270    Line,
271    /// Splits into word hunks.
272    Word,
273}
274
275/// Merge result in either fully-resolved or conflicts form, akin to
276/// `Result<BString, Vec<Merge<BString>>>`.
277#[derive(PartialEq, Eq, Clone, Debug)]
278pub enum MergeResult {
279    /// Resolved content if inputs can be merged successfully.
280    Resolved(BString),
281    /// List of partially-resolved hunks if some of them cannot be merged.
282    Conflict(Vec<Merge<BString>>),
283}
284
285/// Splits `inputs` into hunks, resolves trivial merge conflicts for each.
286///
287/// Returns either fully-resolved content or list of partially-resolved hunks.
288pub fn merge_hunks<T: AsRef<[u8]>>(inputs: &Merge<T>, options: &MergeOptions) -> MergeResult {
289    merge_inner(inputs, options)
290}
291
292/// Splits `inputs` into hunks, resolves trivial merge conflicts for each, then
293/// concatenates the outcome back to single `Merge` object.
294///
295/// The returned merge object is either fully resolved or conflict having the
296/// same number of terms as the `inputs`.
297pub fn merge<T: AsRef<[u8]>>(inputs: &Merge<T>, options: &MergeOptions) -> Merge<BString> {
298    merge_inner(inputs, options)
299}
300
301/// Splits `inputs` into hunks, attempts to resolve trivial merge conflicts for
302/// each.
303///
304/// If all input hunks can be merged successfully, returns the merged content.
305pub fn try_merge<T: AsRef<[u8]>>(inputs: &Merge<T>, options: &MergeOptions) -> Option<BString> {
306    merge_inner(inputs, options)
307}
308
309fn merge_inner<'input, T, B>(inputs: &'input Merge<T>, options: &MergeOptions) -> B
310where
311    T: AsRef<[u8]>,
312    B: FromMergeHunks<'input>,
313{
314    // TODO: Using the first remove as base (first in the inputs) is how it's
315    // usually done for 3-way conflicts. Are there better heuristics when there are
316    // more than 3 parts?
317    let num_diffs = inputs.removes().len();
318    let diff = ContentDiff::by_line(inputs.removes().chain(inputs.adds()));
319    let hunks = resolve_diff_hunks(&diff, num_diffs, options.same_change);
320    match options.hunk_level {
321        FileMergeHunkLevel::Line => B::from_hunks(hunks.map(MergeHunk::Borrowed)),
322        FileMergeHunkLevel::Word => {
323            B::from_hunks(hunks.map(|h| merge_hunk_by_word(h, options.same_change)))
324        }
325    }
326}
327
328fn merge_hunk_by_word(inputs: Merge<&BStr>, same_change: SameChange) -> MergeHunk<'_> {
329    if inputs.is_resolved() {
330        return MergeHunk::Borrowed(inputs);
331    }
332    let num_diffs = inputs.removes().len();
333    let diff = ContentDiff::by_word(inputs.removes().chain(inputs.adds()));
334    let hunks = resolve_diff_hunks(&diff, num_diffs, same_change);
335    // We could instead use collect_merged() to return partially-merged hunk.
336    // This would be more consistent with the line-based merge function, but
337    // might produce surprising results. Partially-merged conflicts would be
338    // hard to review because they would have mixed contexts.
339    if let Some(content) = collect_resolved(hunks.map(MergeHunk::Borrowed)) {
340        MergeHunk::Owned(Merge::resolved(content))
341    } else {
342        drop(diff);
343        MergeHunk::Borrowed(inputs)
344    }
345}
346
347/// `Cow`-like type over `Merge<T>`.
348#[derive(Clone, Debug)]
349enum MergeHunk<'input> {
350    Borrowed(Merge<&'input BStr>),
351    Owned(Merge<BString>),
352}
353
354impl MergeHunk<'_> {
355    fn len(&self) -> usize {
356        match self {
357            MergeHunk::Borrowed(merge) => merge.as_slice().len(),
358            MergeHunk::Owned(merge) => merge.as_slice().len(),
359        }
360    }
361
362    fn iter(&self) -> impl Iterator<Item = &BStr> {
363        match self {
364            MergeHunk::Borrowed(merge) => Either::Left(merge.iter().copied()),
365            MergeHunk::Owned(merge) => Either::Right(merge.iter().map(Borrow::borrow)),
366        }
367    }
368
369    fn as_resolved(&self) -> Option<&BStr> {
370        match self {
371            MergeHunk::Borrowed(merge) => merge.as_resolved().copied(),
372            MergeHunk::Owned(merge) => merge.as_resolved().map(Borrow::borrow),
373        }
374    }
375
376    fn into_owned(self) -> Merge<BString> {
377        match self {
378            MergeHunk::Borrowed(merge) => merge.map(|&s| s.to_owned()),
379            MergeHunk::Owned(merge) => merge,
380        }
381    }
382}
383
384/// `FromIterator` for merge result.
385trait FromMergeHunks<'input>: Sized {
386    fn from_hunks<I: IntoIterator<Item = MergeHunk<'input>>>(hunks: I) -> Self;
387}
388
389impl<'input> FromMergeHunks<'input> for MergeResult {
390    fn from_hunks<I: IntoIterator<Item = MergeHunk<'input>>>(hunks: I) -> Self {
391        collect_hunks(hunks)
392    }
393}
394
395impl<'input> FromMergeHunks<'input> for Merge<BString> {
396    fn from_hunks<I: IntoIterator<Item = MergeHunk<'input>>>(hunks: I) -> Self {
397        collect_merged(hunks)
398    }
399}
400
401impl<'input> FromMergeHunks<'input> for Option<BString> {
402    fn from_hunks<I: IntoIterator<Item = MergeHunk<'input>>>(hunks: I) -> Self {
403        collect_resolved(hunks)
404    }
405}
406
407/// Collects merged hunks into either fully-resolved content or list of
408/// partially-resolved hunks.
409fn collect_hunks<'input>(hunks: impl IntoIterator<Item = MergeHunk<'input>>) -> MergeResult {
410    let mut resolved_hunk = BString::new(vec![]);
411    let mut merge_hunks: Vec<Merge<BString>> = vec![];
412    for hunk in hunks {
413        if let Some(content) = hunk.as_resolved() {
414            resolved_hunk.extend_from_slice(content);
415        } else {
416            if !resolved_hunk.is_empty() {
417                merge_hunks.push(Merge::resolved(resolved_hunk));
418                resolved_hunk = BString::new(vec![]);
419            }
420            merge_hunks.push(hunk.into_owned());
421        }
422    }
423
424    if merge_hunks.is_empty() {
425        MergeResult::Resolved(resolved_hunk)
426    } else {
427        if !resolved_hunk.is_empty() {
428            merge_hunks.push(Merge::resolved(resolved_hunk));
429        }
430        MergeResult::Conflict(merge_hunks)
431    }
432}
433
434/// Collects merged hunks back to single `Merge` object, duplicating resolved
435/// hunks to all positive and negative terms.
436fn collect_merged<'input>(hunks: impl IntoIterator<Item = MergeHunk<'input>>) -> Merge<BString> {
437    let mut maybe_resolved = Merge::resolved(BString::default());
438    for hunk in hunks {
439        if let Some(content) = hunk.as_resolved() {
440            for buf in maybe_resolved.iter_mut() {
441                buf.extend_from_slice(content);
442            }
443        } else {
444            maybe_resolved = match maybe_resolved.into_resolved() {
445                Ok(content) => Merge::from_vec(vec![content; hunk.len()]),
446                Err(conflict) => conflict,
447            };
448            assert_eq!(maybe_resolved.as_slice().len(), hunk.len());
449            for (buf, s) in iter::zip(maybe_resolved.iter_mut(), hunk.iter()) {
450                buf.extend_from_slice(s);
451            }
452        }
453    }
454    maybe_resolved
455}
456
457/// Collects resolved merge hunks. Short-circuits on unresolved hunk.
458fn collect_resolved<'input>(hunks: impl IntoIterator<Item = MergeHunk<'input>>) -> Option<BString> {
459    let mut resolved_content = BString::default();
460    for hunk in hunks {
461        resolved_content.extend_from_slice(hunk.as_resolved()?);
462    }
463    Some(resolved_content)
464}
465
466/// Iterator that attempts to resolve trivial merge conflict for each hunk.
467fn resolve_diff_hunks<'a, 'input>(
468    diff: &'a ContentDiff<'input>,
469    num_diffs: usize,
470    same_change: SameChange,
471) -> impl Iterator<Item = Merge<&'input BStr>> + use<'a, 'input> {
472    diff.hunks().map(move |diff_hunk| match diff_hunk.kind {
473        DiffHunkKind::Matching => {
474            debug_assert!(diff_hunk.contents.iter().all_equal());
475            Merge::resolved(diff_hunk.contents[0])
476        }
477        DiffHunkKind::Different => {
478            let merge = Merge::from_removes_adds(
479                diff_hunk.contents[..num_diffs].iter().copied(),
480                diff_hunk.contents[num_diffs..].iter().copied(),
481            );
482            match merge.resolve_trivial(same_change) {
483                Some(&content) => Merge::resolved(content),
484                None => merge,
485            }
486        }
487    })
488}
489
490#[cfg(test)]
491mod tests {
492    use indoc::indoc;
493
494    use super::*;
495
496    fn conflict<const N: usize>(values: [&[u8]; N]) -> Merge<BString> {
497        Merge::from_vec(values.map(hunk).to_vec())
498    }
499
500    fn resolved(value: &[u8]) -> Merge<BString> {
501        Merge::resolved(hunk(value))
502    }
503
504    fn hunk(data: &[u8]) -> BString {
505        data.into()
506    }
507
508    #[test]
509    fn test_diff_line_iterator_line_numbers() {
510        let mut line_iter = DiffLineIterator::with_line_number(
511            [DiffHunk::different(["a\nb", "c\nd\n"])].into_iter(),
512            DiffLineNumber { left: 1, right: 10 },
513        );
514        // Nothing queued
515        assert_eq!(
516            line_iter.next_line_number(),
517            DiffLineNumber { left: 1, right: 10 }
518        );
519        assert_eq!(
520            line_iter.next().unwrap(),
521            DiffLine {
522                line_number: DiffLineNumber { left: 1, right: 10 },
523                hunks: vec![(DiffLineHunkSide::Left, "a\n".as_ref())],
524            }
525        );
526        // Multiple lines queued
527        assert_eq!(
528            line_iter.next_line_number(),
529            DiffLineNumber { left: 2, right: 10 }
530        );
531        assert_eq!(
532            line_iter.next().unwrap(),
533            DiffLine {
534                line_number: DiffLineNumber { left: 2, right: 10 },
535                hunks: vec![
536                    (DiffLineHunkSide::Left, "b".as_ref()),
537                    (DiffLineHunkSide::Right, "c\n".as_ref()),
538                ],
539            }
540        );
541        // Single line queued
542        assert_eq!(
543            line_iter.next_line_number(),
544            DiffLineNumber { left: 2, right: 11 }
545        );
546        assert_eq!(
547            line_iter.next().unwrap(),
548            DiffLine {
549                line_number: DiffLineNumber { left: 2, right: 11 },
550                hunks: vec![(DiffLineHunkSide::Right, "d\n".as_ref())],
551            }
552        );
553        // No more lines: left remains 2 as it lacks newline
554        assert_eq!(
555            line_iter.next_line_number(),
556            DiffLineNumber { left: 2, right: 12 }
557        );
558        assert!(line_iter.next().is_none());
559        assert_eq!(
560            line_iter.next_line_number(),
561            DiffLineNumber { left: 2, right: 12 }
562        );
563    }
564
565    #[test]
566    fn test_diff_line_iterator_blank_right_line_single_left() {
567        let mut line_iter = DiffLineIterator::new(
568            [
569                DiffHunk::matching(["a"].repeat(2)),
570                DiffHunk::different(["x\n", "\ny\n"]),
571            ]
572            .into_iter(),
573        );
574        assert_eq!(
575            line_iter.next().unwrap(),
576            DiffLine {
577                line_number: DiffLineNumber { left: 1, right: 1 },
578                hunks: vec![
579                    (DiffLineHunkSide::Both, "a".as_ref()),
580                    (DiffLineHunkSide::Left, "x\n".as_ref()),
581                ],
582            }
583        );
584        // "\n" (line_number.right = 1) can be omitted because the previous diff
585        // line has a right content.
586        assert_eq!(
587            line_iter.next().unwrap(),
588            DiffLine {
589                line_number: DiffLineNumber { left: 2, right: 2 },
590                hunks: vec![(DiffLineHunkSide::Right, "y\n".as_ref())],
591            }
592        );
593    }
594
595    #[test]
596    fn test_diff_line_iterator_blank_right_line_multiple_lefts() {
597        let mut line_iter = DiffLineIterator::new(
598            [
599                DiffHunk::matching(["a"].repeat(2)),
600                DiffHunk::different(["x\n\n", "\ny\n"]),
601            ]
602            .into_iter(),
603        );
604        assert_eq!(
605            line_iter.next().unwrap(),
606            DiffLine {
607                line_number: DiffLineNumber { left: 1, right: 1 },
608                hunks: vec![
609                    (DiffLineHunkSide::Both, "a".as_ref()),
610                    (DiffLineHunkSide::Left, "x\n".as_ref()),
611                ],
612            }
613        );
614        assert_eq!(
615            line_iter.next().unwrap(),
616            DiffLine {
617                line_number: DiffLineNumber { left: 2, right: 1 },
618                hunks: vec![(DiffLineHunkSide::Left, "\n".as_ref())],
619            }
620        );
621        // "\n" (line_number.right = 1) can still be omitted because one of the
622        // preceding diff line has a right content.
623        assert_eq!(
624            line_iter.next().unwrap(),
625            DiffLine {
626                line_number: DiffLineNumber { left: 3, right: 2 },
627                hunks: vec![(DiffLineHunkSide::Right, "y\n".as_ref())],
628            }
629        );
630    }
631
632    #[test]
633    fn test_diff_line_iterator_blank_right_line_after_non_empty_left() {
634        let mut line_iter = DiffLineIterator::new(
635            [
636                DiffHunk::matching(["a"].repeat(2)),
637                DiffHunk::different(["x\nz", "\ny\n"]),
638            ]
639            .into_iter(),
640        );
641        assert_eq!(
642            line_iter.next().unwrap(),
643            DiffLine {
644                line_number: DiffLineNumber { left: 1, right: 1 },
645                hunks: vec![
646                    (DiffLineHunkSide::Both, "a".as_ref()),
647                    (DiffLineHunkSide::Left, "x\n".as_ref()),
648                ],
649            }
650        );
651        assert_eq!(
652            line_iter.next().unwrap(),
653            DiffLine {
654                line_number: DiffLineNumber { left: 2, right: 1 },
655                hunks: vec![
656                    (DiffLineHunkSide::Left, "z".as_ref()),
657                    (DiffLineHunkSide::Right, "\n".as_ref()),
658                ],
659            }
660        );
661        assert_eq!(
662            line_iter.next().unwrap(),
663            DiffLine {
664                line_number: DiffLineNumber { left: 2, right: 2 },
665                hunks: vec![(DiffLineHunkSide::Right, "y\n".as_ref())],
666            }
667        );
668    }
669
670    #[test]
671    fn test_diff_line_iterator_blank_right_line_without_preceding_lines() {
672        let mut line_iter = DiffLineIterator::new([DiffHunk::different(["", "\ny\n"])].into_iter());
673        assert_eq!(
674            line_iter.next().unwrap(),
675            DiffLine {
676                line_number: DiffLineNumber { left: 1, right: 1 },
677                hunks: vec![(DiffLineHunkSide::Right, "\n".as_ref())],
678            }
679        );
680        assert_eq!(
681            line_iter.next().unwrap(),
682            DiffLine {
683                line_number: DiffLineNumber { left: 1, right: 2 },
684                hunks: vec![(DiffLineHunkSide::Right, "y\n".as_ref())],
685            }
686        );
687    }
688
689    #[test]
690    fn test_conflict_diff_hunks_no_conflicts() {
691        let diff_hunks = [
692            DiffHunk::matching(["a\n"].repeat(2)),
693            DiffHunk::different(["b\n", "c\n"]),
694        ];
695        let num_lefts = 1;
696        insta::assert_debug_snapshot!(
697            conflict_diff_hunks(&diff_hunks, num_lefts).collect_vec(), @r#"
698        [
699            ConflictDiffHunk {
700                kind: Matching,
701                lefts: Resolved(
702                    "a\n",
703                ),
704                rights: Resolved(
705                    "a\n",
706                ),
707            },
708            ConflictDiffHunk {
709                kind: Different,
710                lefts: Resolved(
711                    "b\n",
712                ),
713                rights: Resolved(
714                    "c\n",
715                ),
716            },
717        ]
718        "#);
719    }
720
721    #[test]
722    fn test_conflict_diff_hunks_simple_conflicts() {
723        let diff_hunks = [
724            // conflict hunk
725            DiffHunk::different(["a\n", "X\n", "b\n", "c\n"]),
726            DiffHunk::matching(["d\n"].repeat(4)),
727            // non-conflict hunk
728            DiffHunk::different(["e\n", "e\n", "e\n", "f\n"]),
729        ];
730        let num_lefts = 3;
731        insta::assert_debug_snapshot!(
732            conflict_diff_hunks(&diff_hunks, num_lefts).collect_vec(), @r#"
733        [
734            ConflictDiffHunk {
735                kind: Different,
736                lefts: Conflicted(
737                    [
738                        "a\n",
739                        "X\n",
740                        "b\n",
741                    ],
742                ),
743                rights: Resolved(
744                    "c\n",
745                ),
746            },
747            ConflictDiffHunk {
748                kind: Matching,
749                lefts: Resolved(
750                    "d\n",
751                ),
752                rights: Resolved(
753                    "d\n",
754                ),
755            },
756            ConflictDiffHunk {
757                kind: Different,
758                lefts: Resolved(
759                    "e\n",
760                ),
761                rights: Resolved(
762                    "f\n",
763                ),
764            },
765        ]
766        "#);
767    }
768
769    #[test]
770    fn test_conflict_diff_hunks_matching_conflicts() {
771        let diff_hunks = [
772            // matching conflict hunk
773            DiffHunk::different(["a\n", "X\n", "b\n", "a\n", "X\n", "b\n"]),
774            DiffHunk::matching(["c\n"].repeat(6)),
775        ];
776        let num_lefts = 3;
777        insta::assert_debug_snapshot!(
778            conflict_diff_hunks(&diff_hunks, num_lefts).collect_vec(), @r#"
779        [
780            ConflictDiffHunk {
781                kind: Matching,
782                lefts: Conflicted(
783                    [
784                        "a\n",
785                        "X\n",
786                        "b\n",
787                    ],
788                ),
789                rights: Conflicted(
790                    [
791                        "a\n",
792                        "X\n",
793                        "b\n",
794                    ],
795                ),
796            },
797            ConflictDiffHunk {
798                kind: Matching,
799                lefts: Resolved(
800                    "c\n",
801                ),
802                rights: Resolved(
803                    "c\n",
804                ),
805            },
806        ]
807        "#);
808    }
809
810    #[test]
811    fn test_conflict_diff_hunks_no_trivial_resolution() {
812        let diff_hunks = [DiffHunk::different(["a", "b", "a", "a"])];
813        let num_lefts = 1;
814        insta::assert_debug_snapshot!(
815            conflict_diff_hunks(&diff_hunks, num_lefts).collect_vec(), @r#"
816        [
817            ConflictDiffHunk {
818                kind: Different,
819                lefts: Resolved(
820                    "a",
821                ),
822                rights: Conflicted(
823                    [
824                        "b",
825                        "a",
826                        "a",
827                    ],
828                ),
829            },
830        ]
831        "#);
832        let num_lefts = 3;
833        insta::assert_debug_snapshot!(
834            conflict_diff_hunks(&diff_hunks, num_lefts).collect_vec(), @r#"
835        [
836            ConflictDiffHunk {
837                kind: Different,
838                lefts: Conflicted(
839                    [
840                        "a",
841                        "b",
842                        "a",
843                    ],
844                ),
845                rights: Resolved(
846                    "a",
847                ),
848            },
849        ]
850        "#);
851    }
852
853    #[test]
854    fn test_merge_single_hunk() {
855        let options = MergeOptions {
856            hunk_level: FileMergeHunkLevel::Line,
857            same_change: SameChange::Accept,
858        };
859        let merge_hunks = |inputs: &_| merge_hunks(inputs, &options);
860        // Unchanged and empty on all sides
861        assert_eq!(
862            merge_hunks(&conflict([b"", b"", b""])),
863            MergeResult::Resolved(hunk(b""))
864        );
865        // Unchanged on all sides
866        assert_eq!(
867            merge_hunks(&conflict([b"a", b"a", b"a"])),
868            MergeResult::Resolved(hunk(b"a"))
869        );
870        // One side removed, one side unchanged
871        assert_eq!(
872            merge_hunks(&conflict([b"", b"a\n", b"a\n"])),
873            MergeResult::Resolved(hunk(b""))
874        );
875        // One side unchanged, one side removed
876        assert_eq!(
877            merge_hunks(&conflict([b"a\n", b"a\n", b""])),
878            MergeResult::Resolved(hunk(b""))
879        );
880        // Both sides removed same line
881        assert_eq!(
882            merge_hunks(&conflict([b"", b"a\n", b""])),
883            MergeResult::Resolved(hunk(b""))
884        );
885        // One side modified, one side unchanged
886        assert_eq!(
887            merge_hunks(&conflict([b"a b", b"a", b"a"])),
888            MergeResult::Resolved(hunk(b"a b"))
889        );
890        // One side unchanged, one side modified
891        assert_eq!(
892            merge_hunks(&conflict([b"a", b"a", b"a b"])),
893            MergeResult::Resolved(hunk(b"a b"))
894        );
895        // All sides added same content
896        assert_eq!(
897            merge_hunks(&conflict([b"a\n", b"", b"a\n", b"", b"a\n"])),
898            MergeResult::Resolved(hunk(b"a\n"))
899        );
900        // One side modified, two sides added
901        assert_eq!(
902            merge_hunks(&conflict([b"b", b"a", b"b", b"", b"b"])),
903            MergeResult::Conflict(vec![conflict([b"b", b"a", b"b", b"", b"b"])])
904        );
905        // All sides removed same content
906        assert_eq!(
907            merge_hunks(&conflict([b"", b"a\n", b"", b"a\n", b"", b"a\n", b""])),
908            MergeResult::Resolved(hunk(b""))
909        );
910        // One side modified, two sides removed
911        assert_eq!(
912            merge_hunks(&conflict([b"b\n", b"a\n", b"", b"a\n", b""])),
913            MergeResult::Conflict(vec![conflict([b"b\n", b"a\n", b"", b"a\n", b""])])
914        );
915        // Three sides made the same change
916        assert_eq!(
917            merge_hunks(&conflict([b"b", b"a", b"b", b"a", b"b"])),
918            MergeResult::Resolved(hunk(b"b"))
919        );
920        // One side removed, one side modified
921        assert_eq!(
922            merge_hunks(&conflict([b"", b"a\n", b"b\n"])),
923            MergeResult::Conflict(vec![conflict([b"", b"a\n", b"b\n"])])
924        );
925        // One side modified, one side removed
926        assert_eq!(
927            merge_hunks(&conflict([b"b\n", b"a\n", b""])),
928            MergeResult::Conflict(vec![conflict([b"b\n", b"a\n", b""])])
929        );
930        // Two sides modified in different ways
931        assert_eq!(
932            merge_hunks(&conflict([b"b", b"a", b"c"])),
933            MergeResult::Conflict(vec![conflict([b"b", b"a", b"c"])])
934        );
935        // Two of three sides don't change, third side changes
936        assert_eq!(
937            merge_hunks(&conflict([b"a", b"a", b"", b"a", b"a"])),
938            MergeResult::Resolved(hunk(b""))
939        );
940        // One side unchanged, two other sides make the same change
941        assert_eq!(
942            merge_hunks(&conflict([b"b", b"a", b"a", b"a", b"b"])),
943            MergeResult::Resolved(hunk(b"b"))
944        );
945        // One side unchanged, two other sides make the different change
946        assert_eq!(
947            merge_hunks(&conflict([b"b", b"a", b"a", b"a", b"c"])),
948            MergeResult::Conflict(vec![conflict([b"b", b"a", b"a", b"a", b"c"])])
949        );
950        // Merge of an unresolved conflict and another branch, where the other branch
951        // undid the change from one of the inputs to the unresolved conflict in the
952        // first.
953        assert_eq!(
954            merge_hunks(&conflict([b"b", b"a", b"a", b"b", b"c"])),
955            MergeResult::Resolved(hunk(b"c"))
956        );
957        // Merge of an unresolved conflict and another branch.
958        assert_eq!(
959            merge_hunks(&conflict([b"c", b"a", b"d", b"b", b"e"])),
960            MergeResult::Conflict(vec![conflict([b"c", b"a", b"d", b"b", b"e"])])
961        );
962        // Two sides made the same change, third side made a different change
963        assert_eq!(
964            merge_hunks(&conflict([b"c", b"a", b"c", b"b", b"c"])),
965            MergeResult::Conflict(vec![conflict([b"c", b"a", b"c", b"b", b"c"])])
966        );
967    }
968
969    #[test]
970    fn test_merge_multi_hunk() {
971        let options = MergeOptions {
972            hunk_level: FileMergeHunkLevel::Line,
973            same_change: SameChange::Accept,
974        };
975        let merge_hunks = |inputs: &_| merge_hunks(inputs, &options);
976        let merge = |inputs: &_| merge(inputs, &options);
977        let try_merge = |inputs: &_| try_merge(inputs, &options);
978        // Two sides left one line unchanged, and added conflicting additional lines
979        let inputs = conflict([b"a\nb\n", b"a\n", b"a\nc\n"]);
980        assert_eq!(
981            merge_hunks(&inputs),
982            MergeResult::Conflict(vec![resolved(b"a\n"), conflict([b"b\n", b"", b"c\n"])])
983        );
984        assert_eq!(merge(&inputs), conflict([b"a\nb\n", b"a\n", b"a\nc\n"]));
985        assert_eq!(try_merge(&inputs), None);
986
987        // Two sides changed different lines: no conflict
988        let inputs = conflict([b"a2\nb\nc\n", b"a\nb\nc\n", b"a\nb\nc2\n"]);
989        assert_eq!(
990            merge_hunks(&inputs),
991            MergeResult::Resolved(hunk(b"a2\nb\nc2\n"))
992        );
993        assert_eq!(merge(&inputs), resolved(b"a2\nb\nc2\n"));
994        assert_eq!(try_merge(&inputs), Some(hunk(b"a2\nb\nc2\n")));
995
996        // Conflict with non-conflicting lines around
997        let inputs = conflict([b"a\nb1\nc\n", b"a\nb\nc\n", b"a\nb2\nc\n"]);
998        assert_eq!(
999            merge_hunks(&inputs),
1000            MergeResult::Conflict(vec![
1001                resolved(b"a\n"),
1002                conflict([b"b1\n", b"b\n", b"b2\n"]),
1003                resolved(b"c\n"),
1004            ])
1005        );
1006        assert_eq!(
1007            merge(&inputs),
1008            conflict([b"a\nb1\nc\n", b"a\nb\nc\n", b"a\nb2\nc\n"])
1009        );
1010        assert_eq!(try_merge(&inputs), None);
1011
1012        // Two conflict hunks, one can be resolved
1013        let inputs = conflict([b"a\nb\nc\n", b"a1\nb\nc\n", b"a2\nb\nc2\n"]);
1014        assert_eq!(
1015            merge_hunks(&inputs),
1016            MergeResult::Conflict(vec![
1017                conflict([b"a\n", b"a1\n", b"a2\n"]),
1018                resolved(b"b\nc2\n"),
1019            ])
1020        );
1021        assert_eq!(
1022            merge(&inputs),
1023            conflict([b"a\nb\nc2\n", b"a1\nb\nc2\n", b"a2\nb\nc2\n"])
1024        );
1025        assert_eq!(try_merge(&inputs), None);
1026
1027        // One side changes a line and adds a block after. The other side just adds the
1028        // same block. You might expect the last block would be deduplicated. However,
1029        // the changes in the first side can be parsed as follows:
1030        // ```
1031        //  a {
1032        // -    p
1033        // +    q
1034        // +}
1035        // +
1036        // +b {
1037        // +    x
1038        //  }
1039        // ```
1040        // Therefore, the first side modifies the block `a { .. }`, and the second side
1041        // adds `b { .. }`. Git and Mercurial both duplicate the block in the result.
1042        let base = indoc! {b"
1043            a {
1044                p
1045            }
1046        "};
1047        let left = indoc! {b"
1048            a {
1049                q
1050            }
1051
1052            b {
1053                x
1054            }
1055        "};
1056        let right = indoc! {b"
1057            a {
1058                p
1059            }
1060
1061            b {
1062                x
1063            }
1064        "};
1065        let merged = indoc! {b"
1066            a {
1067                q
1068            }
1069
1070            b {
1071                x
1072            }
1073
1074            b {
1075                x
1076            }
1077        "};
1078        assert_eq!(merge(&conflict([left, base, right])), resolved(merged));
1079    }
1080
1081    #[test]
1082    fn test_merge_hunk_by_word() {
1083        let options = MergeOptions {
1084            hunk_level: FileMergeHunkLevel::Word,
1085            same_change: SameChange::Accept,
1086        };
1087        let merge = |inputs: &_| merge(inputs, &options);
1088        // No context line in between, but "\n" is a context word
1089        assert_eq!(
1090            merge(&conflict([b"c\nb\n", b"a\nb\n", b"a\nd\n"])),
1091            resolved(b"c\nd\n")
1092        );
1093        // Both sides added to different positions
1094        assert_eq!(merge(&conflict([b"a b", b"a", b"c a"])), resolved(b"c a b"));
1095        // Both sides added to the same position: can't resolve word-level
1096        // conflicts and the whole line should be left as a conflict
1097        assert_eq!(
1098            merge(&conflict([b"a b", b"a", b"a c"])),
1099            conflict([b"a b", b"a", b"a c"])
1100        );
1101        // One side added, both sides added to the same position: the former
1102        // word-level conflict could be resolved, but we preserve the original
1103        // content in that case
1104        assert_eq!(
1105            merge(&conflict([b"a b", b"a", b"x a c"])),
1106            conflict([b"a b", b"a", b"x a c"])
1107        );
1108    }
1109}
jj_lib/files.rs

jj_lib/
files.rs
