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            ParseError::Invalid(m) => write!(f, "invalid patch: {m}"),
39            ParseError::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.
81pub fn parse_patch(patch: &str) -> Result<Vec<Hunk>, ParseError> {
82    let raw: Vec<&str> = patch.lines().collect();
83    let start = raw
84        .iter()
85        .position(|l| l.trim_end() == BEGIN_PATCH)
86        .ok_or_else(|| ParseError::Invalid(format!("missing '{BEGIN_PATCH}' line")))?;
87    let end_rel = raw[start + 1..]
88        .iter()
89        .position(|l| l.trim_end() == END_PATCH)
90        .ok_or_else(|| ParseError::Invalid(format!("missing '{END_PATCH}' line")))?;
91    let body = &raw[start + 1..start + 1 + end_rel];
92
93    let mut hunks = Vec::new();
94    let mut i = 0;
95    while i < body.len() {
96        let line = body[i];
97        if let Some(path) = line.strip_prefix(ADD_FILE) {
98            let contents = parse_add_contents(body, &mut i)?;
99            hunks.push(Hunk::AddFile {
100                path: PathBuf::from(path.trim()),
101                contents,
102            });
103        } else if let Some(path) = line.strip_prefix(DELETE_FILE) {
104            hunks.push(Hunk::DeleteFile {
105                path: PathBuf::from(path.trim()),
106            });
107            i += 1;
108        } else if let Some(path) = line.strip_prefix(UPDATE_FILE) {
109            i += 1;
110            let move_path = body
111                .get(i)
112                .and_then(|l| l.strip_prefix(MOVE_TO))
113                .map(|dst| {
114                    i += 1;
115                    PathBuf::from(dst.trim())
116                });
117            let chunks = parse_update_chunks(body, &mut i)?;
118            hunks.push(Hunk::UpdateFile {
119                path: PathBuf::from(path.trim()),
120                move_path,
121                chunks,
122            });
123        } else if line.trim().is_empty() {
124            i += 1;
125        } else {
126            return Err(ParseError::Invalid(format!(
127                "unexpected line outside a hunk: {line:?}"
128            )));
129        }
130    }
131    if hunks.is_empty() {
132        return Err(ParseError::Invalid("patch contains no hunks".to_string()));
133    }
134    Ok(hunks)
135}
136
137fn parse_add_contents(body: &[&str], i: &mut usize) -> Result<String, ParseError> {
138    *i += 1;
139    let mut lines: Vec<&str> = Vec::new();
140    while *i < body.len() && !is_file_marker(body[*i]) {
141        let l = body[*i];
142        let content = l.strip_prefix('+').ok_or_else(|| ParseError::InvalidHunk {
143            message: format!("expected a '+' line in an Add File hunk, got {l:?}"),
144            line_number: *i,
145        })?;
146        lines.push(content);
147        *i += 1;
148    }
149    Ok(lines.join("\n"))
150}
151
152fn parse_update_chunks(body: &[&str], i: &mut usize) -> Result<Vec<UpdateFileChunk>, ParseError> {
153    let mut chunks: Vec<UpdateFileChunk> = Vec::new();
154    let mut current: Option<UpdateFileChunk> = None;
155    while *i < body.len() && !is_file_marker(body[*i]) {
156        let l = body[*i];
157        if l == EMPTY_CHANGE_CONTEXT || l.starts_with(CHANGE_CONTEXT) {
158            if let Some(c) = current.take() {
159                chunks.push(c);
160            }
161            current = Some(UpdateFileChunk {
162                change_context: l.strip_prefix(CHANGE_CONTEXT).map(str::to_string),
163                ..Default::default()
164            });
165        } else if l == EOF_MARKER {
166            current
167                .get_or_insert_with(UpdateFileChunk::default)
168                .is_end_of_file = true;
169        } else {
170            let c = current.get_or_insert_with(UpdateFileChunk::default);
171            match l.chars().next() {
172                Some('+') => c.new_lines.push(l[1..].to_string()),
173                Some('-') => c.old_lines.push(l[1..].to_string()),
174                Some(' ') => {
175                    let s = l[1..].to_string();
176                    c.old_lines.push(s.clone());
177                    c.new_lines.push(s);
178                },
179                None => {
180                    c.old_lines.push(String::new());
181                    c.new_lines.push(String::new());
182                },
183                _ => {
184                    return Err(ParseError::InvalidHunk {
185                        message: format!("unexpected line in an update hunk: {l:?}"),
186                        line_number: *i,
187                    });
188                },
189            }
190        }
191        *i += 1;
192    }
193    if let Some(c) = current.take() {
194        chunks.push(c);
195    }
196    if chunks.is_empty() {
197        return Err(ParseError::InvalidHunk {
198            message: "update hunk has no changes".to_string(),
199            line_number: *i,
200        });
201    }
202    Ok(chunks)
203}
204
205// ─── matcher ────────────────────────────────────────────────────────
206
207/// A located match: the starting line index, and whether it was byte-exact.
208struct SeekHit {
209    index: usize,
210    exact: bool,
211}
212
213/// Find `pattern` within `lines` at or after `start`, in decreasing strictness:
214/// exact, trailing-whitespace-insensitive, full-trim, then Unicode-normalized.
215/// When `eof` is set, the search anchors at the end of the file first.
216fn seek_sequence(lines: &[String], pattern: &[String], start: usize, eof: bool) -> Option<SeekHit> {
217    if pattern.is_empty() {
218        return Some(SeekHit {
219            index: start,
220            exact: true,
221        });
222    }
223    if pattern.len() > lines.len() {
224        return None;
225    }
226    let search_start = if eof {
227        lines.len() - pattern.len()
228    } else {
229        start
230    };
231    let last = lines.len().saturating_sub(pattern.len());
232
233    for i in search_start..=last {
234        if lines[i..i + pattern.len()] == *pattern {
235            return Some(SeekHit {
236                index: i,
237                exact: true,
238            });
239        }
240    }
241    for i in search_start..=last {
242        if pattern
243            .iter()
244            .enumerate()
245            .all(|(p, pat)| lines[i + p].trim_end() == pat.trim_end())
246        {
247            return Some(SeekHit {
248                index: i,
249                exact: false,
250            });
251        }
252    }
253    for i in search_start..=last {
254        if pattern
255            .iter()
256            .enumerate()
257            .all(|(p, pat)| lines[i + p].trim() == pat.trim())
258        {
259            return Some(SeekHit {
260                index: i,
261                exact: false,
262            });
263        }
264    }
265    for i in search_start..=last {
266        if pattern
267            .iter()
268            .enumerate()
269            .all(|(p, pat)| normalise(&lines[i + p]) == normalise(pat))
270        {
271            return Some(SeekHit {
272                index: i,
273                exact: false,
274            });
275        }
276    }
277    None
278}
279
280/// Normalize typographic punctuation and spaces to their ASCII equivalents.
281fn normalise(s: &str) -> String {
282    s.trim()
283        .chars()
284        .map(|c| match c {
285            '\u{2010}' | '\u{2011}' | '\u{2012}' | '\u{2013}' | '\u{2014}' | '\u{2015}'
286            | '\u{2212}' => '-',
287            '\u{2018}' | '\u{2019}' | '\u{201A}' | '\u{201B}' => '\'',
288            '\u{201C}' | '\u{201D}' | '\u{201E}' | '\u{201F}' => '"',
289            '\u{00A0}' | '\u{2002}' | '\u{2003}' | '\u{2004}' | '\u{2005}' | '\u{2006}'
290            | '\u{2007}' | '\u{2008}' | '\u{2009}' | '\u{200A}' | '\u{202F}' | '\u{205F}'
291            | '\u{3000}' => ' ',
292            other => other,
293        })
294        .collect()
295}
296
297// ─── applier ────────────────────────────────────────────────────────
298
299/// Why applying an update hunk failed. Rendered back to the model.
300#[derive(Debug, PartialEq, Eq)]
301pub enum ApplyError {
302    /// A `@@` context anchor could not be located in the file.
303    ContextNotFound(String),
304    /// The `old_lines` span could not be located in the file.
305    LinesNotFound(String),
306}
307
308impl std::fmt::Display for ApplyError {
309    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
310        match self {
311            ApplyError::ContextNotFound(c) => write!(f, "could not find context line '{c}'"),
312            ApplyError::LinesNotFound(l) => write!(f, "could not find the lines to replace:\n{l}"),
313        }
314    }
315}
316
317/// The result of applying chunks: the new file text and whether any chunk had to
318/// be located fuzzily (whitespace/Unicode-normalized rather than byte-exact).
319pub struct AppliedFile {
320    pub new_contents: String,
321    pub fuzzy: bool,
322}
323
324/// Apply `chunks` to `original`, returning the new file contents.
325pub fn derive_new_contents(
326    original: &str,
327    chunks: &[UpdateFileChunk],
328) -> Result<AppliedFile, ApplyError> {
329    let mut lines: Vec<String> = original.split('\n').map(String::from).collect();
330    if lines.last().is_some_and(String::is_empty) {
331        lines.pop();
332    }
333    let (replacements, fuzzy) = compute_replacements(&lines, chunks)?;
334    let mut new_lines = apply_replacements(lines, &replacements);
335    if !new_lines.last().is_some_and(String::is_empty) {
336        new_lines.push(String::new());
337    }
338    Ok(AppliedFile {
339        new_contents: new_lines.join("\n"),
340        fuzzy,
341    })
342}
343
344type Replacement = (usize, usize, Vec<String>);
345
346fn compute_replacements(
347    original_lines: &[String],
348    chunks: &[UpdateFileChunk],
349) -> Result<(Vec<Replacement>, bool), ApplyError> {
350    let mut replacements: Vec<Replacement> = Vec::new();
351    let mut line_index = 0usize;
352    let mut fuzzy = false;
353
354    for chunk in chunks {
355        if let Some(ctx) = &chunk.change_context {
356            match seek_sequence(original_lines, std::slice::from_ref(ctx), line_index, false) {
357                Some(hit) => {
358                    fuzzy |= !hit.exact;
359                    line_index = hit.index + 1;
360                },
361                None => return Err(ApplyError::ContextNotFound(ctx.clone())),
362            }
363        }
364
365        if chunk.old_lines.is_empty() {
366            let idx = if original_lines.last().is_some_and(String::is_empty) {
367                original_lines.len() - 1
368            } else {
369                original_lines.len()
370            };
371            replacements.push((idx, 0, chunk.new_lines.clone()));
372            continue;
373        }
374
375        let mut pattern: &[String] = &chunk.old_lines;
376        let mut new_slice: &[String] = &chunk.new_lines;
377        let mut found = seek_sequence(original_lines, pattern, line_index, chunk.is_end_of_file);
378        if found.is_none() && pattern.last().is_some_and(String::is_empty) {
379            pattern = &pattern[..pattern.len() - 1];
380            if new_slice.last().is_some_and(String::is_empty) {
381                new_slice = &new_slice[..new_slice.len() - 1];
382            }
383            found = seek_sequence(original_lines, pattern, line_index, chunk.is_end_of_file);
384        }
385
386        match found {
387            Some(hit) => {
388                fuzzy |= !hit.exact;
389                replacements.push((hit.index, pattern.len(), new_slice.to_vec()));
390                line_index = hit.index + pattern.len();
391            },
392            None => return Err(ApplyError::LinesNotFound(chunk.old_lines.join("\n"))),
393        }
394    }
395
396    replacements.sort_by_key(|(i, _, _)| *i);
397    Ok((replacements, fuzzy))
398}
399
400fn apply_replacements(mut lines: Vec<String>, replacements: &[Replacement]) -> Vec<String> {
401    for (start_idx, old_len, new_segment) in replacements.iter().rev() {
402        let start_idx = *start_idx;
403        for _ in 0..*old_len {
404            if start_idx < lines.len() {
405                lines.remove(start_idx);
406            }
407        }
408        for (offset, new_line) in new_segment.iter().enumerate() {
409            lines.insert(start_idx + offset, new_line.clone());
410        }
411    }
412    lines
413}
414
415#[cfg(test)]
416mod tests {
417    use super::*;
418
419    fn v(items: &[&str]) -> Vec<String> {
420        items.iter().map(|s| s.to_string()).collect()
421    }
422
423    fn chunk(ctx: Option<&str>, old: &[&str], new: &[&str], eof: bool) -> UpdateFileChunk {
424        UpdateFileChunk {
425            change_context: ctx.map(str::to_string),
426            old_lines: v(old),
427            new_lines: v(new),
428            is_end_of_file: eof,
429        }
430    }
431
432    #[test]
433    fn parses_update_add_delete_move() {
434        let patch = "*** Begin Patch\n*** Update File: src/main.rs\n@@ fn main()\n-    old();\n+    new();\n*** End Patch\n";
435        assert_eq!(
436            parse_patch(patch).unwrap(),
437            vec![Hunk::UpdateFile {
438                path: PathBuf::from("src/main.rs"),
439                move_path: None,
440                chunks: vec![chunk(
441                    Some("fn main()"),
442                    &["    old();"],
443                    &["    new();"],
444                    false
445                )],
446            }]
447        );
448        assert_eq!(
449            parse_patch("*** Begin Patch\n*** Add File: a.txt\n+x\n+y\n*** End Patch").unwrap(),
450            vec![Hunk::AddFile {
451                path: PathBuf::from("a.txt"),
452                contents: "x\ny".to_string(),
453            }]
454        );
455        let mv =
456            "*** Begin Patch\n*** Update File: old.rs\n*** Move to: new.rs\n-a\n+b\n*** End Patch";
457        match &parse_patch(mv).unwrap()[0] {
458            Hunk::UpdateFile { move_path, .. } => {
459                assert_eq!(move_path.as_deref(), Some(std::path::Path::new("new.rs")))
460            },
461            other => panic!("expected UpdateFile, got {other:?}"),
462        }
463    }
464
465    #[test]
466    fn context_lines_go_to_both_sides_and_eof_flag() {
467        match &parse_patch("*** Begin Patch\n*** Update File: x\n import foo\n+bar\n*** End Patch")
468            .unwrap()[0]
469        {
470            Hunk::UpdateFile { chunks, .. } => {
471                assert_eq!(chunks[0].old_lines, v(&["import foo"]));
472                assert_eq!(chunks[0].new_lines, v(&["import foo", "bar"]));
473            },
474            other => panic!("expected UpdateFile, got {other:?}"),
475        }
476        match &parse_patch(
477            "*** Begin Patch\n*** Update File: x\n+quux\n*** End of File\n*** End Patch",
478        )
479        .unwrap()[0]
480        {
481            Hunk::UpdateFile { chunks, .. } => assert!(chunks[0].is_end_of_file),
482            other => panic!("expected UpdateFile, got {other:?}"),
483        }
484    }
485
486    #[test]
487    fn rejects_missing_markers_and_empty() {
488        assert!(parse_patch("no markers").is_err());
489        assert!(parse_patch("*** Begin Patch\n*** End Patch").is_err());
490    }
491
492    #[test]
493    fn seek_reports_exact_vs_fuzzy_and_eof() {
494        assert!(
495            seek_sequence(&v(&["foo", "bar"]), &v(&["bar"]), 0, false)
496                .unwrap()
497                .exact
498        );
499        let fuzzy = seek_sequence(&v(&["foo   "]), &v(&["foo"]), 0, false).unwrap();
500        assert!(!fuzzy.exact);
501        assert!(seek_sequence(&v(&["only"]), &v(&["a", "b"]), 0, false).is_none());
502        assert_eq!(
503            seek_sequence(&v(&["a", "x", "b", "x"]), &v(&["x"]), 0, true)
504                .unwrap()
505                .index,
506            3
507        );
508    }
509
510    #[test]
511    fn applies_exact_fuzzy_anchor_and_eof() {
512        assert_eq!(
513            derive_new_contents("a\nold\nc\n", &[chunk(None, &["old"], &["new"], false)])
514                .unwrap()
515                .new_contents,
516            "a\nnew\nc\n"
517        );
518        let f = derive_new_contents("a\nold   \nc\n", &[chunk(None, &["old"], &["new"], false)])
519            .unwrap();
520        assert_eq!(f.new_contents, "a\nnew\nc\n");
521        assert!(f.fuzzy);
522        // Anchor picks the SECOND identical block.
523        let out = derive_new_contents(
524            "fn a() {\n    x();\n}\nfn b() {\n    x();\n}\n",
525            &[chunk(Some("fn b() {"), &["    x();"], &["    y();"], false)],
526        )
527        .unwrap();
528        assert_eq!(
529            out.new_contents,
530            "fn a() {\n    x();\n}\nfn b() {\n    y();\n}\n"
531        );
532        assert_eq!(
533            derive_new_contents("a\nb\n", &[chunk(None, &[], &["c"], true)])
534                .unwrap()
535                .new_contents,
536            "a\nb\nc\n"
537        );
538    }
539
540    #[test]
541    fn apply_errors_on_missing_context_or_lines() {
542        assert!(matches!(
543            derive_new_contents("a\n", &[chunk(Some("nope"), &["a"], &["b"], false)]),
544            Err(ApplyError::ContextNotFound(c)) if c == "nope"
545        ));
546        assert!(matches!(
547            derive_new_contents("a\n", &[chunk(None, &["zzz"], &["b"], false)]),
548            Err(ApplyError::LinesNotFound(_))
549        ));
550    }
551}
mermaid_runtime/apply_patch.rs

mermaid_runtime/
apply_patch.rs
