quvyta-cli 0.1.0-alpha.5

//! A small line diff for the edit preview.
//!
//! An edit changes one region, so the common start and end are taken off first and only the
//! middle is compared with a longest-common-subsequence table. An edit that changes nothing but
//! line endings is looked at separately: a line without its ending is the same whatever follows
//! it, so the table would find no change there and the card would ask for a write with nothing
//! on it.

use super::{Change, DiffLine};

/// Past this many table cells the middle is shown as all removed, then all added: correct,
/// only less precise, and the preview stays quick on a huge file.
const MAX_CELLS: usize = 4_000_000;

/// What git writes under a line whose file does not end in a newline, so the card says it the
/// way the diffs people already read do.
const NO_NEWLINE: &str = r"\ No newline at end of file";

/// The sign for a carriage return: a line ending in `\r\n` looks exactly like one ending in `\n`
/// once the ending is taken away.
const CARRIAGE_RETURN: char = '\u{240d}';

/// The changed region of `before` → `after` with up to `context` unchanged lines on each side.
/// Empty when nothing changed.
pub(super) fn diff(before: &str, after: &str, context: usize) -> Vec<DiffLine> {
    let old: Vec<&str> = before.lines().collect();
    let new: Vec<&str> = after.lines().collect();
    if old == new {
        if before == after {
            return Vec::new();
        }
        // The only edit left is one of line endings: a newline added or taken away at the end of
        // the file, or `\r\n` turned into `\n`. The texts are compared again with their endings,
        // so the person sees what they are allowing instead of an empty card.
        return endings(before, after, context);
    }
    let prefix = old.iter().zip(&new).take_while(|(a, b)| a == b).count();
    let room = old.len().min(new.len()) - prefix;
    let suffix = old.iter().rev().zip(new.iter().rev()).take(room).take_while(|(a, b)| a == b).count();
    let mut out = Vec::new();
    push(&mut out, Change::Same, &old[prefix.saturating_sub(context)..prefix]);
    middle(&old[prefix..old.len() - suffix], &new[prefix..new.len() - suffix], &mut out);
    let tail = old.len() - suffix;
    push(&mut out, Change::Same, &old[tail..tail + suffix.min(context)]);
    out
}

fn push(out: &mut Vec<DiffLine>, change: Change, lines: &[&str]) {
    out.extend(lines.iter().map(|text| DiffLine { change, text: (*text).to_owned() }));
}

/// The same shape of output for a change that is only in the line endings: the first and last
/// lines that really differ, as many unchanged lines around them as asked for, and the endings
/// written out, since a line is otherwise shown the same however it ends.
fn endings(before: &str, after: &str, context: usize) -> Vec<DiffLine> {
    // Both texts have as many lines with their endings as they have without, so the lists are the
    // same length and every position can be read in both.
    let old: Vec<&str> = before.split_inclusive('\n').collect();
    let new: Vec<&str> = after.split_inclusive('\n').collect();
    let mut out = Vec::new();
    let Some(first) = old.iter().zip(&new).position(|(a, b)| a != b) else {
        return out;
    };
    let last = (first..old.len()).rev().find(|at| old[*at] != new[*at]).unwrap_or(first);
    let tail = last + 1;
    push_ending(&mut out, Change::Same, &old[first.saturating_sub(context)..first]);
    push_ending(&mut out, Change::Removed, &old[first..=last]);
    push_ending(&mut out, Change::Added, &new[first..=last]);
    push_ending(&mut out, Change::Same, &old[tail..(tail + context).min(old.len())]);
    out
}

/// Pushes `lines` as the card shows them: the text without its ending, a `␍` after a carriage
/// return, and git's own `\ No newline at end of file` under a last line that has no newline at
/// all, tagged the same way as the line it belongs to.
fn push_ending(out: &mut Vec<DiffLine>, change: Change, lines: &[&str]) {
    for line in lines {
        if let Some(text) = line.strip_suffix("\r\n") {
            out.push(DiffLine { change, text: format!("{text} {CARRIAGE_RETURN}") });
        } else {
            out.push(DiffLine { change, text: line.strip_suffix('\n').unwrap_or(line).to_owned() });
            if !line.ends_with('\n') {
                out.push(DiffLine { change, text: NO_NEWLINE.to_owned() });
            }
        }
    }
}

fn middle(old: &[&str], new: &[&str], out: &mut Vec<DiffLine>) {
    if old.len().saturating_mul(new.len()) > MAX_CELLS {
        push(out, Change::Removed, old);
        push(out, Change::Added, new);
        return;
    }
    // common[i * width + j] is the length of the longest common run of old[i..] and new[j..].
    let width = new.len() + 1;
    let mut common = vec![0_u32; (old.len() + 1) * width];
    for i in (0..old.len()).rev() {
        for j in (0..new.len()).rev() {
            common[i * width + j] = if old[i] == new[j] {
                common[(i + 1) * width + j + 1] + 1
            } else {
                common[(i + 1) * width + j].max(common[i * width + j + 1])
            };
        }
    }
    let (mut i, mut j) = (0, 0);
    while i < old.len() && j < new.len() {
        if old[i] == new[j] {
            push(out, Change::Same, &old[i..=i]);
            i += 1;
            j += 1;
        } else if common[(i + 1) * width + j] >= common[i * width + j + 1] {
            push(out, Change::Removed, &old[i..=i]);
            i += 1;
        } else {
            push(out, Change::Added, &new[j..=j]);
            j += 1;
        }
    }
    push(out, Change::Removed, &old[i..]);
    push(out, Change::Added, &new[j..]);
}