wsb 0.255.6379

//! A real line diff, because a replacement is not a line-for-line rewrite.
//!
//! It is tempting to assume line N before is line N after — a replacement
//! rewrites a line in place, so surely nothing moves. It does not hold. A
//! substitute can contain newlines and split one line into five; a regular
//! expression can match across lines and collapse five into one; a replacement
//! can delete a line entirely. Any of those shifts every line after it, and a
//! preview that assumed otherwise would show a reader the wrong lines with
//! confident numbers on them.
//!
//! So the lines are actually diffed. Myers' algorithm, which finds a shortest
//! edit script in O((N+M)·D) where D is the number of edits — proportional to
//! what the refactor changed, not to the size of the file. A common prefix and
//! suffix are trimmed first, which is nearly all of a refactored file.

use serde::{Deserialize, Serialize};

/// One line of a file, as the preview shows it.
///
/// A removed line has a number in the file as it is; an added line has one in
/// the file as it would be. Neither has both, and pretending otherwise is how
/// a diff acquires line numbers that point at nothing.
#[derive(Debug, Clone, Serialize, Deserialize, PartialEq)]
#[serde(tag = "kind", rename_all = "snake_case")]
pub enum DiffLine {
    Context {
        old: usize,
        new: usize,
        text: String,
        /// True when this line ends the file without a newline. Shown, because
        /// adding or removing a final newline is a real change to the bytes.
        #[serde(default, skip_serializing_if = "std::ops::Not::not")]
        no_newline: bool,
    },
    Removed {
        old: usize,
        text: String,
        #[serde(default, skip_serializing_if = "std::ops::Not::not")]
        no_newline: bool,
    },
    Added {
        new: usize,
        text: String,
        #[serde(default, skip_serializing_if = "std::ops::Not::not")]
        no_newline: bool,
    },
}

/// A run of changes with the unchanged lines around it.
#[derive(Debug, Clone, Serialize, Deserialize, PartialEq)]
pub struct Hunk {
    /// 1-based line the hunk starts at in the file as it is.
    pub old_start: usize,
    /// 1-based line the hunk starts at in the file as it would be.
    pub new_start: usize,
    pub lines: Vec<DiffLine>,
}

/// How many unchanged lines are shown either side of a change by default.
pub const DEFAULT_CONTEXT: usize = 3;

/// One step of an edit script.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Step {
    Keep,
    Remove,
    Insert,
}

/// One step of an edit script, carrying the line an insert brings with it.
///
/// The internal form is positional — it is walked alongside both files at
/// once, so it does not need to carry text. A caller that wants the script on
/// its own does, or it has an `Insert` naming nothing.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Edit {
    Keep,
    Remove,
    Insert(String),
}

/// The most edits that will be searched for before giving up.
///
/// Myers costs O((N+M)·D). D is the edit distance, which for a refactor is the
/// handful of lines it changed — but a file replaced wholesale has a D the
/// size of the file, and a diff nobody asked for must not become the slowest
/// thing in the run. Past this the answer is refused and SAID, rather than
/// quietly turned into something cheaper and wrong.
const MAX_EDITS: usize = 20_000;

/// Split into lines, each keeping its own terminator.
///
/// `str::lines` throws the terminator away, and then `"a\n"` and `"a"` are the
/// same list — so a refactor that removed the final newline produced an empty
/// diff. Keeping it makes the last line genuinely different, which is what it
/// is. An empty text has no lines at all, not one empty one.
fn split(text: &str) -> Vec<&str> {
    let mut lines = Vec::new();
    let mut rest = text;
    while !rest.is_empty() {
        match rest.find('\n') {
            Some(at) => {
                lines.push(&rest[..=at]);
                rest = &rest[at + 1..];
            }
            None => {
                lines.push(rest);
                rest = "";
            }
        }
    }
    lines
}

/// A line as it is shown: without its terminator, and whether it had one.
fn displayed(line: &str) -> (String, bool) {
    match line.strip_suffix('\n') {
        // The carriage return of a CRLF file belongs to the terminator too;
        // left in, every line of such a file would render with a stray glyph.
        Some(body) => (body.strip_suffix('\r').unwrap_or(body).to_string(), false),
        None => (line.to_string(), true),
    }
}

/// The hunks between two texts, with `context` unchanged lines around each.
pub fn hunks(before: &str, after: &str, context: usize) -> Result<Vec<Hunk>, String> {
    let old: Vec<&str> = split(before);
    let new: Vec<&str> = split(after);
    let script = edit_script(&old, &new)?;
    Ok(assemble(&old, &new, &script, context))
}

/// The shortest edit script turning `before` into `after`, as lines.
///
/// The same search the diff uses, handed over as a script rather than
/// assembled into hunks — a three-way merge needs to know which lines each
/// side changed, not how to display them.
pub fn script(before: &[&str], after: &[&str]) -> Result<Vec<Edit>, String> {
    let steps = edit_script(before, after)?;
    let mut edits = Vec::with_capacity(steps.len());
    let mut new_index = 0;
    for step in steps {
        match step {
            Step::Keep => {
                new_index += 1;
                edits.push(Edit::Keep);
            }
            Step::Remove => edits.push(Edit::Remove),
            Step::Insert => {
                edits.push(Edit::Insert(after[new_index].to_string()));
                new_index += 1;
            }
        }
    }
    Ok(edits)
}

/// A shortest edit script turning `old` into `new`.
fn edit_script(old: &[&str], new: &[&str]) -> Result<Vec<Step>, String> {
    // Trim what is identical at each end. For a refactored file this is nearly
    // everything, and it is what keeps D small enough for Myers to be quick.
    let mut head = 0;
    while head < old.len() && head < new.len() && old[head] == new[head] {
        head += 1;
    }
    let mut tail = 0;
    while tail < old.len().saturating_sub(head) && tail < new.len().saturating_sub(head)
        && old[old.len() - 1 - tail] == new[new.len() - 1 - tail]
    {
        tail += 1;
    }

    let middle = myers(&old[head..old.len() - tail], &new[head..new.len() - tail])?;

    let mut script = vec![Step::Keep; head];
    script.extend(middle);
    script.extend(std::iter::repeat_n(Step::Keep, tail));
    Ok(script)
}

/// Myers' shortest-edit-script search, with the trace kept for backtracking.
fn myers(old: &[&str], new: &[&str]) -> Result<Vec<Step>, String> {
    let n = old.len();
    let m = new.len();
    if n == 0 {
        return Ok(vec![Step::Insert; m]);
    }
    if m == 0 {
        return Ok(vec![Step::Remove; n]);
    }

    let max = n + m;
    if max > MAX_EDITS {
        return Err(format!(
            "these two versions differ by more than {MAX_EDITS} lines, which is past what this \
             will diff. The change is still listed and still applies; only the line-by-line \
             view is refused."
        ));
    }

    let offset = max as isize;
    // `v[k + offset]` is the furthest x reached on diagonal k.
    let mut v = vec![0isize; 2 * max + 1];
    let mut trace: Vec<Vec<isize>> = Vec::new();

    for d in 0..=max as isize {
        trace.push(v.clone());
        let mut k = -d;
        while k <= d {
            let index = (k + offset) as usize;
            // Which move reached this diagonal: down (an insert) or right (a
            // removal). At the edges there is only one choice.
            let mut x = if k == -d || (k != d && v[index - 1] < v[index + 1]) {
                v[index + 1]
            } else {
                v[index - 1] + 1
            };
            let mut y = x - k;
            // Follow the diagonal as far as the lines agree — free moves.
            while (x as usize) < n && (y as usize) < m && old[x as usize] == new[y as usize] {
                x += 1;
                y += 1;
            }
            v[index] = x;
            if x as usize >= n && y as usize >= m {
                return Ok(backtrack(old, new, &trace, d, offset));
            }
            k += 2;
        }
    }
    // Unreachable: d reaches n + m, which always suffices. Said rather than
    // silently returning an empty script that would render as "no changes".
    Err("the diff did not converge, which should be impossible".to_string())
}

/// Walk the recorded traces backwards into an edit script.
fn backtrack(
    old: &[&str],
    new: &[&str],
    trace: &[Vec<isize>],
    d: isize,
    offset: isize,
) -> Vec<Step> {
    let mut steps = Vec::new();
    let mut x = old.len() as isize;
    let mut y = new.len() as isize;

    for (depth, v) in trace.iter().enumerate().take(d as usize + 1).rev() {
        let depth = depth as isize;
        let k = x - y;
        let index = (k + offset) as usize;
        let previous_k = if k == -depth || (k != depth && v[index - 1] < v[index + 1]) {
            k + 1
        } else {
            k - 1
        };
        let previous_x = v[(previous_k + offset) as usize];
        let previous_y = previous_x - previous_k;

        // The free diagonal moves first: they are the lines both sides share.
        while x > previous_x && y > previous_y {
            steps.push(Step::Keep);
            x -= 1;
            y -= 1;
        }
        if depth == 0 {
            break;
        }
        if x == previous_x {
            steps.push(Step::Insert);
            y -= 1;
        } else {
            steps.push(Step::Remove);
            x -= 1;
        }
    }

    debug_assert!(x == 0 && y == 0, "backtrack must reach the origin");
    let _ = (old, new);
    steps.reverse();
    steps
}

/// Turn an edit script into hunks, with `context` unchanged lines around each.
fn assemble(old: &[&str], new: &[&str], script: &[Step], context: usize) -> Vec<Hunk> {
    // Which script positions are changes, so context can be measured in
    // script positions rather than in either file's numbering.
    let changed: Vec<bool> = script.iter().map(|s| *s != Step::Keep).collect();
    if !changed.iter().any(|c| *c) {
        return Vec::new();
    }

    // Every position within `context` of a change is shown.
    let mut shown = vec![false; script.len()];
    for (index, is_change) in changed.iter().enumerate() {
        if !is_change {
            continue;
        }
        let from = index.saturating_sub(context);
        let to = (index + context).min(script.len() - 1);
        for position in shown.iter_mut().take(to + 1).skip(from) {
            *position = true;
        }
    }

    let mut hunks: Vec<Hunk> = Vec::new();
    let mut old_line = 1usize;
    let mut new_line = 1usize;
    let mut open = false;

    for (index, step) in script.iter().enumerate() {
        if shown[index] && !open {
            hunks.push(Hunk {
                old_start: old_line,
                new_start: new_line,
                lines: Vec::new(),
            });
            open = true;
        } else if !shown[index] && open {
            open = false;
        }

        if shown[index] {
            let hunk = hunks.last_mut().expect("a hunk is open");
            match step {
                Step::Keep => {
                    let (text, no_newline) = displayed(old[old_line - 1]);
                    hunk.lines.push(DiffLine::Context {
                        old: old_line,
                        new: new_line,
                        text,
                        no_newline,
                    });
                }
                Step::Remove => {
                    let (text, no_newline) = displayed(old[old_line - 1]);
                    hunk.lines.push(DiffLine::Removed {
                        old: old_line,
                        text,
                        no_newline,
                    });
                }
                Step::Insert => {
                    let (text, no_newline) = displayed(new[new_line - 1]);
                    hunk.lines.push(DiffLine::Added {
                        new: new_line,
                        text,
                        no_newline,
                    });
                }
            }
        }

        match step {
            Step::Keep => {
                old_line += 1;
                new_line += 1;
            }
            Step::Remove => old_line += 1,
            Step::Insert => new_line += 1,
        }
    }
    hunks
}

#[cfg(test)]
#[path = "textdiff_tests.rs"]
mod textdiff_tests;