crates/hub/src/render/diff.rs at 9a777fec4ed9 · andymccall/oxygenhub

# 9a777fec4ed9 oxygenhub / crates / hub / src / render / diff.rs

16.1 KiB · Rust · last changed Diffs: word marks, whitespace, split view, collapsing 1 month ago source blame history raw

//! Diff rendering: `oxy`'s per-file hunks become unified rows with
//! context, and two snapshots become per-file hunks.

use oxy_core::repo::{DiffHunk, FileDiff};
use oxy_core::state::{FileContent, Snapshot};
use similar::{Algorithm, DiffOp};
use std::collections::BTreeMap;

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Kind {
    Context,
    Add,
    Del,
    /// Elided lines between hunks.
    Gap,
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Line {
    pub kind: Kind,
    pub old_no: Option<u32>,
    pub new_no: Option<u32>,
    /// Raw text, not escaped.
    pub text: String,
    /// For a changed line paired with its counterpart: the text in runs,
    /// marking the words that changed. Empty means show `text` as is.
    pub segments: Vec<Segment>,
}

/// A run of a changed line's text.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Segment {
    pub text: String,
    pub changed: bool,
}

/// How to render a diff.
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub struct Options {
    /// Treat lines that differ only in whitespace as unchanged (`?w=1`).
    pub ignore_whitespace: bool,
}

impl Line {
    fn new(kind: Kind, old_no: Option<u32>, new_no: Option<u32>, text: String) -> Line {
        Line { kind, old_no, new_no, text, segments: vec![] }
    }
}

impl Kind {
    pub fn class(self) -> &'static str {
        match self {
            Kind::Context => "ctx",
            Kind::Add => "add",
            Kind::Del => "del",
            Kind::Gap => "gap",
        }
    }

    pub fn sign(self) -> &'static str {
        match self {
            Kind::Context => " ",
            Kind::Add => "+",
            Kind::Del => "-",
            Kind::Gap => "…",
        }
    }
}

fn text(b: &[u8]) -> String {
    String::from_utf8_lossy(b).trim_end_matches(['\n', '\r']).to_string()
}

/// Unified rows for one file: `base` is the file before the change (empty
/// for an added file) and `hunks` come from `oxy diff`, whose `base_line`
/// is the 1-based line the additions follow (0 = before the first line).
pub fn unified(base: &[u8], hunks: &[DiffHunk], context: usize) -> Vec<Line> {
    unified_with(base, hunks, context, Options::default())
}

/// `unified`, with options, and changed lines refined word by word.
pub fn unified_with(base: &[u8], hunks: &[DiffHunk], context: usize, opts: Options) -> Vec<Line> {
    let base_lines: Vec<String> = oxy_core::diff::split_lines(base).into_iter().map(text).collect();
    // Turn hunks into a per-old-line plan: removed set, and additions keyed
    // by the base line they follow.
    let mut removed = std::collections::HashSet::new();
    let mut added: BTreeMap<u32, Vec<String>> = BTreeMap::new();
    for h in hunks {
        for (line, _) in &h.removed {
            removed.insert(*line);
        }
        added.entry(h.base_line).or_default().extend(h.added.iter().map(|b| text(b)));
    }
    // Walk the base, emitting rows; then trim to context around changes.
    let mut rows: Vec<Line> = Vec::new();
    let mut new_no: u32 = 0;
    if let Some(lines) = added.get(&0) {
        for l in lines {
            new_no += 1;
            rows.push(Line::new(Kind::Add, None, Some(new_no), l.clone()));
        }
    }
    for (i, l) in base_lines.iter().enumerate() {
        let old_no = i as u32 + 1;
        if removed.contains(&old_no) {
            rows.push(Line::new(Kind::Del, Some(old_no), None, l.clone()));
        } else {
            new_no += 1;
            rows.push(Line::new(Kind::Context, Some(old_no), Some(new_no), l.clone()));
        }
        if let Some(lines) = added.get(&old_no) {
            for a in lines {
                new_no += 1;
                rows.push(Line::new(Kind::Add, None, Some(new_no), a.clone()));
            }
        }
    }
    // Any additions anchored past the end (defensive).
    for (anchor, lines) in &added {
        if *anchor as usize > base_lines.len() {
            for a in lines {
                new_no += 1;
                rows.push(Line::new(Kind::Add, None, Some(new_no), a.clone()));
            }
        }
    }
    with_context(refine(rows, opts), context)
}

/// Pair the removed and added lines of each block of changes, line by
/// line. A pair that differs only in whitespace becomes one
/// context line when whitespace is ignored; otherwise a similar pair gets
/// word-level segments so the page can mark what changed within it.
fn refine(rows: Vec<Line>, opts: Options) -> Vec<Line> {
    let mut out: Vec<Line> = Vec::with_capacity(rows.len());
    let mut i = 0;
    while i < rows.len() {
        let changed = |k: usize| matches!(rows[k].kind, Kind::Del | Kind::Add);
        if !changed(i) {
            out.push(rows[i].clone());
            i += 1;
            continue;
        }
        // One block of changed lines, whichever order oxy's hunks put them
        // in; it is shown removals first, then additions.
        let end = (i..rows.len()).find(|&k| !changed(k)).unwrap_or(rows.len());
        let mut dels: Vec<Line> = rows[i..end].iter().filter(|l| l.kind == Kind::Del).cloned().collect();
        let mut adds: Vec<Line> = rows[i..end].iter().filter(|l| l.kind == Kind::Add).cloned().collect();
        let adds_end = end;
        let pairs = dels.len().min(adds.len());
        let mut same_but_space = vec![false; pairs];
        for k in 0..pairs {
            if opts.ignore_whitespace && squash(&dels[k].text) == squash(&adds[k].text) {
                same_but_space[k] = true;
            } else if let Some((d, a)) = words(&dels[k].text, &adds[k].text) {
                dels[k].segments = d;
                adds[k].segments = a;
            }
        }
        if same_but_space.iter().any(|x| *x) {
            // Keep the file's order: changed lines before an unchanged pair
            // come out as removals then additions, then the pair as context.
            let (mut pd, mut pa): (Vec<Line>, Vec<Line>) = (Vec::new(), Vec::new());
            for k in 0..pairs {
                if same_but_space[k] {
                    out.append(&mut pd);
                    out.append(&mut pa);
                    out.push(Line::new(Kind::Context, dels[k].old_no, adds[k].new_no, adds[k].text.clone()));
                } else {
                    pd.push(dels[k].clone());
                    pa.push(adds[k].clone());
                }
            }
            out.append(&mut pd);
            out.extend(dels.drain(pairs..));
            out.append(&mut pa);
            out.extend(adds.drain(pairs..));
        } else {
            out.extend(dels);
            out.extend(adds);
        }
        i = adds_end;
    }
    out
}

/// A line split into identifiers, whitespace runs and single other
/// characters, so `42;` changing to `43;` marks only the number.
fn tokens(s: &str) -> Vec<&str> {
    let mut out = Vec::new();
    let mut start = 0;
    let class = |c: char| {
        if c.is_alphanumeric() || c == '_' {
            0
        } else if c.is_whitespace() {
            1
        } else {
            2
        }
    };
    let mut prev: Option<u8> = None;
    for (i, c) in s.char_indices() {
        let k = class(c);
        if prev.is_some_and(|p| p != k || k == 2) {
            out.push(&s[start..i]);
            start = i;
        }
        prev = Some(k);
    }
    if start < s.len() {
        out.push(&s[start..]);
    }
    out
}

/// Text with every run of whitespace removed, for comparing ignoring it.
fn squash(s: &str) -> String {
    s.split_whitespace().collect()
}

/// Word-level runs of an old and a new line, or None when the lines share
/// too little for marking words to help (then the whole line reads as changed).
fn words(old: &str, new: &str) -> Option<(Vec<Segment>, Vec<Segment>)> {
    if old.len() + new.len() > 2_000 {
        return None;
    }
    let (ot, nt) = (tokens(old), tokens(new));
    let diff = similar::TextDiff::configure().algorithm(Algorithm::Patience).diff_slices(&ot, &nt);
    if diff.ratio() < 0.4 {
        return None;
    }
    let (mut d, mut a) = (Vec::new(), Vec::new());
    let push = |v: &mut Vec<Segment>, text: &str, changed: bool| match v.last_mut() {
        Some(last) if last.changed == changed => last.text.push_str(text),
        _ => v.push(Segment { text: text.to_string(), changed }),
    };
    for change in diff.iter_all_changes() {
        match change.tag() {
            similar::ChangeTag::Equal => {
                push(&mut d, change.value(), false);
                push(&mut a, change.value(), false);
            }
            similar::ChangeTag::Delete => push(&mut d, change.value(), true),
            similar::ChangeTag::Insert => push(&mut a, change.value(), true),
        }
    }
    Some((d, a))
}

/// Keep `context` rows around every change, replacing longer runs with a gap.
fn with_context(rows: Vec<Line>, context: usize) -> Vec<Line> {
    let changed: Vec<bool> = rows.iter().map(|r| r.kind != Kind::Context).collect();
    let mut keep = vec![false; rows.len()];
    for (i, c) in changed.iter().enumerate() {
        if *c {
            let lo = i.saturating_sub(context);
            let hi = (i + context + 1).min(rows.len());
            for k in keep.iter_mut().take(hi).skip(lo) {
                *k = true;
            }
        }
    }
    let mut out = Vec::new();
    let mut gap = 0;
    for (row, k) in rows.into_iter().zip(keep) {
        if k {
            if gap > 0 {
                out.push(Line::new(Kind::Gap, None, None, format!("{gap} unchanged lines")));
                gap = 0;
            }
            out.push(row);
        } else {
            gap += 1;
        }
    }
    if gap > 0 {
        out.push(Line::new(Kind::Gap, None, None, format!("{gap} unchanged lines")));
    }
    out
}

/// Hunks between two texts, in `oxy diff`'s shape.
pub fn hunks_between(old: &[u8], new: &[u8]) -> Vec<DiffHunk> {
    let old_lines = oxy_core::diff::split_lines(old);
    let new_lines = oxy_core::diff::split_lines(new);
    let ops = similar::capture_diff_slices(Algorithm::Myers, &old_lines, &new_lines);
    let mut hunks: Vec<DiffHunk> = Vec::new();
    for op in ops {
        match op {
            DiffOp::Equal { .. } => {}
            DiffOp::Delete { old_index, old_len, .. } => {
                hunks.push(DiffHunk {
                    base_line: (old_index + old_len) as u32,
                    added: vec![],
                    removed: (old_index..old_index + old_len).map(|i| (i as u32 + 1, old_lines[i].to_vec())).collect(),
                });
            }
            DiffOp::Insert { old_index, new_index, new_len } => {
                hunks.push(DiffHunk {
                    base_line: old_index as u32,
                    added: (new_index..new_index + new_len).map(|i| new_lines[i].to_vec()).collect(),
                    removed: vec![],
                });
            }
            DiffOp::Replace { old_index, old_len, new_index, new_len } => {
                hunks.push(DiffHunk {
                    base_line: (old_index + old_len) as u32,
                    added: (new_index..new_index + new_len).map(|i| new_lines[i].to_vec()).collect(),
                    removed: (old_index..old_index + old_len).map(|i| (i as u32 + 1, old_lines[i].to_vec())).collect(),
                });
            }
        }
    }
    hunks
}

/// The per-file diff of one change against its base state (what
/// `oxy diff CHANGE` shows), using an already loaded base.
pub fn change_files(change: &oxy_core::objects::Change, base: &oxy_core::state::State, base_snapshot: &Snapshot) -> Vec<FileDiff> {
    oxy_core::repo::diff_files_of(change, base, base_snapshot)
}

/// Every file that differs between two snapshots, with the base content
/// of files present in both (for context).
pub fn snapshot_diff(base: &Snapshot, head: &Snapshot) -> (Vec<FileDiff>, BTreeMap<String, Vec<u8>>) {
    let mut files = Vec::new();
    let mut bases = BTreeMap::new();
    let text_of = |f: &oxy_core::state::FileState| match &f.content {
        FileContent::Text { bytes, .. } => Some(bytes.clone()),
        _ => None,
    };
    for (path, hf) in &head.files {
        if hf.kind == oxy_core::objects::NodeKind::Dir {
            continue;
        }
        match base.files.get(path) {
            None => {
                let new = text_of(hf).unwrap_or_default();
                files.push(FileDiff { path: path.clone(), kind: "added".into(), hunks: hunks_between(b"", &new), from: None });
            }
            Some(bf) => {
                let (old, new) = (text_of(bf), text_of(hf));
                if old != new {
                    let old_b = old.clone().unwrap_or_default();
                    let hunks = hunks_between(&old_b, &new.unwrap_or_default());
                    if let Some(o) = old {
                        bases.insert(path.clone(), o);
                    }
                    files.push(FileDiff { path: path.clone(), kind: "modified".into(), hunks, from: None });
                } else if bf.mode != hf.mode {
                    files.push(FileDiff { path: path.clone(), kind: "mode".into(), hunks: vec![], from: None });
                }
            }
        }
    }
    for (path, bf) in &base.files {
        if bf.kind != oxy_core::objects::NodeKind::Dir && !head.files.contains_key(path) {
            let old = text_of(bf).unwrap_or_default();
            bases.insert(path.clone(), old.clone());
            files.push(FileDiff { path: path.clone(), kind: "removed".into(), hunks: hunks_between(&old, b""), from: None });
        }
    }
    files.sort_by(|a, b| a.path.cmp(&b.path));
    (files, bases)
}

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

    #[test]
    fn unified_rows_with_context() {
        let base = b"a\nb\nc\nd\ne\nf\ng\nh\n";
        let hunks = hunks_between(base, b"a\nb\nc\nX\ne\nf\ng\nh\nZ\n");
        let rows = unified(base, &hunks, 1);
        let s: Vec<String> = rows.iter().map(|r| format!("{}{}", r.kind.sign(), r.text)).collect();
        assert_eq!(s, ["…2 unchanged lines", " c", "-d", "+X", " e", "…2 unchanged lines", " h", "+Z"]);
        assert_eq!(rows[2].old_no, Some(4));
        assert_eq!(rows[3].new_no, Some(4));
        assert_eq!(rows.last().unwrap().new_no, Some(9));
    }

    #[test]
    fn added_file() {
        let hunks = hunks_between(b"", b"one\ntwo\n");
        let rows = unified(b"", &hunks, 3);
        assert_eq!(rows.iter().map(|r| r.kind).collect::<Vec<_>>(), [Kind::Add, Kind::Add]);
    }
}

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

    fn rows(base: &str, new: &str, opts: Options) -> Vec<Line> {
        unified_with(base.as_bytes(), &hunks_between(base.as_bytes(), new.as_bytes()), 3, opts)
    }

    #[test]
    fn changed_words_are_marked_within_a_line() {
        let r = rows("let answer = 42;\n", "let answer = 43;\n", Options::default());
        let del = r.iter().find(|l| l.kind == Kind::Del).unwrap();
        let add = r.iter().find(|l| l.kind == Kind::Add).unwrap();
        assert_eq!(del.segments.iter().filter(|s| s.changed).map(|s| s.text.as_str()).collect::<Vec<_>>(), ["42"]);
        assert_eq!(add.segments.iter().filter(|s| s.changed).map(|s| s.text.as_str()).collect::<Vec<_>>(), ["43"]);
        assert_eq!(add.segments.iter().map(|s| s.text.as_str()).collect::<String>(), add.text, "segments cover the line");
        // Lines with nothing in common are not broken into words.
        let r = rows("alpha beta\n", "gamma delta\n", Options::default());
        assert!(r.iter().all(|l| l.segments.is_empty()));
    }

    #[test]
    fn whitespace_changes_can_be_hidden() {
        let base = "fn main() {\n  a();\n  b();\n}\n";
        let new = "fn main() {\n    a();\n    c();\n}\n";
        let shown = rows(base, new, Options::default());
        assert_eq!(shown.iter().filter(|l| l.kind == Kind::Add).count(), 2);
        let hidden = rows(base, new, Options { ignore_whitespace: true });
        let kinds: Vec<(Kind, &str)> = hidden.iter().map(|l| (l.kind, l.text.trim())).collect();
        assert_eq!(
            kinds,
            [(Kind::Context, "fn main() {"), (Kind::Context, "a();"), (Kind::Del, "b();"), (Kind::Add, "c();"), (Kind::Context, "}")],
            "only the real change remains, in order"
        );
        let ctx = hidden.iter().find(|l| l.text.trim() == "a();").unwrap();
        assert_eq!((ctx.old_no, ctx.new_no), (Some(2), Some(2)));
    }
}

`/`	Search
`g` `c`	Code
`g` `h`	History
`g` `b`	Bookmarks
`g` `t`	Trust
`y`	Permalink to this state (files and trees)
`?`	This sheet

d23464c0 Andy McCall 1 month ago ↶	1	//! Diff rendering: `oxy`'s per-file hunks become unified rows with
	2	//! context, and two snapshots become per-file hunks.
	3
	4	use oxy_core::repo::{DiffHunk, FileDiff};
	5	use oxy_core::state::{FileContent, Snapshot};
	6	use similar::{Algorithm, DiffOp};
	7	use std::collections::BTreeMap;
	8
	9	#[derive(Clone, Copy, Debug, PartialEq, Eq)]
	10	pub enum Kind {
	11	Context,
	12	Add,
	13	Del,
	14	/// Elided lines between hunks.
	15	Gap,
	16	}
	17
	18	#[derive(Clone, Debug, PartialEq, Eq)]
	19	pub struct Line {
	20	pub kind: Kind,
	21	pub old_no: Option<u32>,
	22	pub new_no: Option<u32>,
	23	/// Raw text, not escaped.
	24	pub text: String,
9df855f2 Andy McCall 1 month ago ↶	25	/// For a changed line paired with its counterpart: the text in runs,
	26	/// marking the words that changed. Empty means show `text` as is.
	27	pub segments: Vec<Segment>,
	28	}
	29
	30	/// A run of a changed line's text.
	31	#[derive(Clone, Debug, PartialEq, Eq)]
	32	pub struct Segment {
	33	pub text: String,
	34	pub changed: bool,
	35	}
	36
	37	/// How to render a diff.
	38	#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
	39	pub struct Options {
	40	/// Treat lines that differ only in whitespace as unchanged (`?w=1`).
	41	pub ignore_whitespace: bool,
d23464c0 Andy McCall 1 month ago ↶	42	}
d23464c0 Andy McCall 1 month ago ↶	43
9df855f2 Andy McCall 1 month ago ↶	44	impl Line {
	45	fn new(kind: Kind, old_no: Option<u32>, new_no: Option<u32>, text: String) -> Line {
	46	Line { kind, old_no, new_no, text, segments: vec![] }
	47	}
	48	}
	49
d23464c0 Andy McCall 1 month ago ↶	50	impl Kind {
	51	pub fn class(self) -> &'static str {
	52	match self {
	53	Kind::Context => "ctx",
	54	Kind::Add => "add",
	55	Kind::Del => "del",
	56	Kind::Gap => "gap",
	57	}
	58	}
	59
	60	pub fn sign(self) -> &'static str {
	61	match self {
	62	Kind::Context => " ",
	63	Kind::Add => "+",
	64	Kind::Del => "-",
	65	Kind::Gap => "…",
	66	}
	67	}
	68	}
	69
	70	fn text(b: &[u8]) -> String {
	71	String::from_utf8_lossy(b).trim_end_matches(['\n', '\r']).to_string()
	72	}
	73
	74	/// Unified rows for one file: `base` is the file before the change (empty
	75	/// for an added file) and `hunks` come from `oxy diff`, whose `base_line`
	76	/// is the 1-based line the additions follow (0 = before the first line).
	77	pub fn unified(base: &[u8], hunks: &[DiffHunk], context: usize) -> Vec<Line> {
9df855f2 Andy McCall 1 month ago ↶	78	unified_with(base, hunks, context, Options::default())
	79	}
	80
	81	/// `unified`, with options, and changed lines refined word by word.
	82	pub fn unified_with(base: &[u8], hunks: &[DiffHunk], context: usize, opts: Options) -> Vec<Line> {
d23464c0 Andy McCall 1 month ago ↶	83	let base_lines: Vec<String> = oxy_core::diff::split_lines(base).into_iter().map(text).collect();
	84	// Turn hunks into a per-old-line plan: removed set, and additions keyed
	85	// by the base line they follow.
	86	let mut removed = std::collections::HashSet::new();
	87	let mut added: BTreeMap<u32, Vec<String>> = BTreeMap::new();
	88	for h in hunks {
	89	for (line, _) in &h.removed {
	90	removed.insert(*line);
	91	}
	92	added.entry(h.base_line).or_default().extend(h.added.iter().map(\|b\| text(b)));
	93	}
	94	// Walk the base, emitting rows; then trim to context around changes.
	95	let mut rows: Vec<Line> = Vec::new();
	96	let mut new_no: u32 = 0;
	97	if let Some(lines) = added.get(&0) {
	98	for l in lines {
	99	new_no += 1;
9df855f2 Andy McCall 1 month ago ↶	100	rows.push(Line::new(Kind::Add, None, Some(new_no), l.clone()));
d23464c0 Andy McCall 1 month ago ↶	101	}
	102	}
	103	for (i, l) in base_lines.iter().enumerate() {
	104	let old_no = i as u32 + 1;
	105	if removed.contains(&old_no) {
9df855f2 Andy McCall 1 month ago ↶	106	rows.push(Line::new(Kind::Del, Some(old_no), None, l.clone()));
d23464c0 Andy McCall 1 month ago ↶	107	} else {
d23464c0 Andy McCall 1 month ago ↶	108	new_no += 1;
9df855f2 Andy McCall 1 month ago ↶	109	rows.push(Line::new(Kind::Context, Some(old_no), Some(new_no), l.clone()));
d23464c0 Andy McCall 1 month ago ↶	110	}
	111	if let Some(lines) = added.get(&old_no) {
	112	for a in lines {
	113	new_no += 1;
9df855f2 Andy McCall 1 month ago ↶	114	rows.push(Line::new(Kind::Add, None, Some(new_no), a.clone()));
d23464c0 Andy McCall 1 month ago ↶	115	}
	116	}
	117	}
	118	// Any additions anchored past the end (defensive).
	119	for (anchor, lines) in &added {
	120	if *anchor as usize > base_lines.len() {
	121	for a in lines {
	122	new_no += 1;
9df855f2 Andy McCall 1 month ago ↶	123	rows.push(Line::new(Kind::Add, None, Some(new_no), a.clone()));
	124	}
	125	}
	126	}
	127	with_context(refine(rows, opts), context)
	128	}
	129
	130	/// Pair the removed and added lines of each block of changes, line by
	131	/// line. A pair that differs only in whitespace becomes one
	132	/// context line when whitespace is ignored; otherwise a similar pair gets
	133	/// word-level segments so the page can mark what changed within it.
	134	fn refine(rows: Vec<Line>, opts: Options) -> Vec<Line> {
	135	let mut out: Vec<Line> = Vec::with_capacity(rows.len());
	136	let mut i = 0;
	137	while i < rows.len() {
	138	let changed = \|k: usize\| matches!(rows[k].kind, Kind::Del \| Kind::Add);
	139	if !changed(i) {
	140	out.push(rows[i].clone());
	141	i += 1;
	142	continue;
	143	}
	144	// One block of changed lines, whichever order oxy's hunks put them
	145	// in; it is shown removals first, then additions.
	146	let end = (i..rows.len()).find(\|&k\| !changed(k)).unwrap_or(rows.len());
	147	let mut dels: Vec<Line> = rows[i..end].iter().filter(\|l\| l.kind == Kind::Del).cloned().collect();
	148	let mut adds: Vec<Line> = rows[i..end].iter().filter(\|l\| l.kind == Kind::Add).cloned().collect();
	149	let adds_end = end;
	150	let pairs = dels.len().min(adds.len());
	151	let mut same_but_space = vec![false; pairs];
	152	for k in 0..pairs {
	153	if opts.ignore_whitespace && squash(&dels[k].text) == squash(&adds[k].text) {
	154	same_but_space[k] = true;
	155	} else if let Some((d, a)) = words(&dels[k].text, &adds[k].text) {
	156	dels[k].segments = d;
	157	adds[k].segments = a;
d23464c0 Andy McCall 1 month ago ↶	158	}
d23464c0 Andy McCall 1 month ago ↶	159	}
9df855f2 Andy McCall 1 month ago ↶	160	if same_but_space.iter().any(\|x\| *x) {
	161	// Keep the file's order: changed lines before an unchanged pair
	162	// come out as removals then additions, then the pair as context.
	163	let (mut pd, mut pa): (Vec<Line>, Vec<Line>) = (Vec::new(), Vec::new());
	164	for k in 0..pairs {
	165	if same_but_space[k] {
	166	out.append(&mut pd);
	167	out.append(&mut pa);
	168	out.push(Line::new(Kind::Context, dels[k].old_no, adds[k].new_no, adds[k].text.clone()));
	169	} else {
	170	pd.push(dels[k].clone());
	171	pa.push(adds[k].clone());
	172	}
	173	}
	174	out.append(&mut pd);
	175	out.extend(dels.drain(pairs..));
	176	out.append(&mut pa);
	177	out.extend(adds.drain(pairs..));
	178	} else {
	179	out.extend(dels);
	180	out.extend(adds);
	181	}
	182	i = adds_end;
d23464c0 Andy McCall 1 month ago ↶	183	}
9df855f2 Andy McCall 1 month ago ↶	184	out
d23464c0 Andy McCall 1 month ago ↶	185	}
d23464c0 Andy McCall 1 month ago ↶	186
9df855f2 Andy McCall 1 month ago ↶	187	/// A line split into identifiers, whitespace runs and single other
	188	/// characters, so `42;` changing to `43;` marks only the number.
	189	fn tokens(s: &str) -> Vec<&str> {
	190	let mut out = Vec::new();
	191	let mut start = 0;
	192	let class = \|c: char\| {
	193	if c.is_alphanumeric() \|\| c == '_' {
	194	0
	195	} else if c.is_whitespace() {
	196	1
	197	} else {
	198	2
	199	}
	200	};
	201	let mut prev: Option<u8> = None;
	202	for (i, c) in s.char_indices() {
	203	let k = class(c);
	204	if prev.is_some_and(\|p\| p != k \|\| k == 2) {
	205	out.push(&s[start..i]);
	206	start = i;
	207	}
	208	prev = Some(k);
	209	}
	210	if start < s.len() {
	211	out.push(&s[start..]);
	212	}
	213	out
	214	}
	215
	216	/// Text with every run of whitespace removed, for comparing ignoring it.
	217	fn squash(s: &str) -> String {
	218	s.split_whitespace().collect()
	219	}
	220
	221	/// Word-level runs of an old and a new line, or None when the lines share
	222	/// too little for marking words to help (then the whole line reads as changed).
	223	fn words(old: &str, new: &str) -> Option<(Vec<Segment>, Vec<Segment>)> {
	224	if old.len() + new.len() > 2_000 {
	225	return None;
	226	}
	227	let (ot, nt) = (tokens(old), tokens(new));
	228	let diff = similar::TextDiff::configure().algorithm(Algorithm::Patience).diff_slices(&ot, &nt);
	229	if diff.ratio() < 0.4 {
	230	return None;
	231	}
	232	let (mut d, mut a) = (Vec::new(), Vec::new());
	233	let push = \|v: &mut Vec<Segment>, text: &str, changed: bool\| match v.last_mut() {
	234	Some(last) if last.changed == changed => last.text.push_str(text),
	235	_ => v.push(Segment { text: text.to_string(), changed }),
	236	};
	237	for change in diff.iter_all_changes() {
	238	match change.tag() {
	239	similar::ChangeTag::Equal => {
	240	push(&mut d, change.value(), false);
	241	push(&mut a, change.value(), false);
	242	}
	243	similar::ChangeTag::Delete => push(&mut d, change.value(), true),
	244	similar::ChangeTag::Insert => push(&mut a, change.value(), true),
	245	}
	246	}
	247	Some((d, a))
	248	}
	249
d23464c0 Andy McCall 1 month ago ↶	250	/// Keep `context` rows around every change, replacing longer runs with a gap.
	251	fn with_context(rows: Vec<Line>, context: usize) -> Vec<Line> {
	252	let changed: Vec<bool> = rows.iter().map(\|r\| r.kind != Kind::Context).collect();
	253	let mut keep = vec![false; rows.len()];
	254	for (i, c) in changed.iter().enumerate() {
	255	if *c {
	256	let lo = i.saturating_sub(context);
	257	let hi = (i + context + 1).min(rows.len());
	258	for k in keep.iter_mut().take(hi).skip(lo) {
	259	*k = true;
	260	}
	261	}
	262	}
	263	let mut out = Vec::new();
	264	let mut gap = 0;
	265	for (row, k) in rows.into_iter().zip(keep) {
	266	if k {
	267	if gap > 0 {
9df855f2 Andy McCall 1 month ago ↶	268	out.push(Line::new(Kind::Gap, None, None, format!("{gap} unchanged lines")));
d23464c0 Andy McCall 1 month ago ↶	269	gap = 0;
	270	}
	271	out.push(row);
	272	} else {
	273	gap += 1;
	274	}
	275	}
	276	if gap > 0 {
9df855f2 Andy McCall 1 month ago ↶	277	out.push(Line::new(Kind::Gap, None, None, format!("{gap} unchanged lines")));
d23464c0 Andy McCall 1 month ago ↶	278	}
	279	out
	280	}
	281
	282	/// Hunks between two texts, in `oxy diff`'s shape.
	283	pub fn hunks_between(old: &[u8], new: &[u8]) -> Vec<DiffHunk> {
	284	let old_lines = oxy_core::diff::split_lines(old);
	285	let new_lines = oxy_core::diff::split_lines(new);
	286	let ops = similar::capture_diff_slices(Algorithm::Myers, &old_lines, &new_lines);
	287	let mut hunks: Vec<DiffHunk> = Vec::new();
	288	for op in ops {
	289	match op {
	290	DiffOp::Equal { .. } => {}
	291	DiffOp::Delete { old_index, old_len, .. } => {
	292	hunks.push(DiffHunk {
	293	base_line: (old_index + old_len) as u32,
	294	added: vec![],
	295	removed: (old_index..old_index + old_len).map(\|i\| (i as u32 + 1, old_lines[i].to_vec())).collect(),
	296	});
	297	}
	298	DiffOp::Insert { old_index, new_index, new_len } => {
	299	hunks.push(DiffHunk {
	300	base_line: old_index as u32,
	301	added: (new_index..new_index + new_len).map(\|i\| new_lines[i].to_vec()).collect(),
	302	removed: vec![],
	303	});
	304	}
	305	DiffOp::Replace { old_index, old_len, new_index, new_len } => {
	306	hunks.push(DiffHunk {
	307	base_line: (old_index + old_len) as u32,
	308	added: (new_index..new_index + new_len).map(\|i\| new_lines[i].to_vec()).collect(),
	309	removed: (old_index..old_index + old_len).map(\|i\| (i as u32 + 1, old_lines[i].to_vec())).collect(),
	310	});
	311	}
	312	}
	313	}
	314	hunks
	315	}
	316
9ff27da5 Andy McCall 1 month ago ↶	317	/// The per-file diff of one change against its base state (what
	318	/// `oxy diff CHANGE` shows), using an already loaded base.
	319	pub fn change_files(change: &oxy_core::objects::Change, base: &oxy_core::state::State, base_snapshot: &Snapshot) -> Vec<FileDiff> {
	320	oxy_core::repo::diff_files_of(change, base, base_snapshot)
	321	}
	322
d23464c0 Andy McCall 1 month ago ↶	323	/// Every file that differs between two snapshots, with the base content
	324	/// of files present in both (for context).
	325	pub fn snapshot_diff(base: &Snapshot, head: &Snapshot) -> (Vec<FileDiff>, BTreeMap<String, Vec<u8>>) {
	326	let mut files = Vec::new();
	327	let mut bases = BTreeMap::new();
	328	let text_of = \|f: &oxy_core::state::FileState\| match &f.content {
	329	FileContent::Text { bytes, .. } => Some(bytes.clone()),
	330	_ => None,
	331	};
	332	for (path, hf) in &head.files {
	333	if hf.kind == oxy_core::objects::NodeKind::Dir {
	334	continue;
	335	}
	336	match base.files.get(path) {
	337	None => {
	338	let new = text_of(hf).unwrap_or_default();
	339	files.push(FileDiff { path: path.clone(), kind: "added".into(), hunks: hunks_between(b"", &new), from: None });
	340	}
	341	Some(bf) => {
	342	let (old, new) = (text_of(bf), text_of(hf));
	343	if old != new {
	344	let old_b = old.clone().unwrap_or_default();
	345	let hunks = hunks_between(&old_b, &new.unwrap_or_default());
	346	if let Some(o) = old {
	347	bases.insert(path.clone(), o);
	348	}
	349	files.push(FileDiff { path: path.clone(), kind: "modified".into(), hunks, from: None });
	350	} else if bf.mode != hf.mode {
	351	files.push(FileDiff { path: path.clone(), kind: "mode".into(), hunks: vec![], from: None });
	352	}
	353	}
	354	}
	355	}
	356	for (path, bf) in &base.files {
	357	if bf.kind != oxy_core::objects::NodeKind::Dir && !head.files.contains_key(path) {
	358	let old = text_of(bf).unwrap_or_default();
	359	bases.insert(path.clone(), old.clone());
	360	files.push(FileDiff { path: path.clone(), kind: "removed".into(), hunks: hunks_between(&old, b""), from: None });
	361	}
	362	}
	363	files.sort_by(\|a, b\| a.path.cmp(&b.path));
	364	(files, bases)
	365	}
	366
	367	#[cfg(test)]
	368	mod tests {
	369	use super::*;
	370
	371	#[test]
	372	fn unified_rows_with_context() {
	373	let base = b"a\nb\nc\nd\ne\nf\ng\nh\n";
	374	let hunks = hunks_between(base, b"a\nb\nc\nX\ne\nf\ng\nh\nZ\n");
	375	let rows = unified(base, &hunks, 1);
	376	let s: Vec<String> = rows.iter().map(\|r\| format!("{}{}", r.kind.sign(), r.text)).collect();
	377	assert_eq!(s, ["…2 unchanged lines", " c", "-d", "+X", " e", "…2 unchanged lines", " h", "+Z"]);
	378	assert_eq!(rows[2].old_no, Some(4));
	379	assert_eq!(rows[3].new_no, Some(4));
	380	assert_eq!(rows.last().unwrap().new_no, Some(9));
	381	}
	382
	383	#[test]
	384	fn added_file() {
	385	let hunks = hunks_between(b"", b"one\ntwo\n");
	386	let rows = unified(b"", &hunks, 3);
387	assert_eq!(rows.iter().map(\|r\| r.kind).collect::<Vec<_>>(), [Kind::Add, Kind::Add]);
388	}
389	}
9df855f2 Andy McCall 1 month ago ↶	390
	391	#[cfg(test)]
	392	mod refine_tests {
	393	use super::*;
	394
	395	fn rows(base: &str, new: &str, opts: Options) -> Vec<Line> {
	396	unified_with(base.as_bytes(), &hunks_between(base.as_bytes(), new.as_bytes()), 3, opts)
	397	}
	398
	399	#[test]
	400	fn changed_words_are_marked_within_a_line() {
	401	let r = rows("let answer = 42;\n", "let answer = 43;\n", Options::default());
	402	let del = r.iter().find(\|l\| l.kind == Kind::Del).unwrap();
	403	let add = r.iter().find(\|l\| l.kind == Kind::Add).unwrap();
	404	assert_eq!(del.segments.iter().filter(\|s\| s.changed).map(\|s\| s.text.as_str()).collect::<Vec<_>>(), ["42"]);
	405	assert_eq!(add.segments.iter().filter(\|s\| s.changed).map(\|s\| s.text.as_str()).collect::<Vec<_>>(), ["43"]);
	406	assert_eq!(add.segments.iter().map(\|s\| s.text.as_str()).collect::<String>(), add.text, "segments cover the line");
	407	// Lines with nothing in common are not broken into words.
	408	let r = rows("alpha beta\n", "gamma delta\n", Options::default());
	409	assert!(r.iter().all(\|l\| l.segments.is_empty()));
	410	}
	411
	412	#[test]
	413	fn whitespace_changes_can_be_hidden() {
	414	let base = "fn main() {\n a();\n b();\n}\n";
	415	let new = "fn main() {\n a();\n c();\n}\n";
	416	let shown = rows(base, new, Options::default());
	417	assert_eq!(shown.iter().filter(\|l\| l.kind == Kind::Add).count(), 2);
	418	let hidden = rows(base, new, Options { ignore_whitespace: true });
	419	let kinds: Vec<(Kind, &str)> = hidden.iter().map(\|l\| (l.kind, l.text.trim())).collect();
	420	assert_eq!(
	421	kinds,
	422	[(Kind::Context, "fn main() {"), (Kind::Context, "a();"), (Kind::Del, "b();"), (Kind::Add, "c();"), (Kind::Context, "}")],
	423	"only the real change remains, in order"
	424	);
	425	let ctx = hidden.iter().find(\|l\| l.text.trim() == "a();").unwrap();
	426	assert_eq!((ctx.old_no, ctx.new_no), (Some(2), Some(2)));
	427	}
	428	}

Keyboard