Skip to main content

grit_lib/apply/
apply_blob.rs

1//! Apply parsed unified-diff hunks to a single blob (no worktree or index I/O).
2
3use super::{Hunk, HunkLine};
4use crate::error::ApplyError;
5
6/// Options controlling blob-level hunk application.
7#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
8pub struct ApplyOptions {
9    /// When true, interpret the patch as reversing a forward diff (`+`/`-` swapped).
10    pub reverse: bool,
11}
12
13/// Mutable line-split view of blob bytes while hunks are applied in order.
14///
15/// Each row is one line, with its `\n` when the source line had one. Untouched rows borrow from
16/// the original blob and rows written by a hunk borrow from that hunk's [`LineEdit`], so the
17/// view never copies line bytes.
18#[derive(Debug, Clone)]
19struct WorkingBlob<'a> {
20    rows: Vec<&'a [u8]>,
21    /// Set for rows an earlier hunk wrote (later hunks must not match through them).
22    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/// Lines that must match in the working blob vs lines that replace them.
54#[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/// Where to start scanning for [`LineEdit::match_rows`].
63#[derive(Debug, Clone, Copy)]
64struct ScanHint {
65    /// 0-based row index in the current working blob.
66    start_row: usize,
67    /// Match only when the edit aligns with the first row of the blob.
68    only_at_front: bool,
69    /// Match only when the edit ends on the last row of the blob.
70    only_at_back: bool,
71}
72
73/// Apply `hunks` to `original` and return the post-image bytes.
74///
75/// Matches `git apply` default behavior: exact line match at the hunk's post-image
76/// line (`new_start` forward, `old_start` when reversing), then search outward;
77/// prefix/suffix context rows may be dropped and the search retried. No fuzz or
78/// whitespace fixing.
79pub 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        // Pin to EOF only when the hunk had leading context but no trailing context
127        // (a change that ends at the file end). Zero-context hunks (`-U0`) must not
128        // take this pin unless we add an explicit unidiff-zero mode; otherwise a line
129        // that also appears at EOF is matched at the wrong row.
130        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/// The rows of a [`LineEdit`] still in play after dropping context from its ends.
210#[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
379/// Replace `remove` rows at `at` with `replace_rows`, marking the new rows consumed.
380fn 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}