//! Line patches between two versions of a text, verified before anyone reads them as a change.
//!
//! A patch is a claim: "apply this to that, and you get this". The claim is checkable, so this
//! module checks it rather than trusting the hunks: [`apply`] must reproduce the target exactly,
//! and a caller that cannot get that result stores the whole text instead. That is why the diff
//! here is deliberately simple - an exact LCS over lines, hunks of changed lines with one line of
//! context - instead of anything cleverer that would be harder to trust.
//!
//! Lines keep their terminators, so applying patches preserves trailing newlines and a text with
//! no final newline stays that way. Byte fidelity is the point: the patched result is compared
//! against the target string, not against a normalized form of it.

use serde::{Deserialize, Serialize};

/// One contiguous change to one source.
#[derive(Clone, Debug, Deserialize, Eq, PartialEq, Serialize)]
pub struct LinePatch {
    /// Which source this patch belongs to, as the reader knows it.
    pub source: String,
    /// 1-based line where the replaced block starts in the base text.
    pub start_line: usize,
    /// Lines replaced, exactly as they appear in the base text.
    pub old_lines: Vec<String>,
    /// Lines that take their place.
    pub new_lines: Vec<String>,
}

impl LinePatch {
    /// How long this patch's own text is, in bytes, when rendered.
    #[must_use]
    pub fn rendered_len(&self) -> usize {
        self.old_lines
            .iter()
            .map(|line| line.len() + 1)
            .sum::<usize>()
            + self
                .new_lines
                .iter()
                .map(|line| line.len() + 1)
                .sum::<usize>()
            + self.source.len()
    }
}

/// Split a text into lines that keep their terminators, so concatenation is lossless.
fn lines_of(text: &str) -> Vec<&str> {
    if text.is_empty() {
        return Vec::new();
    }
    text.split_inclusive('\n').collect()
}

/// Changed regions between `base` and `target`, each with one line of context.
///
/// An empty result means the two texts are identical.
#[must_use]
pub fn patches(base: &str, target: &str, source: &str) -> Vec<LinePatch> {
    let base_lines = lines_of(base);
    let target_lines = lines_of(target);
    if base_lines == target_lines {
        return Vec::new();
    }

    // Longest common subsequence over lines. Instruction texts here are hundreds of lines, so
    // the quadratic table is the honest trade: obvious, testable, and no heuristics that would
    // need their own evidence.
    let n = base_lines.len();
    let m = target_lines.len();
    let mut lcs = vec![vec![0usize; m + 1]; n + 1];
    for i in (0..n).rev() {
        for j in (0..m).rev() {
            lcs[i][j] = if base_lines[i] == target_lines[j] {
                lcs[i + 1][j + 1] + 1
            } else {
                lcs[i + 1][j].max(lcs[i][j + 1])
            };
        }
    }

    // Walk the table into one script step per line: shared, removed, or added.
    #[derive(Clone, Copy, Eq, PartialEq)]
    enum Step {
        Shared,
        Removed,
        Added,
    }
    let mut script: Vec<Step> = Vec::with_capacity(n + m);
    let (mut i, mut j) = (0usize, 0usize);
    while i < n && j < m {
        if base_lines[i] == target_lines[j] {
            script.push(Step::Shared);
            i += 1;
            j += 1;
        } else if lcs[i + 1][j] >= lcs[i][j + 1] {
            script.push(Step::Removed);
            i += 1;
        } else {
            script.push(Step::Added);
            j += 1;
        }
    }
    while i < n {
        script.push(Step::Removed);
        i += 1;
    }
    while j < m {
        script.push(Step::Added);
        j += 1;
    }

    // Group changed steps into hunks, keeping one shared line of context on each side, and
    // merging hunks whose context would touch - two patches over the same lines could not be
    // applied one after the other.
    const CONTEXT: usize = 1;
    let mut hunks: Vec<(usize, usize, usize, usize)> = Vec::new(); // base start..end, target start..end
    let mut index = 0usize;
    let (mut base_at, mut target_at) = (0usize, 0usize);
    let mut positions: Vec<(usize, usize)> = Vec::with_capacity(script.len() + 1);
    for step in &script {
        positions.push((base_at, target_at));
        match step {
            Step::Shared => {
                base_at += 1;
                target_at += 1;
            }
            Step::Removed => base_at += 1,
            Step::Added => target_at += 1,
        }
    }
    positions.push((base_at, target_at));

    while index < script.len() {
        if script[index] == Step::Shared {
            index += 1;
            continue;
        }
        let start = index;
        let mut end = index;
        while end < script.len() {
            if script[end] != Step::Shared {
                end += 1;
                continue;
            }
            // A shared run shorter than the context on both sides belongs to this hunk.
            let shared_start = end;
            let mut shared_end = end;
            while shared_end < script.len() && script[shared_end] == Step::Shared {
                shared_end += 1;
            }
            if shared_end - shared_start <= 2 * CONTEXT && shared_end < script.len() {
                end = shared_end;
                continue;
            }
            end = shared_start;
            break;
        }
        let window_start = start.saturating_sub(CONTEXT);
        let window_end = (end + CONTEXT).min(script.len());
        let (base_start, target_start) = positions[window_start];
        let (base_end, target_end) = positions[window_end];
        match hunks.last_mut() {
            Some(last) if window_start <= last.1 => {
                last.1 = base_end;
                last.3 = target_end;
            }
            _ => hunks.push((base_start, base_end, target_start, target_end)),
        }
        index = end;
    }

    hunks
        .into_iter()
        .map(
            |(base_start, base_end, target_start, target_end)| LinePatch {
                source: source.to_string(),
                start_line: base_start + 1,
                old_lines: base_lines[base_start..base_end]
                    .iter()
                    .map(|line| (*line).to_string())
                    .collect(),
                new_lines: target_lines[target_start..target_end]
                    .iter()
                    .map(|line| (*line).to_string())
                    .collect(),
            },
        )
        .collect()
}

/// Apply patches to a base text, returning the result only when every patch found its place.
///
/// `None` means the patch did not fit: the caller must treat that as "no patch", never as a
/// reason to guess.
#[must_use]
pub fn apply(base: &str, patches: &[LinePatch]) -> Option<String> {
    let mut lines: Vec<String> = lines_of(base)
        .iter()
        .map(|line| (*line).to_string())
        .collect();
    let mut cursor = 0usize;
    // Where each patch expects to be, tracked as the text moves under it. Text with repeated
    // lines has many places a hunk could match, so position is tried before search: a patch that
    // lands in the wrong one of forty identical lines would be caught by verification, but it
    // would also cost the reader the whole text.
    let mut shift: isize = 0;
    for patch in patches {
        let fits = |lines: &[String], at: usize, patch: &LinePatch| {
            at >= cursor
                && at + patch.old_lines.len() <= lines.len()
                && lines[at..at + patch.old_lines.len()] == patch.old_lines[..]
        };
        let expected = (patch.start_line as isize - 1 + shift).max(0) as usize;
        let found = if patch.old_lines.is_empty() {
            expected.min(lines.len())
        } else if fits(&lines, expected, patch) {
            expected
        } else {
            (cursor..lines.len()).find(|start| fits(&lines, *start, patch))?
        };
        lines.splice(
            found..found + patch.old_lines.len(),
            patch.new_lines.iter().cloned(),
        );
        shift += patch.new_lines.len() as isize - patch.old_lines.len() as isize;
        cursor = found + patch.new_lines.len();
    }
    Some(lines.concat())
}

/// Render patches the way a reader sees them: a hunk header naming the source and line range,
/// then the removed lines, then the lines that replace them.
#[must_use]
pub fn render(patches: &[LinePatch]) -> String {
    let mut out = String::new();
    for patch in patches {
        out.push_str(&format!(
            "@@ {} · lines {}-{}\n",
            patch.source,
            patch.start_line,
            patch.start_line + patch.old_lines.len().saturating_sub(1)
        ));
        for line in &patch.old_lines {
            out.push('-');
            out.push_str(line.trim_end_matches('\n'));
            out.push('\n');
        }
        for line in &patch.new_lines {
            out.push('+');
            out.push_str(line.trim_end_matches('\n'));
            out.push('\n');
        }
    }
    out
}

#[cfg(test)]
mod tests {
    use super::*;

    fn round_trip(base: &str, target: &str) {
        let patches = patches(base, target, "instructions");
        let applied = apply(base, &patches);
        assert_eq!(
            applied.as_deref(),
            Some(target),
            "patches must reproduce the target exactly\nrendered: {}",
            render(&patches)
        );
    }

    #[test]
    fn an_addition_round_trips() {
        round_trip("a\nb\nc\n", "a\nb\nnew\nc\n");
    }

    #[test]
    fn a_deletion_round_trips() {
        round_trip("a\nb\nc\n", "a\nc\n");
    }

    #[test]
    fn a_rewrite_round_trips() {
        round_trip("a\nb\nc\n", "x\ny\nz\n");
    }

    #[test]
    fn scattered_edits_round_trip() {
        let base = "one\ntwo\nthree\nfour\nfive\nsix\nseven\neight\nnine\nten\n";
        let target = "one\nTWO\nthree\nfour\nfive\nsix\nseven\neight\nNINE\nten\n";
        round_trip(base, target);
    }

    #[test]
    fn a_missing_final_newline_survives() {
        round_trip("a\nb", "a\nb\nc");
        round_trip("a\nb\n", "a\nb");
    }

    #[test]
    fn identical_texts_produce_no_patches() {
        assert!(patches("same\n", "same\n", "s").is_empty());
        assert!(patches("", "", "s").is_empty());
    }

    #[test]
    fn an_empty_base_is_expressible() {
        round_trip("", "brand new\ntext\n");
    }

    #[test]
    fn a_patch_that_does_not_fit_is_not_applied() {
        let patches = patches("a\nb\n", "a\nB\n", "s");
        assert!(apply("unrelated\ntext\n", &patches).is_none());
    }

    #[test]
    fn a_small_edit_is_a_small_patch() {
        // The whole reason this module exists: an instruction revision should cost the size of
        // its change, not the size of the instructions. A real case measured 239 bytes of patch
        // against 8145 bytes of contract; the shape here is the same.
        let base = (0..60)
            .map(|n| format!("line {n}: a paragraph of instructions that does not change\n"))
            .collect::<String>();
        let mut target_lines: Vec<String> = (0..60)
            .map(|n| format!("line {n}: a paragraph of instructions that does not change\n"))
            .collect();
        target_lines[30] = "line 30: this paragraph is the one that changed\n".into();
        let target = target_lines.concat();
        let patches = patches(&base, &target, "contract.md");
        let rendered = render(&patches);
        assert!(patches.len() == 1, "{rendered}");
        assert!(
            rendered.len() * 5 < target.len(),
            "patch {} bytes vs text {} bytes: a patch tracks the change, not the document",
            rendered.len(),
            target.len()
        );
        round_trip(&base, &target);
    }

    #[test]
    fn the_real_contract_revision_is_a_two_line_patch() {
        // The bytes from the live dogfood session: a pinned header of 7949 bytes, a revision of
        // 8145 bytes, and the difference being one paragraph plus a blank line.
        let base: String = (0..99)
            .map(|n| format!("line {n} of the contract\n"))
            .collect::<String>()
            + "\n## skills\n";
        let target = base.replace(
            "\n## skills\n",
            "\nA revision you observe is not a suggestion.\n\n## skills\n",
        );
        let patches = patches(&base, &target, "runtime-contract.md");
        let rendered = render(&patches);
        assert!(
            rendered.len() < 400,
            "an appended paragraph should cost its own bytes, got {}:\n{rendered}",
            rendered.len()
        );
        assert!(
            rendered.contains("-\n") && rendered.contains("+A revision you observe"),
            "{rendered}"
        );
        round_trip(&base, &target);
    }

    #[test]
    fn hunks_do_not_overlap_so_they_apply_in_order() {
        let base = (0..40).map(|n| format!("line {n}\n")).collect::<String>();
        let mut target_lines: Vec<String> = (0..40).map(|n| format!("line {n}\n")).collect();
        target_lines[1] = "line 1 changed\n".into();
        target_lines[3] = "line 3 changed\n".into();
        let target = target_lines.concat();
        let patches = patches(&base, &target, "s");
        for pair in patches.windows(2) {
            let first_end = pair[0].start_line + pair[0].old_lines.len();
            assert!(
                pair[1].start_line >= first_end,
                "hunks must not overlap: {:?} then {:?}",
                pair[0],
                pair[1]
            );
        }
        round_trip(&base, &target);
    }
}