agents_tools/
apply_diff.rs

1use thiserror::Error;
2
3const END_PATCH: &str = "*** End Patch";
4const END_FILE: &str = "*** End of File";
5const UPDATE_FILE: &str = "*** Update File:";
6const DELETE_FILE: &str = "*** Delete File:";
7const ADD_FILE: &str = "*** Add File:";
8
9const END_SECTION_MARKERS: [&str; 5] = [END_PATCH, UPDATE_FILE, DELETE_FILE, ADD_FILE, END_FILE];
10const SECTION_TERMINATORS: [&str; 4] = [END_PATCH, UPDATE_FILE, DELETE_FILE, ADD_FILE];
11
12/// Selects how an in-memory diff body is interpreted.
13///
14/// [`Update`](Self::Update) patches existing text using context and edit lines.
15/// [`Create`](Self::Create) builds new text exclusively from `+` lines.
16#[derive(Debug, Default, Clone, Copy, PartialEq, Eq)]
17pub enum ApplyDiffMode {
18    /// Patch existing content using context, insertion, deletion, and anchor lines.
19    #[default]
20    Update,
21    /// Build new file content from lines prefixed with `+`.
22    Create,
23}
24
25/// An error produced when a patch cannot be parsed or applied safely.
26///
27/// The message identifies the first invalid anchor, context, content line,
28/// envelope marker, root, or path. Filesystem errors scoped to an individual
29/// logical file are reported as `FailedFile` entries when the `filesystem`
30/// feature is enabled.
31#[derive(Debug, Clone, PartialEq, Eq, Error)]
32#[error("{message}")]
33pub struct ApplyDiffError {
34    message: String,
35}
36
37impl ApplyDiffError {
38    pub(crate) fn new(message: impl Into<String>) -> Self {
39        Self {
40            message: message.into(),
41        }
42    }
43
44    /// Returns the human-readable error message without allocating.
45    pub fn message(&self) -> &str {
46        &self.message
47    }
48}
49
50/// Applies a complete update body to in-memory text.
51///
52/// A body can contain multiple `@@` sections. Within each section, context
53/// lines begin with a space, removals with `-`, and insertions with `+`.
54/// Uniform CRLF input remains CRLF; LF and trailing-newline behavior are also
55/// preserved.
56///
57/// # Errors
58///
59/// Returns [`ApplyDiffError`] when an anchor or context cannot be found, a body
60/// line has an invalid prefix, or the sections are malformed.
61///
62/// # Example
63///
64/// ```
65/// use agents_tools::apply_diff_to_text;
66///
67/// let result = apply_diff_to_text(
68///     "alpha\nbeta\ngamma\n",
69///     "@@ alpha\n-beta\n+BETA\n gamma",
70/// )?;
71/// assert_eq!(result, "alpha\nBETA\ngamma\n");
72/// # Ok::<(), agents_tools::ApplyDiffError>(())
73/// ```
74pub fn apply_diff_to_text(input: &str, diff: &str) -> Result<String, ApplyDiffError> {
75    apply_diff_to_text_with_mode(input, diff, ApplyDiffMode::Update)
76}
77
78/// Applies a diff body to `input` using the requested mode.
79///
80/// Update mode accepts floating sections made of `@@` anchors and lines prefixed
81/// with ` `, `+`, or `-`. Create mode requires every content line to start with
82/// `+`. Existing trailing newlines are preserved by update mode.
83///
84/// # Errors
85///
86/// Returns [`ApplyDiffError`] when the body is invalid for `mode` or cannot be
87/// matched against `input`.
88///
89/// # Example
90///
91/// ```
92/// use agents_tools::{ApplyDiffMode, apply_diff_to_text_with_mode};
93///
94/// let created = apply_diff_to_text_with_mode(
95///     "",
96///     "+first\n+second\n+",
97///     ApplyDiffMode::Create,
98/// )?;
99/// assert_eq!(created, "first\nsecond\n");
100/// # Ok::<(), agents_tools::ApplyDiffError>(())
101/// ```
102pub fn apply_diff_to_text_with_mode(
103    input: &str,
104    diff: &str,
105    mode: ApplyDiffMode,
106) -> Result<String, ApplyDiffError> {
107    let diff_lines = normalize_diff_lines(diff);
108    let uses_crlf = mode == ApplyDiffMode::Update && has_uniform_crlf(input);
109    let normalized_input = uses_crlf.then(|| input.replace("\r\n", "\n"));
110    let input = normalized_input.as_deref().unwrap_or(input);
111    let output = match mode {
112        ApplyDiffMode::Update => {
113            let chunks = parse_update_diff(diff_lines, input)?;
114            apply_chunks(input, &chunks)
115        }
116        ApplyDiffMode::Create => parse_create_diff(diff_lines),
117    }?;
118    Ok(if uses_crlf {
119        output.replace('\n', "\r\n")
120    } else {
121        output
122    })
123}
124
125fn has_uniform_crlf(input: &str) -> bool {
126    let bytes = input.as_bytes();
127    let newline_count = bytes.iter().filter(|byte| **byte == b'\n').count();
128    newline_count > 0 && bytes.windows(2).filter(|pair| pair == b"\r\n").count() == newline_count
129}
130
131#[derive(Debug)]
132struct Chunk {
133    orig_index: usize,
134    del_lines: Vec<String>,
135    ins_lines: Vec<String>,
136}
137
138struct ParserState {
139    lines: Vec<String>,
140    index: usize,
141    fuzz: usize,
142}
143
144fn normalize_diff_lines(diff: &str) -> Vec<String> {
145    let bytes = diff.as_bytes();
146    let mut lines = Vec::new();
147    let mut start = 0;
148
149    for (index, byte) in bytes.iter().enumerate() {
150        if *byte != b'\n' {
151            continue;
152        }
153
154        let mut end = index;
155        if end > start && bytes[end - 1] == b'\r' {
156            end -= 1;
157        }
158
159        let mut line = &diff[start..end];
160        if let Some(without_cr) = line.strip_suffix('\r') {
161            line = without_cr;
162        }
163        lines.push(line.to_owned());
164        start = index + 1;
165    }
166
167    let mut final_line = &diff[start..];
168    if let Some(without_cr) = final_line.strip_suffix('\r') {
169        final_line = without_cr;
170    }
171    lines.push(final_line.to_owned());
172
173    if lines.last().is_some_and(String::is_empty) {
174        lines.pop();
175    }
176    lines
177}
178
179fn is_done(state: &ParserState, prefixes: &[&str]) -> bool {
180    state.index >= state.lines.len()
181        || prefixes
182            .iter()
183            .any(|prefix| state.lines[state.index].starts_with(prefix))
184}
185
186fn read_str(state: &mut ParserState, prefix: &str) -> Option<String> {
187    let suffix = state
188        .lines
189        .get(state.index)
190        .and_then(|line| line.strip_prefix(prefix))?
191        .to_owned();
192    state.index += 1;
193    Some(suffix)
194}
195
196fn parse_create_diff(mut lines: Vec<String>) -> Result<String, ApplyDiffError> {
197    lines.push(END_PATCH.to_owned());
198    let mut parser = ParserState {
199        lines,
200        index: 0,
201        fuzz: 0,
202    };
203    let mut output = Vec::new();
204
205    while !is_done(&parser, &SECTION_TERMINATORS) {
206        let line = &parser.lines[parser.index];
207        parser.index += 1;
208        let Some(content) = line.strip_prefix('+') else {
209            return Err(ApplyDiffError::new(format!(
210                "Invalid Add File Line: {line}"
211            )));
212        };
213        output.push(content);
214    }
215
216    Ok(output.join("\n"))
217}
218
219fn parse_update_diff(mut lines: Vec<String>, input: &str) -> Result<Vec<Chunk>, ApplyDiffError> {
220    lines.push(END_PATCH.to_owned());
221    let mut parser = ParserState {
222        lines,
223        index: 0,
224        fuzz: 0,
225    };
226    let input_lines: Vec<&str> = input.split('\n').collect();
227    let mut chunks = Vec::new();
228    let mut cursor = 0;
229
230    while !is_done(&parser, &END_SECTION_MARKERS) {
231        let (anchors, anchor_count) = read_anchors(&mut parser);
232        if anchor_count == 0 && cursor != 0 {
233            let line = parser
234                .lines
235                .get(parser.index)
236                .map_or("undefined", String::as_str);
237            return Err(ApplyDiffError::new(format!("Invalid Line:\n{line}")));
238        }
239
240        let require_anchor_match = anchor_count > 1;
241        for (index, anchor) in anchors.iter().enumerate() {
242            cursor = advance_cursor_to_anchor(
243                anchor,
244                &input_lines,
245                cursor,
246                &mut parser,
247                require_anchor_match,
248                index > 0,
249            )?;
250        }
251
252        let section = read_section(&parser.lines, parser.index)?;
253        let next_context_text = section.next_context.join("\n");
254        let (new_index, fuzz) =
255            find_context(&input_lines, &section.next_context, cursor, section.eof);
256        let Some(new_index) = new_index else {
257            let kind = if section.eof {
258                "Invalid EOF Context"
259            } else {
260                "Invalid Context"
261            };
262            return Err(ApplyDiffError::new(format!(
263                "{kind} {cursor}:\n{next_context_text}"
264            )));
265        };
266
267        parser.fuzz += fuzz;
268        chunks.extend(section.chunks.into_iter().map(|mut chunk| {
269            chunk.orig_index += new_index;
270            chunk
271        }));
272        cursor = new_index + section.next_context.len();
273        parser.index = section.end_index;
274    }
275
276    Ok(chunks)
277}
278
279fn read_anchors(parser: &mut ParserState) -> (Vec<String>, usize) {
280    let mut anchors = Vec::new();
281    let mut anchor_count = 0;
282
283    loop {
284        let start_index = parser.index;
285        let anchor = read_str(parser, "@@ ");
286        let mut consumed = parser.index != start_index;
287
288        if !consumed
289            && parser
290                .lines
291                .get(parser.index)
292                .is_some_and(|line| line == "@@")
293        {
294            parser.index += 1;
295            consumed = true;
296        }
297        if !consumed {
298            break;
299        }
300
301        anchor_count += 1;
302        if let Some(anchor) = anchor.filter(|anchor| !trim_diff_whitespace(anchor).is_empty()) {
303            anchors.push(anchor);
304        }
305    }
306
307    (anchors, anchor_count)
308}
309
310fn advance_cursor_to_anchor(
311    anchor: &str,
312    input_lines: &[&str],
313    mut cursor: usize,
314    parser: &mut ParserState,
315    require_match: bool,
316    force_forward_search: bool,
317) -> Result<usize, ApplyDiffError> {
318    let mut found = false;
319
320    if !force_forward_search && input_lines[..cursor].contains(&anchor) {
321        found = true;
322    } else if let Some(index) = input_lines[cursor..]
323        .iter()
324        .position(|line| *line == anchor)
325    {
326        cursor += index + 1;
327        found = true;
328    }
329
330    if !found {
331        if !force_forward_search
332            && input_lines[..cursor]
333                .iter()
334                .any(|line| trim_diff_whitespace(line) == trim_diff_whitespace(anchor))
335        {
336            found = true;
337        } else if let Some(index) = input_lines[cursor..]
338            .iter()
339            .position(|line| trim_diff_whitespace(line) == trim_diff_whitespace(anchor))
340        {
341            cursor += index + 1;
342            parser.fuzz += 1;
343            found = true;
344        }
345    }
346
347    if require_match && !found {
348        return Err(ApplyDiffError::new(format!(
349            "Invalid Anchor {cursor}:\n{anchor}"
350        )));
351    }
352
353    Ok(cursor)
354}
355
356#[derive(Debug, Clone, Copy, PartialEq, Eq)]
357enum LineMode {
358    Keep,
359    Add,
360    Delete,
361}
362
363struct Section {
364    next_context: Vec<String>,
365    chunks: Vec<Chunk>,
366    end_index: usize,
367    eof: bool,
368}
369
370fn read_section(lines: &[String], start_index: usize) -> Result<Section, ApplyDiffError> {
371    let mut context = Vec::new();
372    let mut del_lines = Vec::new();
373    let mut ins_lines = Vec::new();
374    let mut chunks = Vec::new();
375    let mut mode = LineMode::Keep;
376    let mut index = start_index;
377    let orig_index = index;
378
379    while index < lines.len() {
380        let raw = &lines[index];
381        if raw.starts_with("@@")
382            || raw.starts_with(END_PATCH)
383            || raw.starts_with(UPDATE_FILE)
384            || raw.starts_with(DELETE_FILE)
385            || raw.starts_with(ADD_FILE)
386            || raw.starts_with(END_FILE)
387        {
388            break;
389        }
390        if raw == "***" {
391            break;
392        }
393        if raw.starts_with("***") {
394            return Err(ApplyDiffError::new(format!("Invalid Line: {raw}")));
395        }
396
397        index += 1;
398        let last_mode = mode;
399        let line = if raw.is_empty() { " " } else { raw.as_str() };
400        let (next_mode, content) = if let Some(content) = line.strip_prefix('+') {
401            (LineMode::Add, content)
402        } else if let Some(content) = line.strip_prefix('-') {
403            (LineMode::Delete, content)
404        } else if let Some(content) = line.strip_prefix(' ') {
405            (LineMode::Keep, content)
406        } else {
407            return Err(ApplyDiffError::new(format!("Invalid Line: {line}")));
408        };
409        mode = next_mode;
410
411        if mode == LineMode::Keep
412            && last_mode != mode
413            && (!ins_lines.is_empty() || !del_lines.is_empty())
414        {
415            chunks.push(Chunk {
416                orig_index: context.len() - del_lines.len(),
417                del_lines: std::mem::take(&mut del_lines),
418                ins_lines: std::mem::take(&mut ins_lines),
419            });
420        }
421
422        match mode {
423            LineMode::Delete => {
424                del_lines.push(content.to_owned());
425                context.push(content.to_owned());
426            }
427            LineMode::Add => ins_lines.push(content.to_owned()),
428            LineMode::Keep => context.push(content.to_owned()),
429        }
430    }
431
432    if !ins_lines.is_empty() || !del_lines.is_empty() {
433        chunks.push(Chunk {
434            orig_index: context.len() - del_lines.len(),
435            del_lines,
436            ins_lines,
437        });
438    }
439
440    if lines.get(index).is_some_and(|line| line == END_FILE) {
441        return Ok(Section {
442            next_context: context,
443            chunks,
444            end_index: index + 1,
445            eof: true,
446        });
447    }
448
449    if index == orig_index {
450        let line = lines.get(index).map_or("undefined", String::as_str);
451        return Err(ApplyDiffError::new(format!(
452            "Nothing in this section - index={index} {line}"
453        )));
454    }
455
456    Ok(Section {
457        next_context: context,
458        chunks,
459        end_index: index,
460        eof: false,
461    })
462}
463
464fn find_context(
465    lines: &[&str],
466    context: &[String],
467    start: usize,
468    eof: bool,
469) -> (Option<usize>, usize) {
470    if eof {
471        let end_start = lines.len().saturating_sub(context.len());
472        let end_match = find_context_core(lines, context, end_start);
473        if end_match.0.is_some() {
474            return end_match;
475        }
476
477        let (new_index, fuzz) = find_context_core(lines, context, start);
478        return (new_index, fuzz + 10_000);
479    }
480
481    find_context_core(lines, context, start)
482}
483
484fn find_context_core(lines: &[&str], context: &[String], start: usize) -> (Option<usize>, usize) {
485    if context.is_empty() {
486        return (Some(start), 0);
487    }
488
489    for index in start..lines.len() {
490        if equals_slice(lines, context, index, |value| value) {
491            return (Some(index), 0);
492        }
493    }
494    for index in start..lines.len() {
495        if equals_slice(lines, context, index, trim_diff_whitespace_end) {
496            return (Some(index), 1);
497        }
498    }
499    for index in start..lines.len() {
500        if equals_slice(lines, context, index, trim_diff_whitespace) {
501            return (Some(index), 100);
502        }
503    }
504
505    (None, 0)
506}
507
508fn equals_slice<'a, F>(source: &'a [&'a str], target: &'a [String], start: usize, map: F) -> bool
509where
510    F: Fn(&'a str) -> &'a str,
511{
512    if start + target.len() > source.len() {
513        return false;
514    }
515
516    source[start..start + target.len()]
517        .iter()
518        .copied()
519        .zip(target.iter().map(String::as_str))
520        .all(|(source, target)| map(source) == map(target))
521}
522
523fn trim_diff_whitespace(value: &str) -> &str {
524    value.trim_matches(is_diff_whitespace)
525}
526
527fn trim_diff_whitespace_end(value: &str) -> &str {
528    value.trim_end_matches(is_diff_whitespace)
529}
530
531fn is_diff_whitespace(character: char) -> bool {
532    matches!(
533        character,
534        '\u{0009}'
535            | '\u{000A}'
536            | '\u{000B}'
537            | '\u{000C}'
538            | '\u{000D}'
539            | '\u{0020}'
540            | '\u{00A0}'
541            | '\u{1680}'
542            | '\u{2000}'
543            ..='\u{200A}'
544                | '\u{2028}'
545                | '\u{2029}'
546                | '\u{202F}'
547                | '\u{205F}'
548                | '\u{3000}'
549                | '\u{FEFF}'
550    )
551}
552
553fn apply_chunks(input: &str, chunks: &[Chunk]) -> Result<String, ApplyDiffError> {
554    let orig_lines: Vec<&str> = input.split('\n').collect();
555    let mut dest_lines: Vec<&str> = Vec::new();
556    let mut orig_index = 0;
557
558    for chunk in chunks {
559        if chunk.orig_index > orig_lines.len() {
560            return Err(ApplyDiffError::new(format!(
561                "applyDiff: chunk.origIndex {} > input length {}",
562                chunk.orig_index,
563                orig_lines.len()
564            )));
565        }
566        if orig_index > chunk.orig_index {
567            return Err(ApplyDiffError::new(format!(
568                "applyDiff: overlapping chunk at {} (cursor {orig_index})",
569                chunk.orig_index
570            )));
571        }
572
573        dest_lines.extend_from_slice(&orig_lines[orig_index..chunk.orig_index]);
574        orig_index = chunk.orig_index;
575        dest_lines.extend(chunk.ins_lines.iter().map(String::as_str));
576        orig_index += chunk.del_lines.len();
577    }
578
579    dest_lines.extend_from_slice(&orig_lines[orig_index..]);
580    Ok(dest_lines.join("\n"))
581}
agents_tools/apply_diff.rs

agents_tools/
apply_diff.rs
