mermaid_runtime/
apply_patch.rs

1//! Pure `apply_patch` engine — parser, graduated fuzzy matcher, and applier —
2//! adapted from OpenAI Codex's `apply-patch` crate.
3//!
4//! It lives in the runtime crate (rather than beside the tool) so BOTH the main
5//! crate's `apply_patch` tool AND the approval-replay path can apply patches
6//! without duplicating the engine. It is PURE: parsing and applying operate on
7//! `&str`; all file I/O stays with the callers (via the confined pathguard).
8//!
9//! Trimmed from Codex: no Lark grammar, no `local_shell`/heredoc extraction, no
10//! lenient GPT-4.1 mode, no streaming — the patch arrives as one string.
11
12use std::path::PathBuf;
13
14const BEGIN_PATCH: &str = "*** Begin Patch";
15const END_PATCH: &str = "*** End Patch";
16const ADD_FILE: &str = "*** Add File: ";
17const DELETE_FILE: &str = "*** Delete File: ";
18const UPDATE_FILE: &str = "*** Update File: ";
19const MOVE_TO: &str = "*** Move to: ";
20const EOF_MARKER: &str = "*** End of File";
21const CHANGE_CONTEXT: &str = "@@ ";
22const EMPTY_CHANGE_CONTEXT: &str = "@@";
23
24// ─── parser ─────────────────────────────────────────────────────────
25
26/// A patch parse failure, rendered back to the model so it can fix the envelope.
27#[derive(Debug, PartialEq, Eq)]
28pub enum ParseError {
29    /// The overall envelope is malformed (missing markers, no hunks, stray line).
30    Invalid(String),
31    /// A line inside an update/add hunk is malformed.
32    InvalidHunk { message: String, line_number: usize },
33}
34
35impl std::fmt::Display for ParseError {
36    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
37        match self {
38            Self::Invalid(m) => write!(f, "invalid patch: {m}"),
39            Self::InvalidHunk {
40                message,
41                line_number,
42            } => write!(f, "invalid hunk at patch line {line_number}: {message}"),
43        }
44    }
45}
46
47/// One file operation in a patch.
48#[derive(Debug, PartialEq, Eq, Clone)]
49pub enum Hunk {
50    /// Create a new file with `contents`.
51    AddFile { path: PathBuf, contents: String },
52    /// Delete an existing file.
53    DeleteFile { path: PathBuf },
54    /// Edit (and optionally rename to `move_path`) an existing file.
55    UpdateFile {
56        path: PathBuf,
57        move_path: Option<PathBuf>,
58        chunks: Vec<UpdateFileChunk>,
59    },
60}
61
62/// One contiguous edit region within an `UpdateFile` hunk. `old_lines` is the
63/// span to locate (context + removed lines, in file order); `new_lines` is its
64/// replacement (context + added lines).
65#[derive(Debug, PartialEq, Eq, Clone, Default)]
66pub struct UpdateFileChunk {
67    /// Optional `@@` anchor line used to disambiguate the region's location.
68    pub change_context: Option<String>,
69    pub old_lines: Vec<String>,
70    pub new_lines: Vec<String>,
71    /// The region must sit at the end of the file (tolerant of trailing newline).
72    pub is_end_of_file: bool,
73}
74
75fn is_file_marker(line: &str) -> bool {
76    line.starts_with(ADD_FILE) || line.starts_with(DELETE_FILE) || line.starts_with(UPDATE_FILE)
77}
78
79/// Parse a complete patch into its hunks. Strict: requires the Begin/End markers
80/// (tolerating surrounding blank lines) and rejects stray lines.
81///
82/// # Errors
83///
84/// [`ParseError::Invalid`] when the `Begin Patch` / `End Patch` markers are
85/// missing or a line inside the body belongs to no hunk, and
86/// [`ParseError::InvalidHunk`] — which carries the offending line number —
87/// when a hunk's own body is malformed. Purely textual: no path here is
88/// opened or checked
89/// for existence, so a patch against a file that is not there still parses.
90pub fn parse_patch(patch: &str) -> Result<Vec<Hunk>, ParseError> {
91    let raw: Vec<&str> = patch.lines().collect();
92    let start = raw
93        .iter()
94        .position(|l| l.trim_end() == BEGIN_PATCH)
95        .ok_or_else(|| ParseError::Invalid(format!("missing '{BEGIN_PATCH}' line")))?;
96    let end_rel = raw[start + 1..]
97        .iter()
98        .position(|l| l.trim_end() == END_PATCH)
99        .ok_or_else(|| ParseError::Invalid(format!("missing '{END_PATCH}' line")))?;
100    let body = &raw[start + 1..start + 1 + end_rel];
101
102    let mut hunks = Vec::new();
103    let mut i = 0;
104    while i < body.len() {
105        let line = body[i];
106        if let Some(path) = line.strip_prefix(ADD_FILE) {
107            let contents = parse_add_contents(body, &mut i)?;
108            hunks.push(Hunk::AddFile {
109                path: PathBuf::from(path.trim()),
110                contents,
111            });
112        } else if let Some(path) = line.strip_prefix(DELETE_FILE) {
113            hunks.push(Hunk::DeleteFile {
114                path: PathBuf::from(path.trim()),
115            });
116            i += 1;
117        } else if let Some(path) = line.strip_prefix(UPDATE_FILE) {
118            i += 1;
119            let move_path = body
120                .get(i)
121                .and_then(|l| l.strip_prefix(MOVE_TO))
122                .map(|dst| {
123                    i += 1;
124                    PathBuf::from(dst.trim())
125                });
126            let chunks = parse_update_chunks(body, &mut i)?;
127            hunks.push(Hunk::UpdateFile {
128                path: PathBuf::from(path.trim()),
129                move_path,
130                chunks,
131            });
132        } else if line.trim().is_empty() {
133            i += 1;
134        } else {
135            return Err(ParseError::Invalid(format!(
136                "unexpected line outside a hunk: {line:?}"
137            )));
138        }
139    }
140    if hunks.is_empty() {
141        return Err(ParseError::Invalid("patch contains no hunks".to_string()));
142    }
143    Ok(hunks)
144}
145
146fn parse_add_contents(body: &[&str], i: &mut usize) -> Result<String, ParseError> {
147    *i += 1;
148    let mut lines: Vec<&str> = Vec::new();
149    while *i < body.len() && !is_file_marker(body[*i]) {
150        let l = body[*i];
151        let content = l.strip_prefix('+').ok_or_else(|| ParseError::InvalidHunk {
152            message: format!("expected a '+' line in an Add File hunk, got {l:?}"),
153            line_number: *i,
154        })?;
155        lines.push(content);
156        *i += 1;
157    }
158    Ok(lines.join("\n"))
159}
160
161fn parse_update_chunks(body: &[&str], i: &mut usize) -> Result<Vec<UpdateFileChunk>, ParseError> {
162    let mut chunks: Vec<UpdateFileChunk> = Vec::new();
163    let mut current: Option<UpdateFileChunk> = None;
164    while *i < body.len() && !is_file_marker(body[*i]) {
165        let l = body[*i];
166        if l == EMPTY_CHANGE_CONTEXT || l.starts_with(CHANGE_CONTEXT) {
167            if let Some(c) = current.take() {
168                chunks.push(c);
169            }
170            current = Some(UpdateFileChunk {
171                change_context: l.strip_prefix(CHANGE_CONTEXT).map(str::to_string),
172                ..Default::default()
173            });
174        } else if l == EOF_MARKER {
175            current
176                .get_or_insert_with(UpdateFileChunk::default)
177                .is_end_of_file = true;
178        } else {
179            let c = current.get_or_insert_with(UpdateFileChunk::default);
180            match l.chars().next() {
181                Some('+') => c.new_lines.push(l[1..].to_string()),
182                Some('-') => c.old_lines.push(l[1..].to_string()),
183                Some(' ') => {
184                    let s = l[1..].to_string();
185                    c.old_lines.push(s.clone());
186                    c.new_lines.push(s);
187                },
188                None => {
189                    c.old_lines.push(String::new());
190                    c.new_lines.push(String::new());
191                },
192                _ => {
193                    return Err(ParseError::InvalidHunk {
194                        message: format!("unexpected line in an update hunk: {l:?}"),
195                        line_number: *i,
196                    });
197                },
198            }
199        }
200        *i += 1;
201    }
202    if let Some(c) = current.take() {
203        chunks.push(c);
204    }
205    if chunks.is_empty() {
206        return Err(ParseError::InvalidHunk {
207            message: "update hunk has no changes".to_string(),
208            line_number: *i,
209        });
210    }
211    Ok(chunks)
212}
213
214// ─── matcher ────────────────────────────────────────────────────────
215
216/// A located match: the starting line index, and whether it was byte-exact.
217struct SeekHit {
218    index: usize,
219    exact: bool,
220}
221
222/// Find `pattern` within `lines` at or after `start`, in decreasing strictness:
223/// exact, trailing-whitespace-insensitive, full-trim, then Unicode-normalized.
224/// When `eof` is set, the search anchors at the end of the file first.
225fn seek_sequence(lines: &[String], pattern: &[String], start: usize, eof: bool) -> Option<SeekHit> {
226    if pattern.is_empty() {
227        return Some(SeekHit {
228            index: start,
229            exact: true,
230        });
231    }
232    if pattern.len() > lines.len() {
233        return None;
234    }
235    let search_start = if eof {
236        lines.len() - pattern.len()
237    } else {
238        start
239    };
240    let last = lines.len().saturating_sub(pattern.len());
241
242    for i in search_start..=last {
243        if lines[i..i + pattern.len()] == *pattern {
244            return Some(SeekHit {
245                index: i,
246                exact: true,
247            });
248        }
249    }
250    for i in search_start..=last {
251        if pattern
252            .iter()
253            .enumerate()
254            .all(|(p, pat)| lines[i + p].trim_end() == pat.trim_end())
255        {
256            return Some(SeekHit {
257                index: i,
258                exact: false,
259            });
260        }
261    }
262    for i in search_start..=last {
263        if pattern
264            .iter()
265            .enumerate()
266            .all(|(p, pat)| lines[i + p].trim() == pat.trim())
267        {
268            return Some(SeekHit {
269                index: i,
270                exact: false,
271            });
272        }
273    }
274    for i in search_start..=last {
275        if pattern
276            .iter()
277            .enumerate()
278            .all(|(p, pat)| normalise(&lines[i + p]) == normalise(pat))
279        {
280            return Some(SeekHit {
281                index: i,
282                exact: false,
283            });
284        }
285    }
286    None
287}
288
289/// Normalize typographic punctuation and spaces to their ASCII equivalents.
290fn normalise(s: &str) -> String {
291    s.trim()
292        .chars()
293        .map(|c| match c {
294            '\u{2010}' | '\u{2011}' | '\u{2012}' | '\u{2013}' | '\u{2014}' | '\u{2015}'
295            | '\u{2212}' => '-',
296            '\u{2018}' | '\u{2019}' | '\u{201A}' | '\u{201B}' => '\'',
297            '\u{201C}' | '\u{201D}' | '\u{201E}' | '\u{201F}' => '"',
298            '\u{00A0}' | '\u{2002}' | '\u{2003}' | '\u{2004}' | '\u{2005}' | '\u{2006}'
299            | '\u{2007}' | '\u{2008}' | '\u{2009}' | '\u{200A}' | '\u{202F}' | '\u{205F}'
300            | '\u{3000}' => ' ',
301            other => other,
302        })
303        .collect()
304}
305
306// ─── applier ────────────────────────────────────────────────────────
307
308/// Why applying an update hunk failed. Rendered back to the model.
309#[derive(Debug, PartialEq, Eq)]
310pub enum ApplyError {
311    /// A `@@` context anchor could not be located in the file.
312    ContextNotFound(String),
313    /// The `old_lines` span could not be located in the file.
314    LinesNotFound(String),
315}
316
317impl std::fmt::Display for ApplyError {
318    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
319        match self {
320            Self::ContextNotFound(c) => write!(f, "could not find context line '{c}'"),
321            Self::LinesNotFound(l) => write!(f, "could not find the lines to replace:\n{l}"),
322        }
323    }
324}
325
326/// The result of applying chunks: the new file text and whether any chunk had to
327/// be located fuzzily (whitespace/Unicode-normalized rather than byte-exact).
328pub struct AppliedFile {
329    pub new_contents: String,
330    pub fuzzy: bool,
331}
332
333/// Apply `chunks` to `original`, returning the new file contents.
334///
335/// # Errors
336///
337/// [`ApplyError::ContextNotFound`] when a chunk's `@@` anchor is nowhere in
338/// the file, and [`ApplyError::LinesNotFound`] when its `old_lines` span is
339/// not locatable from the current position. Both are searched
340/// whitespace/Unicode-normalized before failing, so an `Err` means the region
341/// is genuinely absent, not merely reformatted — a fuzzy match succeeds and
342/// reports itself through `AppliedFile::fuzzy`.
343pub fn derive_new_contents(
344    original: &str,
345    chunks: &[UpdateFileChunk],
346) -> Result<AppliedFile, ApplyError> {
347    let mut lines: Vec<String> = original.split('\n').map(String::from).collect();
348    if lines.last().is_some_and(String::is_empty) {
349        lines.pop();
350    }
351    let (replacements, fuzzy) = compute_replacements(&lines, chunks)?;
352    let mut new_lines = apply_replacements(lines, &replacements);
353    if !new_lines.last().is_some_and(String::is_empty) {
354        new_lines.push(String::new());
355    }
356    Ok(AppliedFile {
357        new_contents: new_lines.join("\n"),
358        fuzzy,
359    })
360}
361
362type Replacement = (usize, usize, Vec<String>);
363
364fn compute_replacements(
365    original_lines: &[String],
366    chunks: &[UpdateFileChunk],
367) -> Result<(Vec<Replacement>, bool), ApplyError> {
368    let mut replacements: Vec<Replacement> = Vec::new();
369    let mut line_index = 0usize;
370    let mut fuzzy = false;
371
372    for chunk in chunks {
373        if let Some(ctx) = &chunk.change_context {
374            match seek_sequence(original_lines, std::slice::from_ref(ctx), line_index, false) {
375                Some(hit) => {
376                    fuzzy |= !hit.exact;
377                    line_index = hit.index + 1;
378                },
379                None => return Err(ApplyError::ContextNotFound(ctx.clone())),
380            }
381        }
382
383        if chunk.old_lines.is_empty() {
384            let idx = if original_lines.last().is_some_and(String::is_empty) {
385                original_lines.len() - 1
386            } else {
387                original_lines.len()
388            };
389            replacements.push((idx, 0, chunk.new_lines.clone()));
390            continue;
391        }
392
393        let mut pattern: &[String] = &chunk.old_lines;
394        let mut new_slice: &[String] = &chunk.new_lines;
395        let mut found = seek_sequence(original_lines, pattern, line_index, chunk.is_end_of_file);
396        if found.is_none() && pattern.last().is_some_and(String::is_empty) {
397            pattern = &pattern[..pattern.len() - 1];
398            if new_slice.last().is_some_and(String::is_empty) {
399                new_slice = &new_slice[..new_slice.len() - 1];
400            }
401            found = seek_sequence(original_lines, pattern, line_index, chunk.is_end_of_file);
402        }
403
404        match found {
405            Some(hit) => {
406                fuzzy |= !hit.exact;
407                replacements.push((hit.index, pattern.len(), new_slice.to_vec()));
408                line_index = hit.index + pattern.len();
409            },
410            None => return Err(ApplyError::LinesNotFound(chunk.old_lines.join("\n"))),
411        }
412    }
413
414    replacements.sort_by_key(|(i, _, _)| *i);
415    Ok((replacements, fuzzy))
416}
417
418fn apply_replacements(mut lines: Vec<String>, replacements: &[Replacement]) -> Vec<String> {
419    for (start_idx, old_len, new_segment) in replacements.iter().rev() {
420        let start_idx = *start_idx;
421        for _ in 0..*old_len {
422            if start_idx < lines.len() {
423                lines.remove(start_idx);
424            }
425        }
426        for (offset, new_line) in new_segment.iter().enumerate() {
427            lines.insert(start_idx + offset, new_line.clone());
428        }
429    }
430    lines
431}
432
433#[cfg(test)]
434mod tests {
435    use super::*;
436
437    fn v(items: &[&str]) -> Vec<String> {
438        items.iter().map(|s| s.to_string()).collect()
439    }
440
441    fn chunk(ctx: Option<&str>, old: &[&str], new: &[&str], eof: bool) -> UpdateFileChunk {
442        UpdateFileChunk {
443            change_context: ctx.map(str::to_string),
444            old_lines: v(old),
445            new_lines: v(new),
446            is_end_of_file: eof,
447        }
448    }
449
450    #[test]
451    fn parses_update_add_delete_move() {
452        let patch = "*** Begin Patch\n*** Update File: src/main.rs\n@@ fn main()\n-    old();\n+    new();\n*** End Patch\n";
453        assert_eq!(
454            parse_patch(patch).unwrap(),
455            vec![Hunk::UpdateFile {
456                path: PathBuf::from("src/main.rs"),
457                move_path: None,
458                chunks: vec![chunk(
459                    Some("fn main()"),
460                    &["    old();"],
461                    &["    new();"],
462                    false
463                )],
464            }]
465        );
466        assert_eq!(
467            parse_patch("*** Begin Patch\n*** Add File: a.txt\n+x\n+y\n*** End Patch").unwrap(),
468            vec![Hunk::AddFile {
469                path: PathBuf::from("a.txt"),
470                contents: "x\ny".to_string(),
471            }]
472        );
473        let mv =
474            "*** Begin Patch\n*** Update File: old.rs\n*** Move to: new.rs\n-a\n+b\n*** End Patch";
475        match &parse_patch(mv).unwrap()[0] {
476            Hunk::UpdateFile { move_path, .. } => {
477                assert_eq!(move_path.as_deref(), Some(std::path::Path::new("new.rs")))
478            },
479            other => panic!("expected UpdateFile, got {other:?}"),
480        }
481    }
482
483    #[test]
484    fn context_lines_go_to_both_sides_and_eof_flag() {
485        match &parse_patch("*** Begin Patch\n*** Update File: x\n import foo\n+bar\n*** End Patch")
486            .unwrap()[0]
487        {
488            Hunk::UpdateFile { chunks, .. } => {
489                assert_eq!(chunks[0].old_lines, v(&["import foo"]));
490                assert_eq!(chunks[0].new_lines, v(&["import foo", "bar"]));
491            },
492            other => panic!("expected UpdateFile, got {other:?}"),
493        }
494        match &parse_patch(
495            "*** Begin Patch\n*** Update File: x\n+quux\n*** End of File\n*** End Patch",
496        )
497        .unwrap()[0]
498        {
499            Hunk::UpdateFile { chunks, .. } => assert!(chunks[0].is_end_of_file),
500            other => panic!("expected UpdateFile, got {other:?}"),
501        }
502    }
503
504    #[test]
505    fn rejects_missing_markers_and_empty() {
506        assert!(parse_patch("no markers").is_err());
507        assert!(parse_patch("*** Begin Patch\n*** End Patch").is_err());
508    }
509
510    #[test]
511    fn seek_reports_exact_vs_fuzzy_and_eof() {
512        assert!(
513            seek_sequence(&v(&["foo", "bar"]), &v(&["bar"]), 0, false)
514                .unwrap()
515                .exact
516        );
517        let fuzzy = seek_sequence(&v(&["foo   "]), &v(&["foo"]), 0, false).unwrap();
518        assert!(!fuzzy.exact);
519        assert!(seek_sequence(&v(&["only"]), &v(&["a", "b"]), 0, false).is_none());
520        assert_eq!(
521            seek_sequence(&v(&["a", "x", "b", "x"]), &v(&["x"]), 0, true)
522                .unwrap()
523                .index,
524            3
525        );
526    }
527
528    #[test]
529    fn applies_exact_fuzzy_anchor_and_eof() {
530        assert_eq!(
531            derive_new_contents("a\nold\nc\n", &[chunk(None, &["old"], &["new"], false)])
532                .unwrap()
533                .new_contents,
534            "a\nnew\nc\n"
535        );
536        let f = derive_new_contents("a\nold   \nc\n", &[chunk(None, &["old"], &["new"], false)])
537            .unwrap();
538        assert_eq!(f.new_contents, "a\nnew\nc\n");
539        assert!(f.fuzzy);
540        // Anchor picks the SECOND identical block.
541        let out = derive_new_contents(
542            "fn a() {\n    x();\n}\nfn b() {\n    x();\n}\n",
543            &[chunk(Some("fn b() {"), &["    x();"], &["    y();"], false)],
544        )
545        .unwrap();
546        assert_eq!(
547            out.new_contents,
548            "fn a() {\n    x();\n}\nfn b() {\n    y();\n}\n"
549        );
550        assert_eq!(
551            derive_new_contents("a\nb\n", &[chunk(None, &[], &["c"], true)])
552                .unwrap()
553                .new_contents,
554            "a\nb\nc\n"
555        );
556    }
557
558    #[test]
559    fn apply_errors_on_missing_context_or_lines() {
560        assert!(matches!(
561            derive_new_contents("a\n", &[chunk(Some("nope"), &["a"], &["b"], false)]),
562            Err(ApplyError::ContextNotFound(c)) if c == "nope"
563        ));
564        assert!(matches!(
565            derive_new_contents("a\n", &[chunk(None, &["zzz"], &["b"], false)]),
566            Err(ApplyError::LinesNotFound(_))
567        ));
568    }
569}
mermaid_runtime/apply_patch.rs

mermaid_runtime/
apply_patch.rs
