agents-tools 0.1.0

use thiserror::Error;

const END_PATCH: &str = "*** End Patch";
const END_FILE: &str = "*** End of File";
const UPDATE_FILE: &str = "*** Update File:";
const DELETE_FILE: &str = "*** Delete File:";
const ADD_FILE: &str = "*** Add File:";

const END_SECTION_MARKERS: [&str; 5] = [END_PATCH, UPDATE_FILE, DELETE_FILE, ADD_FILE, END_FILE];
const SECTION_TERMINATORS: [&str; 4] = [END_PATCH, UPDATE_FILE, DELETE_FILE, ADD_FILE];

/// Selects how an in-memory diff body is interpreted.
///
/// [`Update`](Self::Update) patches existing text using context and edit lines.
/// [`Create`](Self::Create) builds new text exclusively from `+` lines.
#[derive(Debug, Default, Clone, Copy, PartialEq, Eq)]
pub enum ApplyDiffMode {
    /// Patch existing content using context, insertion, deletion, and anchor lines.
    #[default]
    Update,
    /// Build new file content from lines prefixed with `+`.
    Create,
}

/// An error produced when a patch cannot be parsed or applied safely.
///
/// The message identifies the first invalid anchor, context, content line,
/// envelope marker, root, or path. Filesystem errors scoped to an individual
/// logical file are reported as `FailedFile` entries when the `filesystem`
/// feature is enabled.
#[derive(Debug, Clone, PartialEq, Eq, Error)]
#[error("{message}")]
pub struct ApplyDiffError {
    message: String,
}

impl ApplyDiffError {
    pub(crate) fn new(message: impl Into<String>) -> Self {
        Self {
            message: message.into(),
        }
    }

    /// Returns the human-readable error message without allocating.
    pub fn message(&self) -> &str {
        &self.message
    }
}

/// Applies a complete update body to in-memory text.
///
/// A body can contain multiple `@@` sections. Within each section, context
/// lines begin with a space, removals with `-`, and insertions with `+`.
/// Uniform CRLF input remains CRLF; LF and trailing-newline behavior are also
/// preserved.
///
/// # Errors
///
/// Returns [`ApplyDiffError`] when an anchor or context cannot be found, a body
/// line has an invalid prefix, or the sections are malformed.
///
/// # Example
///
/// ```
/// use agents_tools::apply_diff_to_text;
///
/// let result = apply_diff_to_text(
///     "alpha\nbeta\ngamma\n",
///     "@@ alpha\n-beta\n+BETA\n gamma",
/// )?;
/// assert_eq!(result, "alpha\nBETA\ngamma\n");
/// # Ok::<(), agents_tools::ApplyDiffError>(())
/// ```
pub fn apply_diff_to_text(input: &str, diff: &str) -> Result<String, ApplyDiffError> {
    apply_diff_to_text_with_mode(input, diff, ApplyDiffMode::Update)
}

/// Applies a diff body to `input` using the requested mode.
///
/// Update mode accepts floating sections made of `@@` anchors and lines prefixed
/// with ` `, `+`, or `-`. Create mode requires every content line to start with
/// `+`. Existing trailing newlines are preserved by update mode.
///
/// # Errors
///
/// Returns [`ApplyDiffError`] when the body is invalid for `mode` or cannot be
/// matched against `input`.
///
/// # Example
///
/// ```
/// use agents_tools::{ApplyDiffMode, apply_diff_to_text_with_mode};
///
/// let created = apply_diff_to_text_with_mode(
///     "",
///     "+first\n+second\n+",
///     ApplyDiffMode::Create,
/// )?;
/// assert_eq!(created, "first\nsecond\n");
/// # Ok::<(), agents_tools::ApplyDiffError>(())
/// ```
pub fn apply_diff_to_text_with_mode(
    input: &str,
    diff: &str,
    mode: ApplyDiffMode,
) -> Result<String, ApplyDiffError> {
    let diff_lines = normalize_diff_lines(diff);
    let uses_crlf = mode == ApplyDiffMode::Update && has_uniform_crlf(input);
    let normalized_input = uses_crlf.then(|| input.replace("\r\n", "\n"));
    let input = normalized_input.as_deref().unwrap_or(input);
    let output = match mode {
        ApplyDiffMode::Update => {
            let chunks = parse_update_diff(diff_lines, input)?;
            apply_chunks(input, &chunks)
        }
        ApplyDiffMode::Create => parse_create_diff(diff_lines),
    }?;
    Ok(if uses_crlf {
        output.replace('\n', "\r\n")
    } else {
        output
    })
}

fn has_uniform_crlf(input: &str) -> bool {
    let bytes = input.as_bytes();
    let newline_count = bytes.iter().filter(|byte| **byte == b'\n').count();
    newline_count > 0 && bytes.windows(2).filter(|pair| pair == b"\r\n").count() == newline_count
}

#[derive(Debug)]
struct Chunk {
    orig_index: usize,
    del_lines: Vec<String>,
    ins_lines: Vec<String>,
}

struct ParserState {
    lines: Vec<String>,
    index: usize,
    fuzz: usize,
}

fn normalize_diff_lines(diff: &str) -> Vec<String> {
    let bytes = diff.as_bytes();
    let mut lines = Vec::new();
    let mut start = 0;

    for (index, byte) in bytes.iter().enumerate() {
        if *byte != b'\n' {
            continue;
        }

        let mut end = index;
        if end > start && bytes[end - 1] == b'\r' {
            end -= 1;
        }

        let mut line = &diff[start..end];
        if let Some(without_cr) = line.strip_suffix('\r') {
            line = without_cr;
        }
        lines.push(line.to_owned());
        start = index + 1;
    }

    let mut final_line = &diff[start..];
    if let Some(without_cr) = final_line.strip_suffix('\r') {
        final_line = without_cr;
    }
    lines.push(final_line.to_owned());

    if lines.last().is_some_and(String::is_empty) {
        lines.pop();
    }
    lines
}

fn is_done(state: &ParserState, prefixes: &[&str]) -> bool {
    state.index >= state.lines.len()
        || prefixes
            .iter()
            .any(|prefix| state.lines[state.index].starts_with(prefix))
}

fn read_str(state: &mut ParserState, prefix: &str) -> Option<String> {
    let suffix = state
        .lines
        .get(state.index)
        .and_then(|line| line.strip_prefix(prefix))?
        .to_owned();
    state.index += 1;
    Some(suffix)
}

fn parse_create_diff(mut lines: Vec<String>) -> Result<String, ApplyDiffError> {
    lines.push(END_PATCH.to_owned());
    let mut parser = ParserState {
        lines,
        index: 0,
        fuzz: 0,
    };
    let mut output = Vec::new();

    while !is_done(&parser, &SECTION_TERMINATORS) {
        let line = &parser.lines[parser.index];
        parser.index += 1;
        let Some(content) = line.strip_prefix('+') else {
            return Err(ApplyDiffError::new(format!(
                "Invalid Add File Line: {line}"
            )));
        };
        output.push(content);
    }

    Ok(output.join("\n"))
}

fn parse_update_diff(mut lines: Vec<String>, input: &str) -> Result<Vec<Chunk>, ApplyDiffError> {
    lines.push(END_PATCH.to_owned());
    let mut parser = ParserState {
        lines,
        index: 0,
        fuzz: 0,
    };
    let input_lines: Vec<&str> = input.split('\n').collect();
    let mut chunks = Vec::new();
    let mut cursor = 0;

    while !is_done(&parser, &END_SECTION_MARKERS) {
        let (anchors, anchor_count) = read_anchors(&mut parser);
        if anchor_count == 0 && cursor != 0 {
            let line = parser
                .lines
                .get(parser.index)
                .map_or("undefined", String::as_str);
            return Err(ApplyDiffError::new(format!("Invalid Line:\n{line}")));
        }

        let require_anchor_match = anchor_count > 1;
        for (index, anchor) in anchors.iter().enumerate() {
            cursor = advance_cursor_to_anchor(
                anchor,
                &input_lines,
                cursor,
                &mut parser,
                require_anchor_match,
                index > 0,
            )?;
        }

        let section = read_section(&parser.lines, parser.index)?;
        let next_context_text = section.next_context.join("\n");
        let (new_index, fuzz) =
            find_context(&input_lines, &section.next_context, cursor, section.eof);
        let Some(new_index) = new_index else {
            let kind = if section.eof {
                "Invalid EOF Context"
            } else {
                "Invalid Context"
            };
            return Err(ApplyDiffError::new(format!(
                "{kind} {cursor}:\n{next_context_text}"
            )));
        };

        parser.fuzz += fuzz;
        chunks.extend(section.chunks.into_iter().map(|mut chunk| {
            chunk.orig_index += new_index;
            chunk
        }));
        cursor = new_index + section.next_context.len();
        parser.index = section.end_index;
    }

    Ok(chunks)
}

fn read_anchors(parser: &mut ParserState) -> (Vec<String>, usize) {
    let mut anchors = Vec::new();
    let mut anchor_count = 0;

    loop {
        let start_index = parser.index;
        let anchor = read_str(parser, "@@ ");
        let mut consumed = parser.index != start_index;

        if !consumed
            && parser
                .lines
                .get(parser.index)
                .is_some_and(|line| line == "@@")
        {
            parser.index += 1;
            consumed = true;
        }
        if !consumed {
            break;
        }

        anchor_count += 1;
        if let Some(anchor) = anchor.filter(|anchor| !trim_diff_whitespace(anchor).is_empty()) {
            anchors.push(anchor);
        }
    }

    (anchors, anchor_count)
}

fn advance_cursor_to_anchor(
    anchor: &str,
    input_lines: &[&str],
    mut cursor: usize,
    parser: &mut ParserState,
    require_match: bool,
    force_forward_search: bool,
) -> Result<usize, ApplyDiffError> {
    let mut found = false;

    if !force_forward_search && input_lines[..cursor].contains(&anchor) {
        found = true;
    } else if let Some(index) = input_lines[cursor..]
        .iter()
        .position(|line| *line == anchor)
    {
        cursor += index + 1;
        found = true;
    }

    if !found {
        if !force_forward_search
            && input_lines[..cursor]
                .iter()
                .any(|line| trim_diff_whitespace(line) == trim_diff_whitespace(anchor))
        {
            found = true;
        } else if let Some(index) = input_lines[cursor..]
            .iter()
            .position(|line| trim_diff_whitespace(line) == trim_diff_whitespace(anchor))
        {
            cursor += index + 1;
            parser.fuzz += 1;
            found = true;
        }
    }

    if require_match && !found {
        return Err(ApplyDiffError::new(format!(
            "Invalid Anchor {cursor}:\n{anchor}"
        )));
    }

    Ok(cursor)
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum LineMode {
    Keep,
    Add,
    Delete,
}

struct Section {
    next_context: Vec<String>,
    chunks: Vec<Chunk>,
    end_index: usize,
    eof: bool,
}

fn read_section(lines: &[String], start_index: usize) -> Result<Section, ApplyDiffError> {
    let mut context = Vec::new();
    let mut del_lines = Vec::new();
    let mut ins_lines = Vec::new();
    let mut chunks = Vec::new();
    let mut mode = LineMode::Keep;
    let mut index = start_index;
    let orig_index = index;

    while index < lines.len() {
        let raw = &lines[index];
        if raw.starts_with("@@")
            || raw.starts_with(END_PATCH)
            || raw.starts_with(UPDATE_FILE)
            || raw.starts_with(DELETE_FILE)
            || raw.starts_with(ADD_FILE)
            || raw.starts_with(END_FILE)
        {
            break;
        }
        if raw == "***" {
            break;
        }
        if raw.starts_with("***") {
            return Err(ApplyDiffError::new(format!("Invalid Line: {raw}")));
        }

        index += 1;
        let last_mode = mode;
        let line = if raw.is_empty() { " " } else { raw.as_str() };
        let (next_mode, content) = if let Some(content) = line.strip_prefix('+') {
            (LineMode::Add, content)
        } else if let Some(content) = line.strip_prefix('-') {
            (LineMode::Delete, content)
        } else if let Some(content) = line.strip_prefix(' ') {
            (LineMode::Keep, content)
        } else {
            return Err(ApplyDiffError::new(format!("Invalid Line: {line}")));
        };
        mode = next_mode;

        if mode == LineMode::Keep
            && last_mode != mode
            && (!ins_lines.is_empty() || !del_lines.is_empty())
        {
            chunks.push(Chunk {
                orig_index: context.len() - del_lines.len(),
                del_lines: std::mem::take(&mut del_lines),
                ins_lines: std::mem::take(&mut ins_lines),
            });
        }

        match mode {
            LineMode::Delete => {
                del_lines.push(content.to_owned());
                context.push(content.to_owned());
            }
            LineMode::Add => ins_lines.push(content.to_owned()),
            LineMode::Keep => context.push(content.to_owned()),
        }
    }

    if !ins_lines.is_empty() || !del_lines.is_empty() {
        chunks.push(Chunk {
            orig_index: context.len() - del_lines.len(),
            del_lines,
            ins_lines,
        });
    }

    if lines.get(index).is_some_and(|line| line == END_FILE) {
        return Ok(Section {
            next_context: context,
            chunks,
            end_index: index + 1,
            eof: true,
        });
    }

    if index == orig_index {
        let line = lines.get(index).map_or("undefined", String::as_str);
        return Err(ApplyDiffError::new(format!(
            "Nothing in this section - index={index} {line}"
        )));
    }

    Ok(Section {
        next_context: context,
        chunks,
        end_index: index,
        eof: false,
    })
}

fn find_context(
    lines: &[&str],
    context: &[String],
    start: usize,
    eof: bool,
) -> (Option<usize>, usize) {
    if eof {
        let end_start = lines.len().saturating_sub(context.len());
        let end_match = find_context_core(lines, context, end_start);
        if end_match.0.is_some() {
            return end_match;
        }

        let (new_index, fuzz) = find_context_core(lines, context, start);
        return (new_index, fuzz + 10_000);
    }

    find_context_core(lines, context, start)
}

fn find_context_core(lines: &[&str], context: &[String], start: usize) -> (Option<usize>, usize) {
    if context.is_empty() {
        return (Some(start), 0);
    }

    for index in start..lines.len() {
        if equals_slice(lines, context, index, |value| value) {
            return (Some(index), 0);
        }
    }
    for index in start..lines.len() {
        if equals_slice(lines, context, index, trim_diff_whitespace_end) {
            return (Some(index), 1);
        }
    }
    for index in start..lines.len() {
        if equals_slice(lines, context, index, trim_diff_whitespace) {
            return (Some(index), 100);
        }
    }

    (None, 0)
}

fn equals_slice<'a, F>(source: &'a [&'a str], target: &'a [String], start: usize, map: F) -> bool
where
    F: Fn(&'a str) -> &'a str,
{
    if start + target.len() > source.len() {
        return false;
    }

    source[start..start + target.len()]
        .iter()
        .copied()
        .zip(target.iter().map(String::as_str))
        .all(|(source, target)| map(source) == map(target))
}

fn trim_diff_whitespace(value: &str) -> &str {
    value.trim_matches(is_diff_whitespace)
}

fn trim_diff_whitespace_end(value: &str) -> &str {
    value.trim_end_matches(is_diff_whitespace)
}

fn is_diff_whitespace(character: char) -> bool {
    matches!(
        character,
        '\u{0009}'
            | '\u{000A}'
            | '\u{000B}'
            | '\u{000C}'
            | '\u{000D}'
            | '\u{0020}'
            | '\u{00A0}'
            | '\u{1680}'
            | '\u{2000}'
            ..='\u{200A}'
                | '\u{2028}'
                | '\u{2029}'
                | '\u{202F}'
                | '\u{205F}'
                | '\u{3000}'
                | '\u{FEFF}'
    )
}

fn apply_chunks(input: &str, chunks: &[Chunk]) -> Result<String, ApplyDiffError> {
    let orig_lines: Vec<&str> = input.split('\n').collect();
    let mut dest_lines: Vec<&str> = Vec::new();
    let mut orig_index = 0;

    for chunk in chunks {
        if chunk.orig_index > orig_lines.len() {
            return Err(ApplyDiffError::new(format!(
                "applyDiff: chunk.origIndex {} > input length {}",
                chunk.orig_index,
                orig_lines.len()
            )));
        }
        if orig_index > chunk.orig_index {
            return Err(ApplyDiffError::new(format!(
                "applyDiff: overlapping chunk at {} (cursor {orig_index})",
                chunk.orig_index
            )));
        }

        dest_lines.extend_from_slice(&orig_lines[orig_index..chunk.orig_index]);
        orig_index = chunk.orig_index;
        dest_lines.extend(chunk.ins_lines.iter().map(String::as_str));
        orig_index += chunk.del_lines.len();
    }

    dest_lines.extend_from_slice(&orig_lines[orig_index..]);
    Ok(dest_lines.join("\n"))
}