curd-editor 0.8.0

A small terminal code editor: file tree, git status and change markers, tabs, undo, selection, search and replace, a git menu, and language-server colours, errors and completion
//! Which lines of a file differ from an older version of it, for the
//! change markers beside the text.

#[cfg(test)]
mod tests;

/// Past this many differing lines the exact answer costs too much: the
/// whole changed stretch is shown as modified instead.
const MAX_DIFFERENCES: isize = 500;

/// How a line of the new text compares with the old text.
#[derive(Clone, Copy, Debug, Default, PartialEq)]
pub enum Mark {
    #[default]
    Same,
    /// A new line.
    Added,
    /// A line that replaced one or more old lines.
    Modified,
    /// Unchanged, but lines were removed just below it.
    RemovedBelow,
    /// The first line, when lines were removed above it.
    RemovedAbove,
}

/// One mark for each line of `new`, compared with `old`.
pub fn marks(old: &[String], new: &[String]) -> Vec<Mark> {
    // Most of a file is usually untouched: skip what matches at both ends.
    let prefix = old.iter().zip(new).take_while(|(a, b)| a == b).count();
    let suffix = old[prefix..]
        .iter()
        .rev()
        .zip(new[prefix..].iter().rev())
        .take_while(|(a, b)| a == b)
        .count();
    let a = &old[prefix..old.len() - suffix];
    let b = &new[prefix..new.len() - suffix];
    let (a_kept, b_kept) =
        unchanged(a, b).unwrap_or_else(|| (vec![false; a.len()], vec![false; b.len()]));

    let mut marks = vec![Mark::Same; new.len()];
    let (mut i, mut j) = (0, 0);
    while i < a.len() || j < b.len() {
        if i < a.len() && j < b.len() && a_kept[i] && b_kept[j] {
            i += 1;
            j += 1;
            continue;
        }
        // A stretch that differs: some old lines gone, some new ones here.
        let (removed_from, added_from) = (i, j);
        while i < a.len() && !a_kept[i] {
            i += 1;
        }
        while j < b.len() && !b_kept[j] {
            j += 1;
        }
        let at = prefix + added_from;
        if j > added_from {
            let mark = if i > removed_from { Mark::Modified } else { Mark::Added };
            marks[at..prefix + j].fill(mark);
        } else if at > 0 {
            if marks[at - 1] == Mark::Same {
                marks[at - 1] = Mark::RemovedBelow;
            }
        } else if let Some(first) = marks.first_mut() {
            *first = Mark::RemovedAbove;
        }
    }
    marks
}

/// Finds the lines `a` and `b` have in common, in order (Myers' algorithm).
/// Returns, for each line of `a` and of `b`, whether it is one of them, or
/// `None` when the two differ by more than `MAX_DIFFERENCES` lines.
fn unchanged(a: &[String], b: &[String]) -> Option<(Vec<bool>, Vec<bool>)> {
    let (n, m) = (a.len() as isize, b.len() as isize);
    let limit = MAX_DIFFERENCES.min(n + m);
    // `reach[k]` is how far along `a` the best path on diagonal `k` has
    // got, where diagonal `k` holds the points with x - y = k.
    let middle = limit + 1;
    let mut reach = vec![0isize; (2 * limit + 3) as usize];
    let at = |k: isize| (middle + k) as usize;
    // What `reach` held before each round, to walk the path back afterwards.
    let mut history: Vec<Vec<isize>> = Vec::new();

    for d in 0..=limit {
        history.push(reach[at(-d - 1)..=at(d + 1)].to_vec());
        for k in (-d..=d).step_by(2) {
            let down = k == -d || (k != d && reach[at(k - 1)] < reach[at(k + 1)]);
            let mut x = if down { reach[at(k + 1)] } else { reach[at(k - 1)] + 1 };
            let mut y = x - k;
            while x < n && y < m && a[x as usize] == b[y as usize] {
                x += 1;
                y += 1;
            }
            reach[at(k)] = x;
            if x >= n && y >= m {
                return Some(walk_back(&history, n, m));
            }
        }
    }
    None
}

/// Follows the path found by `unchanged` from the end back to the start,
/// noting the lines it passed over unchanged.
fn walk_back(history: &[Vec<isize>], n: isize, m: isize) -> (Vec<bool>, Vec<bool>) {
    let mut a_kept = vec![false; n as usize];
    let mut b_kept = vec![false; m as usize];
    let (mut x, mut y) = (n, m);
    for d in (0..history.len() as isize).rev() {
        // Round `d` saved diagonals -d-1..=d+1, so diagonal k is at k+d+1.
        let before = |k: isize| history[d as usize][(k + d + 1) as usize];
        let k = x - y;
        let (from_x, from_y) = if d == 0 {
            (0, 0)
        } else {
            let down = k == -d || (k != d && before(k - 1) < before(k + 1));
            let from_k = if down { k + 1 } else { k - 1 };
            (before(from_k), before(from_k) - from_k)
        };
        while x > from_x && y > from_y {
            x -= 1;
            y -= 1;
            a_kept[x as usize] = true;
            b_kept[y as usize] = true;
        }
        (x, y) = (from_x, from_y);
    }
    (a_kept, b_kept)
}