Skip to content

Solution for long term memory for agent coding CLIs and to facilitate handoff between different agent vendors

Rust
16.3 KB
Raw Blame
//! Bounded line diff for the page-history view.
//!
//! Myers' O((N+M)·D) algorithm over lines, after trimming the common prefix
//! and suffix. Every dimension is capped: input bytes and lines per side, the
//! edit distance the search may explore, and the rendered output lines. A
//! pair past a cap renders as [`Diff::TooLarge`] instead of spending memory
//! or CPU on a page nobody can read as a diff anyway.

use serde::Serialize;

/// Largest side, in bytes, the diff accepts.
pub(crate) const MAX_INPUT_BYTES: usize = 512 * 1024;
/// Largest side, in lines, the diff accepts.
pub(crate) const MAX_INPUT_LINES: usize = 10_000;
/// Most line edits the search explores before giving up. Its trace keeps one
/// frontier per edit step, so memory grows with the square of this.
pub(crate) const MAX_EDIT_DISTANCE: usize = 1_000;
/// Most diff lines (context and changes) one response carries.
pub(crate) const MAX_OUTPUT_LINES: usize = 2_000;
/// Unchanged lines shown around each change.
const CONTEXT: usize = 3;

/// One rendered diff line.
#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
pub(crate) struct DiffLine {
    /// `' '` context, `'-'` removed, `'+'` added.
    pub op: char,
    /// The line, without its newline.
    pub text: String,
}

/// One hunk: a run of changes with surrounding context.
#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
pub(crate) struct Hunk {
    /// 1-based first line in the old text (0 when the hunk is empty there).
    pub old_start: usize,
    /// Lines the hunk covers in the old text.
    pub old_len: usize,
    /// 1-based first line in the new text (0 when the hunk is empty there).
    pub new_start: usize,
    /// Lines the hunk covers in the new text.
    pub new_len: usize,
    /// The hunk's lines.
    pub lines: Vec<DiffLine>,
}

impl Hunk {
    /// The `@@ -a,b +c,d @@` header line.
    pub(crate) fn header(&self) -> String {
        format!(
            "@@ -{},{} +{},{} @@",
            self.old_start, self.old_len, self.new_start, self.new_len
        )
    }
}

/// Outcome of [`unified`].
#[derive(Debug, Clone, PartialEq, Eq)]
pub(crate) enum Diff {
    /// The two texts are identical.
    Same,
    /// Hunks in order. `truncated` is set when [`MAX_OUTPUT_LINES`] cut the
    /// list short.
    Changed { hunks: Vec<Hunk>, truncated: bool },
    /// A cap refused the pair; the string says which.
    TooLarge(&'static str),
}

#[derive(Clone, Copy, PartialEq, Eq)]
enum Op {
    Keep,
    Delete,
    Insert,
}

/// Unified line diff from `old` to `new`, bounded by this module's caps.
pub(crate) fn unified(old: &str, new: &str) -> Diff {
    if old == new {
        return Diff::Same;
    }
    if old.len() > MAX_INPUT_BYTES || new.len() > MAX_INPUT_BYTES {
        return Diff::TooLarge("a version is larger than the diff limit");
    }
    let a: Vec<&str> = old.lines().collect();
    let b: Vec<&str> = new.lines().collect();
    if a.len() > MAX_INPUT_LINES || b.len() > MAX_INPUT_LINES {
        return Diff::TooLarge("a version has more lines than the diff limit");
    }
    let Some(ops) = edit_script(&a, &b) else {
        return Diff::TooLarge("the versions differ in more lines than the diff limit");
    };
    if ops.iter().all(|op| *op == Op::Keep) {
        // Same lines, different line endings or trailing newline.
        return Diff::Changed {
            hunks: Vec::new(),
            truncated: false,
        };
    }
    let (hunks, truncated) = hunks(&a, &b, &ops);
    Diff::Changed { hunks, truncated }
}

/// The shortest edit script, or `None` past [`MAX_EDIT_DISTANCE`].
fn edit_script(a: &[&str], b: &[&str]) -> Option<Vec<Op>> {
    let prefix = a.iter().zip(b).take_while(|(x, y)| x == y).count();
    let suffix = a[prefix..]
        .iter()
        .rev()
        .zip(b[prefix..].iter().rev())
        .take_while(|(x, y)| x == y)
        .count();
    let mid_a = &a[prefix..a.len() - suffix];
    let mid_b = &b[prefix..b.len() - suffix];
    let mut ops = vec![Op::Keep; prefix];
    ops.extend(myers(mid_a, mid_b)?);
    ops.extend(std::iter::repeat_n(Op::Keep, suffix));
    Some(ops)
}

/// Myers' greedy forward search, keeping one frontier per edit step so the
/// path can be walked back.
fn myers(a: &[&str], b: &[&str]) -> Option<Vec<Op>> {
    let n = a.len();
    let m = b.len();
    let max = n + m;
    if max == 0 {
        return Some(Vec::new());
    }
    let limit = max.min(MAX_EDIT_DISTANCE);
    // `v[k + offset]` is the furthest x reached on diagonal k = x - y.
    let offset = limit + 1;
    let mut v = vec![0usize; 2 * limit + 3];
    let mut trace: Vec<Vec<usize>> = Vec::new();
    for d in 0..=limit {
        trace.push(v.clone());
        let d_i = d as isize;
        let mut k = -d_i;
        while k <= d_i {
            let idx = (k + offset as isize) as usize;
            let mut x = if k == -d_i || (k != d_i && v[idx - 1] < v[idx + 1]) {
                v[idx + 1]
            } else {
                v[idx - 1] + 1
            };
            let mut y = (x as isize - k) as usize;
            while x < n && y < m && a[x] == b[y] {
                x += 1;
                y += 1;
            }
            v[idx] = x;
            if x >= n && y >= m {
                return Some(backtrack(&trace, offset, n, m));
            }
            k += 2;
        }
    }
    None
}

fn backtrack(trace: &[Vec<usize>], offset: usize, n: usize, m: usize) -> Vec<Op> {
    let mut ops = Vec::with_capacity(n + m);
    let mut x = n as isize;
    let mut y = m as isize;
    for (d, v) in trace.iter().enumerate().rev() {
        let d = d as isize;
        let k = x - y;
        let at = |k: isize| v[(k + offset as isize) as usize] as isize;
        let prev_k = if k == -d || (k != d && at(k - 1) < at(k + 1)) {
            k + 1
        } else {
            k - 1
        };
        let prev_x = if d == 0 { 0 } else { at(prev_k) };
        let prev_y = if d == 0 { 0 } else { prev_x - prev_k };
        while x > prev_x && y > prev_y {
            ops.push(Op::Keep);
            x -= 1;
            y -= 1;
        }
        if d > 0 {
            ops.push(if x == prev_x { Op::Insert } else { Op::Delete });
        }
        x = prev_x;
        y = prev_y;
    }
    ops.reverse();
    ops
}

/// Group an edit script into hunks with [`CONTEXT`] lines around each run of
/// changes, stopping at [`MAX_OUTPUT_LINES`].
fn hunks(a: &[&str], b: &[&str], ops: &[Op]) -> (Vec<Hunk>, bool) {
    // Positions in each text before every op.
    let mut positions = Vec::with_capacity(ops.len());
    let (mut ia, mut ib) = (0usize, 0usize);
    for op in ops {
        positions.push((ia, ib));
        match op {
            Op::Keep => {
                ia += 1;
                ib += 1;
            }
            Op::Delete => ia += 1,
            Op::Insert => ib += 1,
        }
    }
    let changes: Vec<usize> = (0..ops.len()).filter(|&i| ops[i] != Op::Keep).collect();
    let mut out = Vec::new();
    let mut emitted = 0usize;
    let mut i = 0usize;
    while i < changes.len() {
        let start = changes[i].saturating_sub(CONTEXT);
        let mut end = changes[i];
        // Merge changes whose context windows touch.
        while i + 1 < changes.len() && changes[i + 1] <= end + 2 * CONTEXT + 1 {
            i += 1;
            end = changes[i];
        }
        let end = (end + CONTEXT + 1).min(ops.len());
        let (old_first, new_first) = positions[start];
        let mut lines = Vec::new();
        let (mut old_len, mut new_len) = (0usize, 0usize);
        for j in start..end {
            if emitted >= MAX_OUTPUT_LINES {
                if !lines.is_empty() {
                    out.push(Hunk {
                        old_start: start_of(old_first, old_len),
                        old_len,
                        new_start: start_of(new_first, new_len),
                        new_len,
                        lines,
                    });
                }
                return (out, true);
            }
            let (pa, pb) = positions[j];
            let line = match ops[j] {
                Op::Keep => {
                    old_len += 1;
                    new_len += 1;
                    DiffLine {
                        op: ' ',
                        text: a[pa].to_owned(),
                    }
                }
                Op::Delete => {
                    old_len += 1;
                    DiffLine {
                        op: '-',
                        text: a[pa].to_owned(),
                    }
                }
                Op::Insert => {
                    new_len += 1;
                    DiffLine {
                        op: '+',
                        text: b[pb].to_owned(),
                    }
                }
            };
            lines.push(line);
            emitted += 1;
        }
        out.push(Hunk {
            old_start: start_of(old_first, old_len),
            old_len,
            new_start: start_of(new_first, new_len),
            new_len,
            lines,
        });
        i += 1;
    }
    (out, false)
}

/// Unified-diff convention: a side the hunk does not touch starts at the line
/// before it (0 at the top of the file).
fn start_of(first: usize, len: usize) -> usize {
    if len == 0 { first } else { first + 1 }
}

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

    fn render(diff: &Diff) -> String {
        match diff {
            Diff::Same => "same".into(),
            Diff::TooLarge(why) => format!("too large: {why}"),
            Diff::Changed { hunks, truncated } => {
                let mut out = String::new();
                for hunk in hunks {
                    out.push_str(&hunk.header());
                    out.push('\n');
                    for line in &hunk.lines {
                        out.push(line.op);
                        out.push_str(&line.text);
                        out.push('\n');
                    }
                }
                if *truncated {
                    out.push_str("[truncated]\n");
                }
                out
            }
        }
    }

    #[test]
    fn identical_texts_are_the_same() {
        assert_eq!(unified("a\nb\n", "a\nb\n"), Diff::Same);
    }

    #[test]
    fn one_changed_line_gets_context_and_headers() {
        let old = "1\n2\n3\n4\n5\n6\n7\n8\n9\n";
        let new = "1\n2\n3\n4\nfive\n6\n7\n8\n9\n";
        assert_eq!(
            render(&unified(old, new)),
            "@@ -2,7 +2,7 @@\n 2\n 3\n 4\n-5\n+five\n 6\n 7\n 8\n"
        );
    }

    #[test]
    fn insertions_and_deletions_at_the_edges() {
        assert_eq!(render(&unified("", "a\nb\n")), "@@ -0,0 +1,2 @@\n+a\n+b\n");
        assert_eq!(render(&unified("a\nb\n", "")), "@@ -1,2 +0,0 @@\n-a\n-b\n");
        assert_eq!(
            render(&unified("b\n", "a\nb\nc\n")),
            "@@ -1,1 +1,3 @@\n+a\n b\n+c\n"
        );
    }

    #[test]
    fn distant_changes_are_separate_hunks() {
        let old: String = (1..=30).map(|i| format!("{i}\n")).collect();
        let new: String = (1..=30)
            .map(|i| match i {
                2 => "two\n".to_owned(),
                28 => "twenty-eight\n".to_owned(),
                _ => format!("{i}\n"),
            })
            .collect();
        let Diff::Changed { hunks, truncated } = unified(&old, &new) else {
            panic!("expected a change");
        };
        assert!(!truncated);
        assert_eq!(hunks.len(), 2, "{}", render(&unified(&old, &new)));
        assert_eq!(hunks[0].header(), "@@ -1,5 +1,5 @@");
        assert_eq!(hunks[1].header(), "@@ -25,6 +25,6 @@");
    }

    #[test]
    fn the_script_is_minimal_and_reproduces_the_new_text() {
        let old = "a\nb\nc\na\nb\nb\na\n";
        let new = "c\nb\na\nb\na\nc\n";
        let Diff::Changed { hunks, .. } = unified(old, new) else {
            panic!("expected a change");
        };
        let lines: Vec<&DiffLine> = hunks.iter().flat_map(|h| &h.lines).collect();
        let edits = lines.iter().filter(|l| l.op != ' ').count();
        // The classic Myers example: five edits.
        assert_eq!(edits, 5);
        let rebuilt: Vec<&str> = lines
            .iter()
            .filter(|l| l.op != '-')
            .map(|l| l.text.as_str())
            .collect();
        assert_eq!(rebuilt, new.lines().collect::<Vec<_>>());
        let original: Vec<&str> = lines
            .iter()
            .filter(|l| l.op != '+')
            .map(|l| l.text.as_str())
            .collect();
        assert_eq!(original, old.lines().collect::<Vec<_>>());
    }

    /// Every pair over a small alphabet: the script must rebuild both texts
    /// and be as short as the LCS says it can be.
    #[test]
    fn scripts_are_valid_and_minimal_against_a_brute_force_lcs() {
        fn lcs(a: &[&str], b: &[&str]) -> usize {
            let mut t = vec![vec![0usize; b.len() + 1]; a.len() + 1];
            for i in 0..a.len() {
                for j in 0..b.len() {
                    t[i + 1][j + 1] = if a[i] == b[j] {
                        t[i][j] + 1
                    } else {
                        t[i][j + 1].max(t[i + 1][j])
                    };
                }
            }
            t[a.len()][b.len()]
        }
        // A tiny deterministic generator; no new dependency for a test.
        let mut seed: u64 = 0x9e37_79b9_7f4a_7c15;
        let mut next = move || {
            seed ^= seed << 13;
            seed ^= seed >> 7;
            seed ^= seed << 17;
            seed
        };
        let alphabet = ["a", "b", "c"];
        for _ in 0..2_000 {
            let len_a = (next() % 9) as usize;
            let len_b = (next() % 9) as usize;
            let a: Vec<&str> = (0..len_a)
                .map(|_| alphabet[(next() % 3) as usize])
                .collect();
            let b: Vec<&str> = (0..len_b)
                .map(|_| alphabet[(next() % 3) as usize])
                .collect();
            let ops = edit_script(&a, &b).expect("small inputs stay under the cap");
            let (mut ia, mut ib) = (0, 0);
            for op in &ops {
                match op {
                    Op::Keep => {
                        assert_eq!(a[ia], b[ib], "{a:?} -> {b:?}");
                        ia += 1;
                        ib += 1;
                    }
                    Op::Delete => ia += 1,
                    Op::Insert => ib += 1,
                }
            }
            assert_eq!((ia, ib), (a.len(), b.len()), "{a:?} -> {b:?}");
            let edits = ops.iter().filter(|op| **op != Op::Keep).count();
            assert_eq!(edits, a.len() + b.len() - 2 * lcs(&a, &b), "{a:?} -> {b:?}");
        }
    }

    #[test]
    fn caps_refuse_oversized_input_and_edit_distance() {
        let big = "x".repeat(MAX_INPUT_BYTES + 1);
        assert!(matches!(unified(&big, "y"), Diff::TooLarge(_)));

        let many: String = (0..=MAX_INPUT_LINES).map(|i| format!("{i}\n")).collect();
        assert!(matches!(unified(&many, "y"), Diff::TooLarge(_)));

        // Every line differs: the distance is twice the line count.
        let old: String = (0..MAX_EDIT_DISTANCE).map(|i| format!("a{i}\n")).collect();
        let new: String = (0..MAX_EDIT_DISTANCE).map(|i| format!("b{i}\n")).collect();
        assert!(matches!(unified(&old, &new), Diff::TooLarge(_)));
        // Under the distance cap the same shape diffs.
        let old: String = (0..100).map(|i| format!("a{i}\n")).collect();
        let new: String = (0..100).map(|i| format!("b{i}\n")).collect();
        assert!(matches!(unified(&old, &new), Diff::Changed { .. }));
    }

    #[test]
    fn output_is_cut_at_the_line_cap() {
        let old: String = (0..MAX_INPUT_LINES / 2).map(|i| format!("{i}\n")).collect();
        // 500 changed lines (an edit distance of 1000, inside the cap), close
        // enough that their context merges into one run longer than the cap.
        let new: String = (0..MAX_INPUT_LINES / 2)
            .map(|i| {
                if i % 7 == 0 && i < 3_500 {
                    format!("changed {i}\n")
                } else {
                    format!("{i}\n")
                }
            })
            .collect();
        let Diff::Changed { hunks, truncated } = unified(&old, &new) else {
            panic!("expected a change");
        };
        assert!(truncated);
        let lines: usize = hunks.iter().map(|h| h.lines.len()).sum();
        assert_eq!(lines, MAX_OUTPUT_LINES);
    }

    #[test]
    fn a_line_ending_only_change_reports_no_hunks() {
        assert_eq!(
            unified("a\nb", "a\nb\n"),
            Diff::Changed {
                hunks: Vec::new(),
                truncated: false
            }
        );
    }
}