Debian Codegraph @

src/blob/builtin_driver/text/function.rs

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