codex_apply_patch/
parser.rs

1//! This module is responsible for parsing & validating a patch into a list of "hunks".
2//! (It does not attempt to actually check that the patch can be applied to the filesystem.)
3//!
4//! The official Lark grammar for the apply-patch format is:
5//!
6//! start: begin_patch environment_id? hunk+ end_patch
7//! begin_patch: "*** Begin Patch" LF
8//! environment_id: "*** Environment ID: " filename LF
9//! end_patch: "*** End Patch" LF?
10//!
11//! hunk: add_hunk | delete_hunk | update_hunk
12//! add_hunk: "*** Add File: " filename LF add_line+
13//! delete_hunk: "*** Delete File: " filename LF
14//! update_hunk: "*** Update File: " filename LF change_move? change?
15//! filename: /(.+)/
16//! add_line: "+" /(.+)/ LF -> line
17//!
18//! change_move: "*** Move to: " filename LF
19//! change: (change_context | change_line)+ eof_line?
20//! change_context: ("@@" | "@@ " /(.+)/) LF
21//! change_line: ("+" | "-" | " ") /(.+)/ LF
22//! eof_line: "*** End of File" LF
23//!
24//! The parser below is a little more lenient than the explicit spec and allows for
25//! leading/trailing whitespace around patch markers.
26use crate::ApplyPatchArgs;
27use crate::streaming_parser::StreamingPatchParser;
28#[cfg(test)]
29use codex_utils_absolute_path::test_support::PathBufExt;
30use codex_utils_path_uri::PathUri;
31use codex_utils_path_uri::PathUriParseError;
32use std::path::Path;
33use std::path::PathBuf;
34
35use thiserror::Error;
36
37pub(crate) const BEGIN_PATCH_MARKER: &str = "*** Begin Patch";
38pub(crate) const END_PATCH_MARKER: &str = "*** End Patch";
39pub(crate) const ADD_FILE_MARKER: &str = "*** Add File: ";
40pub(crate) const DELETE_FILE_MARKER: &str = "*** Delete File: ";
41pub(crate) const UPDATE_FILE_MARKER: &str = "*** Update File: ";
42pub(crate) const MOVE_TO_MARKER: &str = "*** Move to: ";
43pub(crate) const EOF_MARKER: &str = "*** End of File";
44pub(crate) const CHANGE_CONTEXT_MARKER: &str = "@@ ";
45pub(crate) const EMPTY_CHANGE_CONTEXT_MARKER: &str = "@@";
46
47/// Currently, the only OpenAI model that knowingly requires lenient parsing is
48/// gpt-4.1. While we could try to require everyone to pass in a strictness
49/// param when invoking apply_patch, it is a pain to thread it through all of
50/// the call sites, so we resign ourselves allowing lenient parsing for all
51/// models. See [`ParseMode::Lenient`] for details on the exceptions we make for
52/// gpt-4.1.
53const PARSE_IN_STRICT_MODE: bool = false;
54
55#[derive(Debug, PartialEq, Error, Clone)]
56pub enum ParseError {
57    #[error("invalid patch: {0}")]
58    InvalidPatchError(String),
59    #[error("invalid hunk at line {line_number}, {message}")]
60    InvalidHunkError { message: String, line_number: usize },
61}
62use ParseError::*;
63
64#[derive(Debug, PartialEq, Clone)]
65#[allow(clippy::enum_variant_names)]
66pub enum Hunk {
67    AddFile {
68        path: PathBuf,
69        contents: String,
70    },
71    DeleteFile {
72        path: PathBuf,
73    },
74    UpdateFile {
75        path: PathBuf,
76        move_path: Option<PathBuf>,
77
78        /// Chunks should be in order, i.e. the `change_context` of one chunk
79        /// should occur later in the file than the previous chunk.
80        chunks: Vec<UpdateFileChunk>,
81    },
82}
83
84impl Hunk {
85    pub fn resolve_path(&self, cwd: &PathUri) -> Result<PathUri, PathUriParseError> {
86        let path = match self {
87            Hunk::UpdateFile { path, .. } => path,
88            Hunk::AddFile { .. } | Hunk::DeleteFile { .. } => self.path(),
89        };
90        cwd.join(&path.to_string_lossy())
91    }
92
93    /// Returns the path affected by this hunk, using the move destination for rename hunks.
94    pub fn path(&self) -> &Path {
95        match self {
96            Hunk::AddFile { path, .. } => path,
97            Hunk::DeleteFile { path } => path,
98            Hunk::UpdateFile {
99                move_path: Some(path),
100                ..
101            } => path,
102            Hunk::UpdateFile {
103                path,
104                move_path: None,
105                ..
106            } => path,
107        }
108    }
109}
110
111#[cfg(test)]
112use Hunk::*;
113
114#[derive(Debug, PartialEq, Clone)]
115pub struct UpdateFileChunk {
116    /// A single line of context used to narrow down the position of the chunk
117    /// (this is usually a class, method, or function definition.)
118    pub change_context: Option<String>,
119
120    /// A contiguous block of lines that should be replaced with `new_lines`.
121    /// `old_lines` must occur strictly after `change_context`.
122    pub old_lines: Vec<String>,
123    pub new_lines: Vec<String>,
124
125    /// If set to true, `old_lines` must occur at the end of the source file.
126    /// (Tolerance around trailing newlines should be encouraged.)
127    pub is_end_of_file: bool,
128}
129
130pub fn parse_patch(patch: &str) -> Result<ApplyPatchArgs, ParseError> {
131    let mode = if PARSE_IN_STRICT_MODE {
132        ParseMode::Strict
133    } else {
134        ParseMode::Lenient
135    };
136    parse_patch_text(patch, mode)
137}
138
139enum ParseMode {
140    /// Parse the patch text argument as is.
141    Strict,
142
143    /// GPT-4.1 is known to formulate the `command` array for the `local_shell`
144    /// tool call for `apply_patch` call using something like the following:
145    ///
146    /// ```json
147    /// [
148    ///   "apply_patch",
149    ///   "<<'EOF'\n*** Begin Patch\n*** Update File: README.md\n@@...\n*** End Patch\nEOF\n",
150    /// ]
151    /// ```
152    ///
153    /// This is a problem because `local_shell` is a bit of a misnomer: the
154    /// `command` is not invoked by passing the arguments to a shell like Bash,
155    /// but are invoked using something akin to `execvpe(3)`.
156    ///
157    /// This is significant in this case because where a shell would interpret
158    /// `<<'EOF'...` as a heredoc and pass the contents via stdin (which is
159    /// fine, as `apply_patch` is specified to read from stdin if no argument is
160    /// passed), `execvpe(3)` interprets the heredoc as a literal string. To get
161    /// the `local_shell` tool to run a command the way shell would, the
162    /// `command` array must be something like:
163    ///
164    /// ```json
165    /// [
166    ///   "bash",
167    ///   "-lc",
168    ///   "apply_patch <<'EOF'\n*** Begin Patch\n*** Update File: README.md\n@@...\n*** End Patch\nEOF\n",
169    /// ]
170    /// ```
171    ///
172    /// In lenient mode, we check if the argument to `apply_patch` starts with
173    /// `<<'EOF'` and ends with `EOF\n`. If so, we strip off these markers,
174    /// trim() the result, and treat what is left as the patch text.
175    Lenient,
176}
177
178fn parse_patch_text(patch: &str, mode: ParseMode) -> Result<ApplyPatchArgs, ParseError> {
179    let lines: Vec<&str> = patch.trim().lines().collect();
180    let patch_lines = match mode {
181        ParseMode::Strict => check_patch_boundaries_strict(&lines)?,
182        ParseMode::Lenient => check_patch_boundaries_lenient(&lines)?,
183    };
184
185    let patch = patch_lines.join("\n");
186    let mut parser = StreamingPatchParser::default();
187    parser.push_delta(&patch)?;
188    let hunks = parser.finish()?;
189    let environment_id = parser.environment_id().map(str::to_owned);
190    Ok(ApplyPatchArgs {
191        hunks,
192        patch,
193        workdir: None,
194        environment_id,
195    })
196}
197
198/// Checks the start and end lines of the patch text for `apply_patch`,
199/// returning an error if they do not match the expected markers.
200fn check_patch_boundaries_strict<'a>(lines: &'a [&'a str]) -> Result<&'a [&'a str], ParseError> {
201    let (first_line, last_line) = match lines {
202        [] => (None, None),
203        [first] => (Some(first), Some(first)),
204        [first, .., last] => (Some(first), Some(last)),
205    };
206    check_start_and_end_lines_strict(first_line, last_line)?;
207    Ok(lines)
208}
209
210/// If we are in lenient mode, we check if the first line starts with `<<EOF`
211/// (possibly quoted) and the last line ends with `EOF`. There must be at least
212/// 4 lines total because the heredoc markers take up 2 lines and the patch text
213/// must have at least 2 lines.
214///
215/// If successful, returns the lines of the patch text that contain the patch
216/// contents, excluding the heredoc markers.
217fn check_patch_boundaries_lenient<'a>(
218    original_lines: &'a [&'a str],
219) -> Result<&'a [&'a str], ParseError> {
220    let original_parse_error = match check_patch_boundaries_strict(original_lines) {
221        Ok(lines) => return Ok(lines),
222        Err(e) => e,
223    };
224
225    match original_lines {
226        [first, .., last] => {
227            if (first == &"<<EOF" || first == &"<<'EOF'" || first == &"<<\"EOF\"")
228                && last.ends_with("EOF")
229                && original_lines.len() >= 4
230            {
231                let inner_lines = &original_lines[1..original_lines.len() - 1];
232                check_patch_boundaries_strict(inner_lines)
233            } else {
234                Err(original_parse_error)
235            }
236        }
237        _ => Err(original_parse_error),
238    }
239}
240
241fn check_start_and_end_lines_strict(
242    first_line: Option<&&str>,
243    last_line: Option<&&str>,
244) -> Result<(), ParseError> {
245    let first_line = first_line.map(|line| line.trim());
246    let last_line = last_line.map(|line| line.trim());
247
248    match (first_line, last_line) {
249        (Some(first), Some(last)) if first == BEGIN_PATCH_MARKER && last == END_PATCH_MARKER => {
250            Ok(())
251        }
252        (Some(first), _) if first != BEGIN_PATCH_MARKER => Err(InvalidPatchError(String::from(
253            "The first line of the patch must be '*** Begin Patch'",
254        ))),
255        _ => Err(InvalidPatchError(String::from(
256            "The last line of the patch must be '*** End Patch'",
257        ))),
258    }
259}
260
261#[test]
262fn test_parse_patch() {
263    assert_eq!(
264        parse_patch_text("bad", ParseMode::Strict),
265        Err(InvalidPatchError(
266            "The first line of the patch must be '*** Begin Patch'".to_string()
267        ))
268    );
269    assert_eq!(
270        parse_patch_text("*** Begin Patch\nbad", ParseMode::Strict),
271        Err(InvalidPatchError(
272            "The last line of the patch must be '*** End Patch'".to_string()
273        ))
274    );
275
276    assert_eq!(
277        parse_patch_text(
278            concat!(
279                "*** Begin Patch",
280                " ",
281                "\n*** Add File: foo\n+hi\n",
282                " ",
283                "*** End Patch"
284            ),
285            ParseMode::Strict
286        )
287        .unwrap()
288        .hunks,
289        vec![AddFile {
290            path: PathBuf::from("foo"),
291            contents: "hi\n".to_string()
292        }]
293    );
294    assert_eq!(
295        parse_patch_text(
296            "*** Begin Patch\n\
297             *** Update File: test.py\n\
298             *** End Patch",
299            ParseMode::Strict
300        ),
301        Err(InvalidHunkError {
302            message: "Update file hunk for path 'test.py' is empty".to_string(),
303            line_number: 2,
304        })
305    );
306    assert_eq!(
307        parse_patch_text(
308            "*** Begin Patch\n\
309             *** End Patch",
310            ParseMode::Strict
311        )
312        .unwrap()
313        .hunks,
314        Vec::new()
315    );
316    assert_eq!(
317        parse_patch_text(
318            "*** Begin Patch\n\
319             *** Add File: path/add.py\n\
320             +abc\n\
321             +def\n\
322             *** Delete File: path/delete.py\n\
323             *** Update File: path/update.py\n\
324             *** Move to: path/update2.py\n\
325             @@ def f():\n\
326             -    pass\n\
327             +    return 123\n\
328             *** End Patch",
329            ParseMode::Strict
330        )
331        .unwrap()
332        .hunks,
333        vec![
334            AddFile {
335                path: PathBuf::from("path/add.py"),
336                contents: "abc\ndef\n".to_string()
337            },
338            DeleteFile {
339                path: PathBuf::from("path/delete.py")
340            },
341            UpdateFile {
342                path: PathBuf::from("path/update.py"),
343                move_path: Some(PathBuf::from("path/update2.py")),
344                chunks: vec![UpdateFileChunk {
345                    change_context: Some("def f():".to_string()),
346                    old_lines: vec!["    pass".to_string()],
347                    new_lines: vec!["    return 123".to_string()],
348                    is_end_of_file: false
349                }]
350            }
351        ]
352    );
353    // Update hunk followed by another hunk (Add File).
354    assert_eq!(
355        parse_patch_text(
356            "*** Begin Patch\n\
357             *** Update File: file.py\n\
358             @@\n\
359             +line\n\
360             *** Add File: other.py\n\
361             +content\n\
362             *** End Patch",
363            ParseMode::Strict
364        )
365        .unwrap()
366        .hunks,
367        vec![
368            UpdateFile {
369                path: PathBuf::from("file.py"),
370                move_path: None,
371                chunks: vec![UpdateFileChunk {
372                    change_context: None,
373                    old_lines: vec![],
374                    new_lines: vec!["line".to_string()],
375                    is_end_of_file: false
376                }],
377            },
378            AddFile {
379                path: PathBuf::from("other.py"),
380                contents: "content\n".to_string()
381            }
382        ]
383    );
384
385    // Update hunk without an explicit @@ header for the first chunk should parse.
386    // Use a raw string to preserve the leading space diff marker on the context line.
387    assert_eq!(
388        parse_patch_text(
389            r#"*** Begin Patch
390*** Update File: file2.py
391 import foo
392+bar
393*** End Patch"#,
394            ParseMode::Strict
395        )
396        .unwrap()
397        .hunks,
398        vec![UpdateFile {
399            path: PathBuf::from("file2.py"),
400            move_path: None,
401            chunks: vec![UpdateFileChunk {
402                change_context: None,
403                old_lines: vec!["import foo".to_string()],
404                new_lines: vec!["import foo".to_string(), "bar".to_string()],
405                is_end_of_file: false,
406            }],
407        }]
408    );
409}
410
411#[test]
412fn test_parse_patch_preserves_end_of_file_marker() {
413    let patch =
414        "*** Begin Patch\n*** Update File: file.txt\n@@\n+quux\n*** End of File\n\n*** End Patch";
415    assert_eq!(
416        parse_patch(patch),
417        Ok(ApplyPatchArgs {
418            hunks: vec![UpdateFile {
419                path: PathBuf::from("file.txt"),
420                move_path: None,
421                chunks: vec![UpdateFileChunk {
422                    change_context: None,
423                    old_lines: Vec::new(),
424                    new_lines: vec!["quux".to_string()],
425                    is_end_of_file: true,
426                }],
427            }],
428            patch: patch.to_string(),
429            workdir: None,
430            environment_id: None,
431        })
432    );
433}
434
435#[test]
436fn test_parse_patch_accepts_relative_and_absolute_hunk_paths() {
437    let dir = tempfile::tempdir().unwrap();
438    let absolute_delete = dir.path().join("absolute-delete.py").abs();
439    let absolute_update = dir.path().join("absolute-update.py").abs();
440    let patch_text = format!(
441        r#"*** Begin Patch
442*** Add File: relative-add.py
443+content
444*** Delete File: {}
445*** Update File: {}
446@@
447-old
448+new
449*** End Patch"#,
450        absolute_delete.display(),
451        absolute_update.display()
452    );
453
454    assert_eq!(
455        parse_patch_text(&patch_text, ParseMode::Strict)
456            .unwrap()
457            .hunks,
458        vec![
459            AddFile {
460                path: PathBuf::from("relative-add.py"),
461                contents: "content\n".to_string()
462            },
463            DeleteFile {
464                path: absolute_delete.to_path_buf()
465            },
466            UpdateFile {
467                path: absolute_update.to_path_buf(),
468                move_path: None,
469                chunks: vec![UpdateFileChunk {
470                    change_context: None,
471                    old_lines: vec!["old".to_string()],
472                    new_lines: vec!["new".to_string()],
473                    is_end_of_file: false
474                }]
475            },
476        ]
477    );
478}
479
480#[test]
481fn test_hunk_resolve_path_accepts_relative_and_absolute_paths() {
482    let cwd_dir = tempfile::tempdir().unwrap();
483    let cwd = PathUri::from_host_native_path(cwd_dir.path()).unwrap();
484    let absolute_dir = tempfile::tempdir().unwrap();
485    let absolute_add = absolute_dir.path().join("absolute-add.py").abs();
486    let absolute_delete = absolute_dir.path().join("absolute-delete.py").abs();
487    let absolute_update = absolute_dir.path().join("absolute-update.py").abs();
488
489    for (hunk, expected_path) in [
490        (
491            AddFile {
492                path: PathBuf::from("relative-add.py"),
493                contents: String::new(),
494            },
495            cwd.join("relative-add.py").unwrap(),
496        ),
497        (
498            DeleteFile {
499                path: PathBuf::from("relative-delete.py"),
500            },
501            cwd.join("relative-delete.py").unwrap(),
502        ),
503        (
504            UpdateFile {
505                path: PathBuf::from("relative-update.py"),
506                move_path: None,
507                chunks: Vec::new(),
508            },
509            cwd.join("relative-update.py").unwrap(),
510        ),
511        (
512            AddFile {
513                path: absolute_add.to_path_buf(),
514                contents: String::new(),
515            },
516            PathUri::from_abs_path(&absolute_add),
517        ),
518        (
519            DeleteFile {
520                path: absolute_delete.to_path_buf(),
521            },
522            PathUri::from_abs_path(&absolute_delete),
523        ),
524        (
525            UpdateFile {
526                path: absolute_update.to_path_buf(),
527                move_path: None,
528                chunks: Vec::new(),
529            },
530            PathUri::from_abs_path(&absolute_update),
531        ),
532    ] {
533        assert_eq!(hunk.resolve_path(&cwd), Ok(expected_path));
534    }
535}
536
537#[test]
538fn test_parse_patch_lenient() {
539    let patch_text = r#"*** Begin Patch
540*** Update File: file2.py
541 import foo
542+bar
543*** End Patch"#;
544    let expected_patch = vec![UpdateFile {
545        path: PathBuf::from("file2.py"),
546        move_path: None,
547        chunks: vec![UpdateFileChunk {
548            change_context: None,
549            old_lines: vec!["import foo".to_string()],
550            new_lines: vec!["import foo".to_string(), "bar".to_string()],
551            is_end_of_file: false,
552        }],
553    }];
554    let expected_error =
555        InvalidPatchError("The first line of the patch must be '*** Begin Patch'".to_string());
556
557    let patch_text_in_heredoc = format!("<<EOF\n{patch_text}\nEOF\n");
558    assert_eq!(
559        parse_patch_text(&patch_text_in_heredoc, ParseMode::Strict),
560        Err(expected_error.clone())
561    );
562    assert_eq!(
563        parse_patch_text(&patch_text_in_heredoc, ParseMode::Lenient),
564        Ok(ApplyPatchArgs {
565            hunks: expected_patch.clone(),
566            patch: patch_text.to_string(),
567            workdir: None,
568            environment_id: None,
569        })
570    );
571
572    let patch_text_in_single_quoted_heredoc = format!("<<'EOF'\n{patch_text}\nEOF\n");
573    assert_eq!(
574        parse_patch_text(&patch_text_in_single_quoted_heredoc, ParseMode::Strict),
575        Err(expected_error.clone())
576    );
577    assert_eq!(
578        parse_patch_text(&patch_text_in_single_quoted_heredoc, ParseMode::Lenient),
579        Ok(ApplyPatchArgs {
580            hunks: expected_patch.clone(),
581            patch: patch_text.to_string(),
582            workdir: None,
583            environment_id: None,
584        })
585    );
586
587    let patch_text_in_double_quoted_heredoc = format!("<<\"EOF\"\n{patch_text}\nEOF\n");
588    assert_eq!(
589        parse_patch_text(&patch_text_in_double_quoted_heredoc, ParseMode::Strict),
590        Err(expected_error.clone())
591    );
592    assert_eq!(
593        parse_patch_text(&patch_text_in_double_quoted_heredoc, ParseMode::Lenient),
594        Ok(ApplyPatchArgs {
595            hunks: expected_patch,
596            patch: patch_text.to_string(),
597            workdir: None,
598            environment_id: None,
599        })
600    );
601
602    let patch_text_in_mismatched_quotes_heredoc = format!("<<\"EOF'\n{patch_text}\nEOF\n");
603    assert_eq!(
604        parse_patch_text(&patch_text_in_mismatched_quotes_heredoc, ParseMode::Strict),
605        Err(expected_error.clone())
606    );
607    assert_eq!(
608        parse_patch_text(&patch_text_in_mismatched_quotes_heredoc, ParseMode::Lenient),
609        Err(expected_error.clone())
610    );
611
612    let patch_text_with_missing_closing_heredoc =
613        "<<EOF\n*** Begin Patch\n*** Update File: file2.py\nEOF\n".to_string();
614    assert_eq!(
615        parse_patch_text(&patch_text_with_missing_closing_heredoc, ParseMode::Strict),
616        Err(expected_error)
617    );
618    assert_eq!(
619        parse_patch_text(&patch_text_with_missing_closing_heredoc, ParseMode::Lenient),
620        Err(InvalidPatchError(
621            "The last line of the patch must be '*** End Patch'".to_string()
622        ))
623    );
624}
625
626#[test]
627fn test_parse_patch_environment_id_preamble() {
628    assert_eq!(
629        parse_patch_text(
630            "*** Begin Patch\n\
631             *** Environment ID: remote\n\
632             *** Add File: hello.txt\n\
633             +hello\n\
634             *** End Patch",
635            ParseMode::Strict
636        ),
637        Ok(ApplyPatchArgs {
638            hunks: vec![AddFile {
639                path: PathBuf::from("hello.txt"),
640                contents: "hello\n".to_string(),
641            }],
642            patch: "*** Begin Patch\n*** Environment ID: remote\n*** Add File: hello.txt\n+hello\n*** End Patch".to_string(),
643            workdir: None,
644            environment_id: Some("remote".to_string()),
645        })
646    );
647
648    assert_eq!(
649        parse_patch_text(
650            "*** Begin Patch\n\
651             *** Environment ID:   \n\
652             *** Add File: hello.txt\n\
653             +hello\n\
654             *** End Patch",
655            ParseMode::Strict
656        ),
657        Err(InvalidPatchError(
658            "apply_patch environment_id cannot be empty".to_string()
659        ))
660    );
661}
codex_apply_patch/parser.rs

codex_apply_patch/
parser.rs
