create, apply, compose, and invert patches from file changes

patch.rs

use std::collections::HashMap;

pub fn create_patch(original: &str, modified: &str) -> String {
    let original_lines = original.lines().collect::<Vec<_>>();
    let modified_lines = modified.lines().collect::<Vec<_>>();
    let mut longest_common_subsequences = HashMap::new();
    longest_common_subsequences.insert((0, 0), vec![]);

    for (i, &original_line) in original_lines.iter().enumerate() {
        for (j, &modified_line) in modified_lines.iter().enumerate() {
            let mut lcs = longest_common_subsequences.get(&(i, j)).unwrap().clone();

            if original_line == modified_line {
                lcs.push(original_line);
                longest_common_subsequences.insert((i + 1, j + 1), lcs);
            } else {
                let lcs_insert = longest_common_subsequences.get(&(i, j + 1)).unwrap();
                let lcs_delete = longest_common_subsequences.get(&(i + 1, j)).unwrap();

                if lcs_insert.len() > lcs_delete.len() {
                    longest_common_subsequences.insert((i + 1, j + 1), lcs_insert.clone());
                } else {
                    longest_common_subsequences.insert((i + 1, j + 1), lcs_delete.clone());
                }
            }
        }
    }

    let lcs = longest_common_subsequences
        .get(&(original_lines.len(), modified_lines.len()))
        .unwrap();
    let mut patch = String::new();

    let mut i = 0;
    let mut j = 0;

    for &line in lcs {
        while original_lines[i] != line {
            patch.push_str(&format!("-{}\n", original_lines[i]));
            i += 1;
        }

        while modified_lines[j] != line {
            patch.push_str(&format!("+{}\n", modified_lines[j]));
            j += 1;
        }

        patch.push_str(" \n");
        i += 1;
        j += 1;
    }

    while i < original_lines.len() {
        patch.push_str(&format!("-{}\n", original_lines[i]));
        i += 1;
    }

    while j < modified_lines.len() {
        patch.push_str(&format!("+{}\n", modified_lines[j]));
        j += 1;
    }

    patch
}

pub fn apply_patch(original: &str, patch: &str) -> Result<String, &'static str> {
    let original_lines = original.lines().collect::<Vec<_>>();
    let patch_lines = patch.lines().collect::<Vec<_>>();
    let mut result = String::new();
    let mut i = 0;

    for &line in &patch_lines {
        match line.chars().next() {
            Some('-') => {
                if original_lines[i] != &line[1..] {
                    return Err("Patch does not apply");
                }
                i += 1;
            }
            Some('+') => {
                result.push_str(&line[1..]);
                result.push('\n');
            }
            Some(' ') => {
                if original_lines[i] != &line[1..] {
                    return Err("Patch does not apply");
                }
                result.push_str(&line[1..]);
                result.push('\n');
                i += 1;
            }
            _ => return Err("Malformed patch"),
        }
    }

    if i != original_lines.len() {
        return Err("Patch does not apply");
    }

    Ok(result)
}

pub fn invert_patch(patch: &str) -> Result<String, &'static str> {
    let patch_lines = patch.lines().collect::<Vec<_>>();
    let mut result = String::new();

    for &line in &patch_lines {
        match line.chars().next() {
            Some('-') => {
                result.push('+');
                result.push_str(&line[1..]);
                result.push('\n');
            }
            Some('+') => {
                result.push('-');
                result.push_str(&line[1..]);
                result.push('\n');
            }
            Some(' ') => {
                result.push_str(line);
                result.push('\n');
            }
            _ => return Err("Malformed patch"),
        }
    }

    Ok(result)
}

pub fn compose_patches(original: &str, patch1: &str, patch2: &str) -> Result<String, &'static str> {
    let after_patch1 = apply_patch(original, patch1)?;

    let after_patch2 = apply_patch(&after_patch1, patch2)?;

    let composed_patch = create_patch(original, &after_patch2);

    Ok(composed_patch)
}

pub fn merge_patches(original: &str, patch1: &str, patch2: &str) -> Result<String, &'static str> {
    let original_lines = original.lines().collect::<Vec<_>>();
    let patch1_lines = patch1.lines().collect::<Vec<_>>();
    let patch2_lines = patch2.lines().collect::<Vec<_>>();
    let mut result1 = String::new();
    let mut result2 = String::new();
    let mut i = 0;

    for (&line1, &line2) in patch1_lines.iter().zip(patch2_lines.iter()) {
        match (line1.chars().next(), line2.chars().next()) {
            (Some('-'), Some('-'))
                if line1[1..] == line2[1..] && &line1[1..] == original_lines[i] =>
            {
                result1.push_str(line1);
                result1.push('\n');
                result2.push_str(line2);
                result2.push('\n');
                i += 1;
            }
            (Some('+'), Some('+')) if line1[1..] == line2[1..] => {
                result1.push_str(line1);
                result1.push('\n');
                result2.push_str(line2);
                result2.push('\n');
            }
            (Some(' '), Some(' '))
                if line1[1..] == line2[1..] && &line1[1..] == original_lines[i] =>
            {
                result1.push_str(line1);
                result1.push('\n');
                result2.push_str(line2);
                result2.push('\n');
                i += 1;
            }
            _ => return Err("Patch conflict"),
        }
    }

    if result1 != result2 {
        return Err("Patch conflict");
    }

    Ok(result1)
}

pub fn serialize_patch(patch: &str) -> Vec<u8> {
    patch.as_bytes().to_vec()
}

pub fn deserialize_patch(bytes: &[u8]) -> Result<String, &'static str> {
    String::from_utf8(bytes.to_vec()).map_err(|_| "Invalid UTF-8")
}