| 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(¤t_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 => (¤t_hunks, &intersecting), |
| 106 |
Side::Other => (&intersecting, ¤t_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 => (¤t_hunks, &intersecting), |
| 176 |
Side::Other => (&intersecting, ¤t_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 => (¤t_hunks, &intersecting), |
| 203 |
Side::Other => (&intersecting, ¤t_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 |
} |