1use super::{Hunk, HunkLine};
4use crate::error::ApplyError;
5
6#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
8pub struct ApplyOptions {
9 pub reverse: bool,
11}
12
13#[derive(Debug, Clone)]
19struct WorkingBlob<'a> {
20 rows: Vec<&'a [u8]>,
21 consumed: Vec<bool>,
23}
24
25impl<'a> WorkingBlob<'a> {
26 fn decode(data: &'a [u8]) -> Self {
27 let mut rows = Vec::with_capacity(memchr::memchr_iter(b'\n', data).count() + 1);
28 let mut start = 0usize;
29 for i in memchr::memchr_iter(b'\n', data) {
30 rows.push(&data[start..=i]);
31 start = i + 1;
32 }
33 if start < data.len() {
34 rows.push(&data[start..]);
35 }
36 let consumed = vec![false; rows.len()];
37 Self { rows, consumed }
38 }
39
40 fn encode(&self) -> Vec<u8> {
41 let mut out = Vec::with_capacity(self.rows.iter().map(|row| row.len()).sum());
42 for row in &self.rows {
43 out.extend_from_slice(row);
44 }
45 out
46 }
47
48 fn len(&self) -> usize {
49 self.rows.len()
50 }
51}
52
53#[derive(Debug, Clone)]
55struct LineEdit {
56 match_rows: Vec<Vec<u8>>,
57 replace_rows: Vec<Vec<u8>>,
58 stable_prefix: usize,
59 stable_suffix: usize,
60}
61
62#[derive(Debug, Clone, Copy)]
64struct ScanHint {
65 start_row: usize,
67 only_at_front: bool,
69 only_at_back: bool,
71}
72
73pub fn apply_hunks_to_blob(
80 original: &[u8],
81 hunks: &[Hunk],
82 opts: &ApplyOptions,
83) -> Result<Vec<u8>, ApplyError> {
84 let edits: Vec<LineEdit> = hunks
85 .iter()
86 .map(|hunk| line_edit_from_hunk(hunk, opts.reverse))
87 .collect();
88 let mut working = WorkingBlob::decode(original);
89 for (hunk_index, (hunk, edit)) in hunks.iter().zip(&edits).enumerate() {
90 let insert_only = if opts.reverse {
91 hunk.new_count == 0
92 } else {
93 hunk.old_count == 0
94 };
95 let hint = scan_hint_for_hunk(hunk, edit, opts.reverse);
96 let Some(at) = locate_and_apply(&mut working, edit, hint, hunk, hunk_index, insert_only)?
97 else {
98 return Err(ApplyError::ContextMismatch {
99 hunk_index,
100 expected_line: if opts.reverse {
101 hunk.old_start
102 } else {
103 hunk.new_start
104 },
105 });
106 };
107 let _ = at;
108 }
109 Ok(working.encode())
110}
111
112fn scan_hint_for_hunk(hunk: &Hunk, edit: &LineEdit, reverse: bool) -> ScanHint {
113 let (header_line, only_at_front) = if reverse {
114 (hunk.old_start, hunk.new_start <= 1)
115 } else {
116 (hunk.new_start, hunk.old_start <= 1)
117 };
118 let start_row = if header_line == 0 {
119 0
120 } else {
121 header_line.saturating_sub(1)
122 };
123 ScanHint {
124 start_row,
125 only_at_front,
126 only_at_back: edit.stable_suffix == 0 && edit.stable_prefix > 0,
131 }
132}
133
134fn line_edit_from_hunk(hunk: &Hunk, reverse: bool) -> LineEdit {
135 let mut match_rows = Vec::new();
136 let mut replace_rows = Vec::new();
137 let mut stable_prefix = 0usize;
138 let mut stable_suffix = 0usize;
139 let mut in_change = false;
140
141 let mut i = 0usize;
142 while i < hunk.lines.len() {
143 let (tag, text) = match &hunk.lines[i] {
144 HunkLine::Context(s) => ("ctx", s.as_str()),
145 HunkLine::Add(s) => ("add", s.as_str()),
146 HunkLine::Remove(s) => ("del", s.as_str()),
147 HunkLine::NoNewline => {
148 i += 1;
149 continue;
150 }
151 };
152 let tag = if reverse {
153 match tag {
154 "add" => "del",
155 "del" => "add",
156 other => other,
157 }
158 } else {
159 tag
160 };
161
162 let with_nl = !matches!(hunk.lines.get(i + 1), Some(HunkLine::NoNewline));
163 let row = hunk_text_as_row(text, with_nl);
164
165 match tag {
166 "ctx" => {
167 if !in_change {
168 stable_prefix += 1;
169 }
170 stable_suffix += 1;
171 match_rows.push(row.clone());
172 replace_rows.push(row);
173 }
174 "del" => {
175 in_change = true;
176 stable_suffix = 0;
177 match_rows.push(row);
178 }
179 "add" => {
180 in_change = true;
181 stable_suffix = 0;
182 replace_rows.push(row);
183 }
184 _ => {}
185 }
186 i += 1;
187 }
188
189 if !in_change {
190 stable_suffix = stable_prefix;
191 }
192
193 LineEdit {
194 match_rows,
195 replace_rows,
196 stable_prefix,
197 stable_suffix,
198 }
199}
200
201fn hunk_text_as_row(text: &str, with_newline: bool) -> Vec<u8> {
202 let mut row = text.as_bytes().to_vec();
203 if with_newline {
204 row.push(b'\n');
205 }
206 row
207}
208
209#[derive(Debug, Clone)]
211struct EditWindow {
212 match_rows: std::ops::Range<usize>,
213 replace_rows: std::ops::Range<usize>,
214}
215
216impl EditWindow {
217 fn whole(edit: &LineEdit) -> Self {
218 Self {
219 match_rows: 0..edit.match_rows.len(),
220 replace_rows: 0..edit.replace_rows.len(),
221 }
222 }
223
224 fn trim_front(&mut self) {
225 if !self.match_rows.is_empty() {
226 self.match_rows.start += 1;
227 }
228 if !self.replace_rows.is_empty() {
229 self.replace_rows.start += 1;
230 }
231 }
232
233 fn trim_back(&mut self) {
234 if !self.match_rows.is_empty() {
235 self.match_rows.end -= 1;
236 }
237 if !self.replace_rows.is_empty() {
238 self.replace_rows.end -= 1;
239 }
240 }
241}
242
243fn locate_and_apply<'a>(
244 working: &mut WorkingBlob<'a>,
245 edit: &'a LineEdit,
246 hint: ScanHint,
247 hunk: &Hunk,
248 _hunk_index: usize,
249 insert_only: bool,
250) -> Result<Option<usize>, ApplyError> {
251 let mut window = EditWindow::whole(edit);
252 let mut hint = hint;
253 let mut prefix = edit.stable_prefix;
254 let mut suffix = edit.stable_suffix;
255 let mut pin_front = hint.only_at_front;
256 let mut pin_back = hint.only_at_back;
257
258 loop {
259 let match_rows = &edit.match_rows[window.match_rows.clone()];
260 let replace_rows = &edit.replace_rows[window.replace_rows.clone()];
261 if match_rows.is_empty() {
262 if insert_only && !replace_rows.is_empty() {
263 let row = insert_only_row(hint, working, hunk);
264 splice_edit(working, row, 0, replace_rows);
265 return Ok(Some(row));
266 }
267 if prefix == 0 && suffix == 0 {
268 return Ok(None);
269 }
270 } else if let Some(row) = search_outward(working, match_rows, hint, pin_front, pin_back) {
271 splice_edit(working, row, match_rows.len(), replace_rows);
272 return Ok(Some(row));
273 }
274
275 if pin_front || pin_back {
276 pin_front = false;
277 pin_back = false;
278 continue;
279 }
280 if prefix == 0 && suffix == 0 {
281 return Ok(None);
282 }
283 if prefix >= suffix {
284 window.trim_front();
285 prefix -= 1;
286 hint.start_row = hint.start_row.saturating_sub(1);
287 }
288 if suffix > prefix {
289 window.trim_back();
290 suffix -= 1;
291 }
292 }
293}
294
295fn insert_only_row(hint: ScanHint, working: &WorkingBlob, hunk: &Hunk) -> usize {
296 let len = working.len();
297 let at = hint.start_row.min(len);
298 if hint.only_at_back
299 && hunk.old_count == 0
300 && hunk.old_start > 0
301 && hunk.old_start >= len
302 && hunk.new_start >= hunk.old_start
303 {
304 return len;
305 }
306 at
307}
308
309fn search_outward(
310 working: &WorkingBlob,
311 pattern: &[Vec<u8>],
312 hint: ScanHint,
313 pin_front: bool,
314 pin_back: bool,
315) -> Option<usize> {
316 let width = pattern.len();
317 debug_assert!(!pattern.is_empty());
318 let mut anchor = hint.start_row.min(working.len());
319 if pin_front {
320 anchor = 0;
321 } else if pin_back {
322 anchor = working.len().saturating_sub(width);
323 }
324
325 let mut low = anchor;
326 let mut high = anchor;
327 let mut cursor = anchor;
328
329 let attempts = working.len().saturating_add(width).saturating_add(1);
330 for step in 0..attempts {
331 if rows_equal_pattern(working, cursor, pattern, pin_front, pin_back) {
332 return Some(cursor);
333 }
334
335 let can_low = low > 0;
336 let can_high = high < working.len();
337 if !can_low && !can_high {
338 break;
339 }
340
341 if step & 1 == 1 {
342 if can_low {
343 low -= 1;
344 cursor = low;
345 }
346 } else if can_high {
347 high += 1;
348 cursor = high;
349 }
350 }
351 None
352}
353
354fn rows_equal_pattern(
355 working: &WorkingBlob,
356 at: usize,
357 pattern: &[Vec<u8>],
358 pin_front: bool,
359 pin_back: bool,
360) -> bool {
361 if pin_front && at != 0 {
362 return false;
363 }
364 if pin_back && at + pattern.len() != working.len() {
365 return false;
366 }
367 if at + pattern.len() > working.len() {
368 return false;
369 }
370 let rows = &working.rows[at..at + pattern.len()];
371 let consumed = &working.consumed[at..at + pattern.len()];
372 !consumed.contains(&true)
373 && rows
374 .iter()
375 .zip(pattern)
376 .all(|(row, expected)| *row == expected.as_slice())
377}
378
379fn splice_edit<'a>(
381 working: &mut WorkingBlob<'a>,
382 at: usize,
383 remove: usize,
384 replace_rows: &'a [Vec<u8>],
385) {
386 let end = at + remove.min(working.rows.len().saturating_sub(at));
387 working
388 .rows
389 .splice(at..end, replace_rows.iter().map(Vec::as_slice));
390 working
391 .consumed
392 .splice(at..end, std::iter::repeat_n(true, replace_rows.len()));
393}