gix_merge/blob/builtin_driver/text/
function.rs

1use crate::blob::builtin_driver::text::utils::{
2    assure_ends_with_nl, contains_lines, detect_line_ending, detect_line_ending_or_nl, fill_ancestor,
3    hunks_differ_in_diff3, take_intersecting, tokens, write_ancestor, write_conflict_marker, write_hunks,
4    zealously_contract_hunks, CollectHunks, Hunk, Side,
5};
6use crate::blob::builtin_driver::text::{Conflict, ConflictStyle, Labels, Options};
7use crate::blob::Resolution;
8use std::ops::Range;
9
10/// Merge `current` and `other` with `ancestor` as base according to `opts`.
11///
12/// Use `labels` to annotate conflict sections.
13///
14/// `input` is for reusing memory for lists of tokens, but note that it grows indefinitely
15/// while tokens for `current`, `ancestor` and `other` are added.
16/// Place the merged result in `out` (cleared before use) and return the resolution.
17///
18/// # Important
19///
20/// *The caller* is responsible for clearing `input`, otherwise tokens will accumulate.
21/// This idea is to save time if the input is known to be very similar.
22#[allow(clippy::too_many_arguments)]
23pub fn merge<'a>(
24    out: &mut Vec<u8>,
25    input: &mut imara_diff::intern::InternedInput<&'a [u8]>,
26    Labels {
27        ancestor: ancestor_label,
28        current: current_label,
29        other: other_label,
30    }: Labels<'_>,
31    current: &'a [u8],
32    ancestor: &'a [u8],
33    other: &'a [u8],
34    Options {
35        diff_algorithm,
36        conflict,
37    }: Options,
38) -> Resolution {
39    out.clear();
40    input.update_before(tokens(ancestor));
41    input.update_after(tokens(current));
42
43    let hunks = imara_diff::diff(
44        diff_algorithm,
45        input,
46        CollectHunks {
47            side: Side::Current,
48            hunks: Default::default(),
49        },
50    );
51
52    let current_tokens = std::mem::take(&mut input.after);
53    input.update_after(tokens(other));
54
55    let mut hunks = imara_diff::diff(
56        diff_algorithm,
57        input,
58        CollectHunks {
59            side: Side::Other,
60            hunks,
61        },
62    );
63
64    if hunks.is_empty() {
65        write_ancestor(input, 0, input.before.len(), out);
66        return Resolution::Complete;
67    }
68
69    hunks.sort_by(|a, b| a.before.start.cmp(&b.before.start));
70    let mut hunks = hunks.into_iter().peekable();
71    let mut intersecting = Vec::new();
72    let mut ancestor_integrated_until = 0;
73    let mut resolution = Resolution::Complete;
74    let mut current_hunks = Vec::with_capacity(2);
75    while take_intersecting(&mut hunks, &mut current_hunks, &mut intersecting).is_some() {
76        if intersecting.is_empty() {
77            let hunk = current_hunks.pop().expect("always pushed during intersection check");
78            write_ancestor(input, ancestor_integrated_until, hunk.before.start as usize, out);
79            ancestor_integrated_until = hunk.before.end;
80            write_hunks(std::slice::from_ref(&hunk), input, &current_tokens, out);
81            continue;
82        }
83
84        let filled_hunks_side = current_hunks.first().expect("at least one hunk").side;
85        {
86            let filled_hunks_range = before_range_from_hunks(&current_hunks);
87            let intersecting_range = before_range_from_hunks(&intersecting);
88            let extended_range = filled_hunks_range.start..intersecting_range.end.max(filled_hunks_range.end);
89            fill_ancestor(&extended_range, &mut current_hunks);
90            fill_ancestor(&extended_range, &mut intersecting);
91        }
92        match conflict {
93            Conflict::Keep { style, marker_size } => {
94                let marker_size = marker_size.get();
95                let (hunks_front_and_back, num_hunks_front) = match style {
96                    ConflictStyle::Merge | ConflictStyle::ZealousDiff3 => {
97                        zealously_contract_hunks(&mut current_hunks, &mut intersecting, input, &current_tokens)
98                    }
99                    ConflictStyle::Diff3 => (Vec::new(), 0),
100                };
101                let (our_hunks, their_hunks) = match filled_hunks_side {
102                    Side::Current => (&current_hunks, &intersecting),
103                    Side::Other => (&intersecting, &current_hunks),
104                    Side::Ancestor => {
105                        unreachable!("initial hunks are never ancestors")
106                    }
107                };
108                let (front_hunks, back_hunks) = hunks_front_and_back.split_at(num_hunks_front);
109                let first_hunk = first_hunk(front_hunks, our_hunks, their_hunks, back_hunks);
110                let last_hunk = last_hunk(front_hunks, our_hunks, their_hunks, back_hunks);
111                write_ancestor(input, ancestor_integrated_until, first_hunk.before.start as usize, out);
112                write_hunks(front_hunks, input, &current_tokens, out);
113                if their_hunks.is_empty() {
114                    write_hunks(our_hunks, input, &current_tokens, out);
115                } else if our_hunks.is_empty() {
116                    write_hunks(their_hunks, input, &current_tokens, out);
117                } else {
118                    // DEVIATION: this makes tests (mostly) pass, but probably is very different from what Git does.
119                    let hunk_storage;
120                    let nl = detect_line_ending(
121                        if front_hunks.is_empty() {
122                            hunk_storage = Hunk {
123                                before: ancestor_integrated_until..first_hunk.before.start,
124                                after: Default::default(),
125                                side: Side::Ancestor,
126                            };
127                            std::slice::from_ref(&hunk_storage)
128                        } else {
129                            front_hunks
130                        },
131                        input,
132                        &current_tokens,
133                    )
134                    .or_else(|| detect_line_ending(our_hunks, input, &current_tokens))
135                    .unwrap_or(b"\n".into());
136                    match style {
137                        ConflictStyle::Merge => {
138                            if contains_lines(our_hunks) || contains_lines(their_hunks) {
139                                resolution = Resolution::Conflict;
140                                write_conflict_marker(out, b'<', current_label, marker_size, nl);
141                                write_hunks(our_hunks, input, &current_tokens, out);
142                                write_conflict_marker(out, b'=', None, marker_size, nl);
143                                write_hunks(their_hunks, input, &current_tokens, out);
144                                write_conflict_marker(out, b'>', other_label, marker_size, nl);
145                            }
146                        }
147                        ConflictStyle::Diff3 | ConflictStyle::ZealousDiff3 => {
148                            if contains_lines(our_hunks) || contains_lines(their_hunks) {
149                                if hunks_differ_in_diff3(style, our_hunks, their_hunks, input, &current_tokens) {
150                                    resolution = Resolution::Conflict;
151                                    write_conflict_marker(out, b'<', current_label, marker_size, nl);
152                                    write_hunks(our_hunks, input, &current_tokens, out);
153                                    let ancestor_hunk = Hunk {
154                                        before: first_hunk.before.start..last_hunk.before.end,
155                                        after: Default::default(),
156                                        side: Side::Ancestor,
157                                    };
158                                    let ancestor_hunk = std::slice::from_ref(&ancestor_hunk);
159                                    let ancestor_nl = detect_line_ending_or_nl(ancestor_hunk, input, &current_tokens);
160                                    write_conflict_marker(out, b'|', ancestor_label, marker_size, ancestor_nl);
161                                    write_hunks(ancestor_hunk, input, &current_tokens, out);
162                                    write_conflict_marker(out, b'=', None, marker_size, nl);
163                                    write_hunks(their_hunks, input, &current_tokens, out);
164                                    write_conflict_marker(out, b'>', other_label, marker_size, nl);
165                                } else {
166                                    write_hunks(our_hunks, input, &current_tokens, out);
167                                }
168                            }
169                        }
170                    }
171                }
172                write_hunks(back_hunks, input, &current_tokens, out);
173                ancestor_integrated_until = last_hunk.before.end;
174            }
175            Conflict::ResolveWithOurs | Conflict::ResolveWithTheirs => {
176                let (our_hunks, their_hunks) = match filled_hunks_side {
177                    Side::Current => (&current_hunks, &intersecting),
178                    Side::Other => (&intersecting, &current_hunks),
179                    Side::Ancestor => {
180                        unreachable!("initial hunks are never ancestors")
181                    }
182                };
183                if hunks_differ_in_diff3(ConflictStyle::Diff3, our_hunks, their_hunks, input, &current_tokens) {
184                    resolution = Resolution::CompleteWithAutoResolvedConflict;
185                }
186                let hunks_to_write = if conflict == Conflict::ResolveWithOurs {
187                    our_hunks
188                } else {
189                    their_hunks
190                };
191                if let Some(first_hunk) = hunks_to_write.first() {
192                    write_ancestor(input, ancestor_integrated_until, first_hunk.before.start as usize, out);
193                }
194                write_hunks(hunks_to_write, input, &current_tokens, out);
195                if let Some(last_hunk) = hunks_to_write.last() {
196                    ancestor_integrated_until = last_hunk.before.end;
197                }
198            }
199            Conflict::ResolveWithUnion => {
200                let (hunks_front_and_back, num_hunks_front) =
201                    zealously_contract_hunks(&mut current_hunks, &mut intersecting, input, &current_tokens);
202
203                let (our_hunks, their_hunks) = match filled_hunks_side {
204                    Side::Current => (&current_hunks, &intersecting),
205                    Side::Other => (&intersecting, &current_hunks),
206                    Side::Ancestor => {
207                        unreachable!("initial hunks are never ancestors")
208                    }
209                };
210                if hunks_differ_in_diff3(ConflictStyle::Diff3, our_hunks, their_hunks, input, &current_tokens) {
211                    resolution = Resolution::CompleteWithAutoResolvedConflict;
212                }
213                let (front_hunks, back_hunks) = hunks_front_and_back.split_at(num_hunks_front);
214                let first_hunk = first_hunk(front_hunks, our_hunks, their_hunks, back_hunks);
215                write_ancestor(input, ancestor_integrated_until, first_hunk.before.start as usize, out);
216                write_hunks(front_hunks, input, &current_tokens, out);
217                assure_ends_with_nl(out, detect_line_ending_or_nl(front_hunks, input, &current_tokens));
218                write_hunks(our_hunks, input, &current_tokens, out);
219                assure_ends_with_nl(out, detect_line_ending_or_nl(our_hunks, input, &current_tokens));
220                write_hunks(their_hunks, input, &current_tokens, out);
221                if !back_hunks.is_empty() {
222                    assure_ends_with_nl(out, detect_line_ending_or_nl(their_hunks, input, &current_tokens));
223                }
224                write_hunks(back_hunks, input, &current_tokens, out);
225                let last_hunk = last_hunk(front_hunks, our_hunks, their_hunks, back_hunks);
226                ancestor_integrated_until = last_hunk.before.end;
227            }
228        }
229    }
230    write_ancestor(input, ancestor_integrated_until, input.before.len(), out);
231
232    resolution
233}
234
235fn first_hunk<'a>(front: &'a [Hunk], ours: &'a [Hunk], theirs: &'a [Hunk], back: &'a [Hunk]) -> &'a Hunk {
236    front
237        .first()
238        .or(ours.first())
239        .or(theirs.first())
240        .or(back.first())
241        .expect("at least one hunk - we aborted if there are none anywhere")
242}
243
244/// Note that last-hunk could be [`first_hunk()`], so the hunk must only be used accordingly.
245fn last_hunk<'a>(front: &'a [Hunk], ours: &'a [Hunk], theirs: &'a [Hunk], back: &'a [Hunk]) -> &'a Hunk {
246    back.last()
247        .or(theirs.last())
248        .or(ours.last())
249        .or(front.last())
250        .expect("at least one hunk - we aborted if there are none anywhere")
251}
252
253fn before_range_from_hunks(hunks: &[Hunk]) -> Range<u32> {
254    hunks
255        .first()
256        .zip(hunks.last())
257        .map(|(f, l)| f.before.start..l.before.end)
258        .expect("at least one entry")
259}
gix_merge/blob/builtin_driver/text/function.rs

gix_merge/blob/builtin_driver/text/
function.rs
