ashlar_diff/
lib.rs

1//! Headless text diffs for ashlar: line diffs with a cost cap, word-level changes, hunks with
2//! context and collapsible unchanged ranges, and a unified-patch parser and writer.
3//!
4//! No dependencies, no UI; builds for `wasm32-unknown-unknown`. The view lives in
5//! `ashlar_ui::diff_view`.
6//!
7//! ```
8//! use ashlar_diff::{FileDiff, LineKind};
9//!
10//! let d = FileDiff::from_texts("a\nb\nc\n", "a\nB\nc\n").with_paths("x.txt", "x.txt");
11//! let hunk = &d.hunks[0];
12//! assert_eq!((hunk.old_start, hunk.old_len, hunk.new_start, hunk.new_len), (1, 3, 1, 3));
13//! assert_eq!(hunk.lines[1].kind, LineKind::Removed);
14//! assert_eq!(d.to_patch(), "--- a/x.txt\n+++ b/x.txt\n@@ -1,3 +1,3 @@\n a\n-b\n+B\n c\n");
15//! ```
16//!
17//! Patches from `git diff` parse into one [`FileDiff`] per file and write back byte for byte:
18//!
19//! ```
20//! let patch = "diff --git a/f b/f\nindex 1..2 100644\n--- a/f\n+++ b/f\n@@ -1 +1 @@\n-x\n+y\n";
21//! let files = ashlar_diff::parse_patch(patch).unwrap();
22//! assert_eq!(files[0].new_path.as_deref(), Some("f"));
23//! assert_eq!(ashlar_diff::write_patch(&files), patch);
24//! ```
25
26mod myers;
27mod patch;
28mod words;
29
30use std::ops::Range;
31
32pub use myers::{DEFAULT_MAX_COST, Edit, Op, diff_ops};
33pub use patch::{PatchError, PatchErrorKind, parse_patch, write_patch};
34pub use words::{MAX_WORD_DIFF_LINE, word_diff};
35
36/// What a diff line is.
37#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
38pub enum LineKind {
39    /// Unchanged (shown for context).
40    Context,
41    /// Only in the old text.
42    Removed,
43    /// Only in the new text.
44    Added,
45}
46
47/// One line of a hunk.
48#[derive(Clone, Debug, PartialEq, Eq)]
49pub struct Line {
50    pub kind: LineKind,
51    /// 1-based line number in the old text (`None` for added lines).
52    pub old_no: Option<u32>,
53    /// 1-based line number in the new text (`None` for removed lines).
54    pub new_no: Option<u32>,
55    /// The text, without its line break.
56    pub text: String,
57    /// The line has no line break (`\ No newline at end of file`).
58    pub no_newline: bool,
59    /// Byte ranges of `text` that changed against the paired line (word-level), sorted.
60    pub emphasis: Vec<Range<usize>>,
61}
62
63/// A run of changes with the context around them.
64#[derive(Clone, Debug, PartialEq, Eq)]
65pub struct Hunk {
66    /// As in the `@@ -old_start,old_len +new_start,new_len @@` header: when a length is 0 the
67    /// start is the line *before* the hunk.
68    pub old_start: u32,
69    pub old_len: u32,
70    pub new_start: u32,
71    pub new_len: u32,
72    /// The text after the second `@@` (often the enclosing function), without the leading space.
73    pub section: String,
74    pub lines: Vec<Line>,
75}
76
77impl Hunk {
78    /// The first new line number the hunk covers, and one past its last.
79    pub fn new_range(&self) -> Range<u32> {
80        let first = if self.new_len == 0 { self.new_start.saturating_add(1) } else { self.new_start };
81        first..first.saturating_add(self.new_len)
82    }
83
84    /// The first old line number the hunk covers, and one past its last.
85    pub fn old_range(&self) -> Range<u32> {
86        let first = if self.old_len == 0 { self.old_start.saturating_add(1) } else { self.old_start };
87        first..first.saturating_add(self.old_len)
88    }
89
90    /// The `@@ … @@` header line.
91    pub fn header(&self) -> String {
92        let range = |start: u32, len: u32| if len == 1 { start.to_string() } else { format!("{start},{len}") };
93        let mut s = format!("@@ -{} +{} @@", range(self.old_start, self.old_len), range(self.new_start, self.new_len));
94        if !self.section.is_empty() {
95            s.push(' ');
96            s.push_str(&self.section);
97        }
98        s
99    }
100}
101
102/// How a file changed.
103#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Default)]
104pub enum FileStatus {
105    #[default]
106    Modified,
107    Added,
108    Deleted,
109    Renamed,
110    Copied,
111}
112
113/// An unchanged range between hunks (or before the first, or after the last), which a view
114/// shows collapsed.
115#[derive(Clone, Copy, Debug, PartialEq, Eq)]
116pub struct Gap {
117    /// The hunk this gap comes before (`hunks.len()` for the gap after the last hunk).
118    pub before_hunk: usize,
119    /// First hidden line, 1-based, in the old and the new text.
120    pub old_start: u32,
121    pub new_start: u32,
122    /// Number of hidden lines.
123    pub len: u32,
124    /// The lines' text is known ([`FileDiff::source_line`]), so the gap can be expanded.
125    pub expandable: bool,
126}
127
128/// The new text of a file, indexed by line, so collapsed ranges can be expanded.
129#[derive(Clone, Debug, PartialEq, Eq, Default)]
130struct Source {
131    text: String,
132    /// Byte offset where each line starts.
133    starts: Vec<usize>,
134}
135
136impl Source {
137    fn new(text: String) -> Source {
138        let mut starts = vec![0];
139        starts.extend(text.match_indices('\n').map(|(i, _)| i + 1).filter(|&i| i < text.len()));
140        if text.is_empty() {
141            starts.clear();
142        }
143        Source { text, starts }
144    }
145
146    fn line(&self, i: usize) -> Option<&str> {
147        let start = *self.starts.get(i)?;
148        let end = self.starts.get(i + 1).copied().unwrap_or(self.text.len());
149        let s = self.text.get(start..end)?;
150        Some(s.strip_suffix('\n').unwrap_or(s))
151    }
152}
153
154/// Options for [`FileDiff::from_texts_with`].
155#[derive(Clone, Copy, Debug, PartialEq, Eq)]
156pub struct DiffOptions {
157    /// Unchanged lines kept around each change (default 3).
158    pub context: u32,
159    /// Cost cap of one Myers run (default [`DEFAULT_MAX_COST`]); see [`diff_ops`].
160    pub max_cost: usize,
161    /// Compute word-level emphasis for paired lines (default on).
162    pub words: bool,
163}
164
165impl Default for DiffOptions {
166    fn default() -> Self {
167        DiffOptions { context: 3, max_cost: DEFAULT_MAX_COST, words: true }
168    }
169}
170
171/// The changes to one file.
172#[derive(Clone, Debug, PartialEq, Eq, Default)]
173pub struct FileDiff {
174    /// Path before the change (`None` for an added file); `a/` and `b/` prefixes are stripped.
175    pub old_path: Option<String>,
176    /// Path after the change (`None` for a deleted file).
177    pub new_path: Option<String>,
178    pub status: FileStatus,
179    /// A binary file: no hunks, only a marker.
180    pub binary: bool,
181    /// `similarity index` of a rename or copy, in percent.
182    pub similarity: Option<u8>,
183    pub old_mode: Option<String>,
184    pub new_mode: Option<String>,
185    pub hunks: Vec<Hunk>,
186    /// The header lines as written (`diff --git`, `index`, `---`, `+++`, binary data…), without
187    /// line breaks; [`FileDiff::to_patch`] writes them back verbatim.
188    pub header: Vec<String>,
189    /// The diff hit its cost cap: correct, but not necessarily the smallest.
190    pub coarse: bool,
191    source: Option<Source>,
192}
193
194impl FileDiff {
195    /// Diffs two texts line by line with the default options.
196    pub fn from_texts(old: &str, new: &str) -> FileDiff {
197        FileDiff::from_texts_with(old, new, DiffOptions::default())
198    }
199
200    /// Diffs two texts line by line. The new text is kept, so every [`Gap`] is expandable.
201    pub fn from_texts_with(old: &str, new: &str, opts: DiffOptions) -> FileDiff {
202        let a: Vec<&str> = old.split_inclusive('\n').collect();
203        let b: Vec<&str> = new.split_inclusive('\n').collect();
204        let edit = diff_ops(&a, &b, opts.max_cost);
205        let mut hunks = build_hunks(&a, &b, &edit, opts.context);
206        if opts.words {
207            for h in &mut hunks {
208                emphasize(h);
209            }
210        }
211        FileDiff {
212            hunks,
213            header: vec!["--- a".to_owned(), "+++ b".to_owned()],
214            coarse: edit.coarse,
215            source: Some(Source::new(new.to_owned())),
216            ..FileDiff::default()
217        }
218    }
219
220    /// Sets both paths (and the `---`/`+++` header lines).
221    pub fn with_paths(mut self, old: &str, new: &str) -> FileDiff {
222        self.old_path = Some(old.to_owned());
223        self.new_path = Some(new.to_owned());
224        self.header = vec![format!("--- a/{old}"), format!("+++ b/{new}")];
225        if old != new && self.status == FileStatus::Modified {
226            self.status = FileStatus::Renamed;
227        }
228        self
229    }
230
231    /// Supplies the full new text of a parsed patch, so its collapsed ranges can be expanded.
232    pub fn with_source(mut self, new_text: &str) -> FileDiff {
233        self.source = Some(Source::new(new_text.to_owned()));
234        self
235    }
236
237    /// The path to show: the new one, else the old one.
238    pub fn path(&self) -> &str {
239        self.new_path.as_deref().or(self.old_path.as_deref()).unwrap_or("")
240    }
241
242    /// Lines added and removed.
243    pub fn stats(&self) -> (usize, usize) {
244        let mut added = 0usize;
245        let mut removed = 0usize;
246        for l in self.hunks.iter().flat_map(|h| &h.lines) {
247            match l.kind {
248                LineKind::Added => added += 1,
249                LineKind::Removed => removed += 1,
250                LineKind::Context => {}
251            }
252        }
253        (added, removed)
254    }
255
256    /// Number of lines of the new text, when it is known.
257    pub fn source_len(&self) -> Option<u32> {
258        self.source.as_ref().map(|s| u32::try_from(s.starts.len()).unwrap_or(u32::MAX))
259    }
260
261    /// Line `new_no` (1-based) of the new text, without its line break, when the text is known.
262    pub fn source_line(&self, new_no: u32) -> Option<&str> {
263        let i = usize::try_from(new_no.checked_sub(1)?).ok()?;
264        self.source.as_ref()?.line(i)
265    }
266
267    /// The unchanged ranges around the hunks, in order. The range after the last hunk is listed
268    /// only when the new text is known (a patch does not say how long the file is). Empty ranges
269    /// are left out.
270    pub fn gaps(&self) -> Vec<Gap> {
271        let expandable = self.source.is_some();
272        let mut out = Vec::new();
273        let (mut old_next, mut new_next) = (1u32, 1u32);
274        for (i, h) in self.hunks.iter().enumerate() {
275            let (o, n) = (h.old_range(), h.new_range());
276            let len = n.start.saturating_sub(new_next);
277            if len > 0 {
278                out.push(Gap { before_hunk: i, old_start: old_next, new_start: new_next, len, expandable });
279            }
280            old_next = o.end;
281            new_next = n.end;
282        }
283        if let Some(total) = self.source_len() {
284            let len = total.saturating_add(1).saturating_sub(new_next);
285            if len > 0 && !self.binary {
286                out.push(Gap { before_hunk: self.hunks.len(), old_start: old_next, new_start: new_next, len, expandable });
287            }
288        }
289        out
290    }
291
292    /// This file as a unified patch: the header lines, then the hunks.
293    pub fn to_patch(&self) -> String {
294        let mut out = String::new();
295        patch::write_file(self, &mut out);
296        out
297    }
298}
299
300/// Builds hunks from a line edit script; `a` and `b` keep their line breaks.
301fn build_hunks(a: &[&str], b: &[&str], edit: &Edit, context: u32) -> Vec<Hunk> {
302    // one entry per line of the script: (kind, old index, new index)
303    let mut rows: Vec<(LineKind, usize, usize)> = Vec::with_capacity(a.len().saturating_add(b.len()));
304    for op in &edit.ops {
305        match *op {
306            Op::Equal { old, new, len } => rows.extend((0..len).map(|i| (LineKind::Context, old + i, new + i))),
307            Op::Delete { old, len } => rows.extend((0..len).map(|i| (LineKind::Removed, old + i, 0))),
308            Op::Insert { new, len } => rows.extend((0..len).map(|i| (LineKind::Added, 0, new + i))),
309        }
310    }
311    let ctx = context as usize;
312    let is_change = |i: usize| rows.get(i).is_some_and(|r| r.0 != LineKind::Context);
313    let mut hunks = Vec::new();
314    let mut i = 0usize;
315    // old and new lines before `rows[i]`
316    let (mut old_before, mut new_before) = (0usize, 0usize);
317    let mut hunk_end = 0usize;
318    while i < rows.len() {
319        if !is_change(i) {
320            i += 1;
321            continue;
322        }
323        // extend over changes separated by at most 2·context unchanged lines
324        let first = i;
325        let mut last_end = i;
326        let mut j = i;
327        while j < rows.len() {
328            if is_change(j) {
329                last_end = j + 1;
330                j += 1;
331            } else if j - last_end < 2 * ctx && j + 1 < rows.len() {
332                j += 1;
333            } else {
334                break;
335            }
336        }
337        let lo = first.saturating_sub(ctx).max(hunk_end);
338        let hi = last_end.saturating_add(ctx).min(rows.len());
339        // count lines between the previous hunk's end and `lo`
340        for r in rows.get(hunk_end..lo).unwrap_or(&[]) {
341            count(r.0, &mut old_before, &mut new_before);
342        }
343        let mut lines = Vec::with_capacity(hi - lo);
344        let (mut o, mut n) = (old_before, new_before);
345        for &(kind, oi, ni) in rows.get(lo..hi).unwrap_or(&[]) {
346            let raw = match kind {
347                LineKind::Added => b.get(ni),
348                _ => a.get(oi),
349            }
350            .copied()
351            .unwrap_or("");
352            let no_newline = !raw.ends_with('\n');
353            let text = raw.strip_suffix('\n').unwrap_or(raw).to_owned();
354            let num = |x: usize| u32::try_from(x + 1).ok();
355            let (old_no, new_no) = match kind {
356                LineKind::Context => (num(o), num(n)),
357                LineKind::Removed => (num(o), None),
358                LineKind::Added => (None, num(n)),
359            };
360            count(kind, &mut o, &mut n);
361            lines.push(Line { kind, old_no, new_no, text, no_newline, emphasis: Vec::new() });
362        }
363        let old_len = o - old_before;
364        let new_len = n - new_before;
365        let start = |before: usize, len: usize| u32::try_from(if len == 0 { before } else { before + 1 }).unwrap_or(u32::MAX);
366        hunks.push(Hunk {
367            old_start: start(old_before, old_len),
368            old_len: u32::try_from(old_len).unwrap_or(u32::MAX),
369            new_start: start(new_before, new_len),
370            new_len: u32::try_from(new_len).unwrap_or(u32::MAX),
371            section: String::new(),
372            lines,
373        });
374        old_before = o;
375        new_before = n;
376        hunk_end = hi;
377        i = hi;
378    }
379    hunks
380}
381
382fn count(kind: LineKind, old: &mut usize, new: &mut usize) {
383    match kind {
384        LineKind::Context => {
385            *old += 1;
386            *new += 1;
387        }
388        LineKind::Removed => *old += 1,
389        LineKind::Added => *new += 1,
390    }
391}
392
393/// Word-level emphasis for a hunk: in each run of removed lines followed by added lines, the
394/// n-th removed line pairs with the n-th added line.
395pub(crate) fn emphasize(h: &mut Hunk) {
396    let mut i = 0usize;
397    let len = h.lines.len();
398    while i < len {
399        let removed = h.lines.iter().skip(i).take_while(|l| l.kind == LineKind::Removed).count();
400        if removed == 0 {
401            i += 1;
402            continue;
403        }
404        let added = h.lines.iter().skip(i + removed).take_while(|l| l.kind == LineKind::Added).count();
405        for k in 0..removed.min(added) {
406            let (ri, ai) = (i + k, i + removed + k);
407            let pair = match (h.lines.get(ri), h.lines.get(ai)) {
408                (Some(r), Some(a)) => word_diff(&r.text, &a.text),
409                _ => None,
410            };
411            if let Some((er, ea)) = pair {
412                if let Some(r) = h.lines.get_mut(ri) {
413                    r.emphasis = er;
414                }
415                if let Some(a) = h.lines.get_mut(ai) {
416                    a.emphasis = ea;
417                }
418            }
419        }
420        i += removed + added;
421    }
422}
423
424#[cfg(test)]
425mod tests {
426    use super::*;
427
428    #[test]
429    fn hunks_merge_close_changes_and_split_far_ones() {
430        let old: String = (1..=30).map(|i| format!("{i}\n")).collect();
431        let new: String = (1..=30)
432            .map(|i| match i {
433                5 => "five\n".to_owned(),
434                8 => "eight\n".to_owned(),
435                25 => "x\n".to_owned(),
436                _ => format!("{i}\n"),
437            })
438            .collect();
439        let d = FileDiff::from_texts(&old, &new);
440        assert_eq!(d.hunks.len(), 2);
441        let h = &d.hunks[0];
442        assert_eq!((h.old_start, h.old_len, h.new_start, h.new_len), (2, 10, 2, 10));
443        let h = &d.hunks[1];
444        assert_eq!((h.old_start, h.old_len), (22, 7));
445        let gaps = d.gaps();
446        assert_eq!(gaps.len(), 3);
447        assert_eq!((gaps[0].new_start, gaps[0].len), (1, 1));
448        assert_eq!((gaps[1].new_start, gaps[1].len), (12, 10));
449        assert_eq!((gaps[2].new_start, gaps[2].len, gaps[2].before_hunk), (29, 2, 2));
450        assert_eq!(d.source_line(12), Some("12"));
451    }
452
453    #[test]
454    fn identical_texts_are_one_gap() {
455        let d = FileDiff::from_texts("a\nb\n", "a\nb\n");
456        assert!(d.hunks.is_empty());
457        assert_eq!(d.gaps(), vec![Gap { before_hunk: 0, old_start: 1, new_start: 1, len: 2, expandable: true }]);
458        assert!(FileDiff::from_texts("", "").gaps().is_empty());
459    }
460
461    #[test]
462    fn missing_final_newline() {
463        let d = FileDiff::from_texts("a\nb", "a\nb\n");
464        let p = d.to_patch();
465        assert_eq!(p, "--- a\n+++ b\n@@ -1,2 +1,2 @@\n a\n-b\n\\ No newline at end of file\n+b\n");
466        let back = parse_patch(&p).unwrap();
467        assert_eq!(back[0].hunks, d.hunks);
468    }
469
470    #[test]
471    fn added_and_deleted_whole_files() {
472        let d = FileDiff::from_texts("", "x\ny\n");
473        assert_eq!(d.hunks[0].header(), "@@ -0,0 +1,2 @@");
474        let d = FileDiff::from_texts("x\n", "");
475        assert_eq!(d.hunks[0].header(), "@@ -1 +0,0 @@");
476    }
477}
ashlar_diff/lib.rs

ashlar_diff/
lib.rs
