Skip to main content

tinyharness_ui/ui/
diff.rs

1use std::{
2    error::Error,
3    io::{self, Write},
4};
5
6use super::frame::{FOOT, GAP, GUTTER, GUTTER_WIDTH, gutter_line, truncate_ellipsis, write_band};
7use super::wrap::MAX_LINE_WIDTH;
8use crate::style::*;
9
10// ── Diff computation (LCS-based algorithm) ─────────────────────────────────
11
12/// A single line in a diff hunk — either kept, removed, or added.
13#[derive(Debug, Clone, PartialEq)]
14pub enum DiffLine<'a> {
15    /// Line present in both old and new (unchanged).
16    Keep(&'a str),
17    /// Line present only in old (removed).
18    Remove(&'a str),
19    /// Line present only in new (added).
20    Add(&'a str),
21}
22
23/// Compute the shortest edit script between `old` and `new`.
24///
25/// Uses a standard LCS (Longest Common Subsequence) dynamic programming approach
26/// to find the optimal alignment, then walks the DP table to produce the diff.
27/// This produces the same quality of diff as `git diff` for line-level changes.
28pub fn compute_diff<'a>(old: &'a [&str], new: &'a [&str]) -> Vec<DiffLine<'a>> {
29    let n = old.len();
30    let m = new.len();
31
32    // Trivial cases
33    if n == 0 && m == 0 {
34        return vec![];
35    }
36    if n == 0 {
37        return new.iter().map(|l| DiffLine::Add(l)).collect();
38    }
39    if m == 0 {
40        return old.iter().map(|l| DiffLine::Remove(l)).collect();
41    }
42    if old == new {
43        return old.iter().map(|l| DiffLine::Keep(l)).collect();
44    }
45
46    // Build LCS length table using O(n) space (rolling rows).
47    // dp[j] = LCS length for old[0..i] and new[0..j]
48    let mut dp = vec![0usize; m + 1];
49    let mut prev = vec![0usize; m + 1];
50
51    // We also need to store the full table for backtracking.
52    // For correctness we store the full (n+1) x (m+1) table.
53    // This is fine since diffs are typically small (file previews in confirmation prompts).
54    let mut table = vec![vec![0usize; m + 1]; n + 1];
55
56    for i in 1..=n {
57        prev.copy_from_slice(&dp);
58        for j in 1..=m {
59            if old[i - 1] == new[j - 1] {
60                dp[j] = prev[j - 1] + 1;
61            } else {
62                dp[j] = dp[j - 1].max(prev[j]);
63            }
64        }
65        table[i].copy_from_slice(&dp);
66    }
67
68    // Backtrack through the full table to reconstruct the diff
69    let mut result = Vec::with_capacity(n + m);
70    let mut i = n;
71    let mut j = m;
72
73    while i > 0 || j > 0 {
74        if i > 0 && j > 0 && old[i - 1] == new[j - 1] {
75            result.push(DiffLine::Keep(old[i - 1]));
76            i -= 1;
77            j -= 1;
78        } else if j > 0 && (i == 0 || table[i][j - 1] >= table[i - 1][j]) {
79            result.push(DiffLine::Add(new[j - 1]));
80            j -= 1;
81        } else {
82            result.push(DiffLine::Remove(old[i - 1]));
83            i -= 1;
84        }
85    }
86
87    result.reverse();
88    result
89}
90
91/// Context lines to show around each change in unified diff output.
92const DIFF_CONTEXT_LINES: usize = 3;
93
94// ── Public API ─────────────────────────────────────────────────────────────
95
96/// Diff-card glyph — "not equal", marking the block as a change preview
97/// rather than a completed tool result.
98const DIFF_GLYPH: &str = "≠";
99
100/// Which side of the diff a rendered row belongs to.
101#[derive(Debug, Clone, Copy, PartialEq, Eq)]
102enum Kind {
103    Keep,
104    Remove,
105    Add,
106}
107
108impl Kind {
109    /// One-character change indicator, in the column before the line number.
110    fn sign(self) -> char {
111        match self {
112            Kind::Keep => ' ',
113            Kind::Remove => '-',
114            Kind::Add => '+',
115        }
116    }
117
118    fn color(self) -> &'static str {
119        match self {
120            Kind::Keep => FG_FAINT,
121            Kind::Remove => FG_ERR,
122            Kind::Add => FG_OK,
123        }
124    }
125}
126
127/// One row of a diff card.
128enum DiffRow {
129    /// A source line, with the number of the side it belongs to.
130    Line {
131        kind: Kind,
132        num: usize,
133        text: String,
134    },
135    /// Hunk boundary: how many unchanged rows were skipped.
136    Gap(usize),
137}
138
139/// Number every row of a computed diff with the line number of its own side,
140/// so a reader can jump straight to the location in their editor.
141fn numbered(diff: &[DiffLine]) -> Vec<(Kind, usize, String)> {
142    let (mut old, mut new) = (0usize, 0usize);
143    diff.iter()
144        .map(|item| match item {
145            DiffLine::Keep(t) => {
146                old += 1;
147                new += 1;
148                (Kind::Keep, old, (*t).to_string())
149            }
150            DiffLine::Remove(t) => {
151                old += 1;
152                (Kind::Remove, old, (*t).to_string())
153            }
154            DiffLine::Add(t) => {
155                new += 1;
156                (Kind::Add, new, (*t).to_string())
157            }
158        })
159        .collect()
160}
161
162/// Collapse numbered rows into hunks around the changes, keeping `context`
163/// unchanged lines on each side and replacing everything else with a
164/// [`DiffRow::Gap`] that says how much was hidden.
165///
166/// Never hides a change — only context — so the preview always shows every
167/// line the tool would touch.
168fn hunked(rows: &[(Kind, usize, String)], context: usize) -> Vec<DiffRow> {
169    let changed: Vec<usize> = rows
170        .iter()
171        .enumerate()
172        .filter(|(_, (k, ..))| *k != Kind::Keep)
173        .map(|(i, _)| i)
174        .collect();
175    if changed.is_empty() {
176        return vec![];
177    }
178
179    // Merge overlapping windows into hunk ranges.
180    let mut ranges: Vec<(usize, usize)> = Vec::new();
181    let mut start = changed[0].saturating_sub(context);
182    let mut end = (changed[0] + context + 1).min(rows.len());
183    for &i in &changed[1..] {
184        let lo = i.saturating_sub(context);
185        let hi = (i + context + 1).min(rows.len());
186        if lo <= end {
187            end = end.max(hi);
188        } else {
189            ranges.push((start, end));
190            start = lo;
191            end = hi;
192        }
193    }
194    ranges.push((start, end));
195
196    let mut out: Vec<DiffRow> = Vec::new();
197    let mut cursor = 0usize;
198    for (lo, hi) in ranges {
199        if lo > cursor {
200            out.push(DiffRow::Gap(lo - cursor));
201        }
202        for (kind, num, text) in &rows[lo..hi] {
203            out.push(DiffRow::Line {
204                kind: *kind,
205                num: *num,
206                text: text.clone(),
207            });
208        }
209        cursor = hi;
210    }
211    out
212}
213
214/// Draw a diff card: a `≠` title band naming the operation and target, then
215/// gutter-outlined rows carrying line numbers and `-`/`+` signs.
216///
217/// `stat` is a pre-styled trailing segment for the band (change counts, or a
218/// note like `new file`); pass an empty string to omit it. When `rows` is
219/// empty the card is just the band — the "nothing to change" case.
220fn write_diff_card<W: Write>(
221    w: &mut W,
222    op: &str,
223    path: &str,
224    stat: &str,
225    rows: &[DiffRow],
226) -> io::Result<()> {
227    // `stat` may carry its own inline colors (e.g. `-3 +7`), so it is passed
228    // through as an unstyled segment.
229    let mut segments: Vec<(&str, &str)> = vec![
230        (DIFF_GLYPH, FG_ACCENT),
231        (" ", FG_FAINT),
232        (op, FG_BAND),
233        (" · ", FG_FAINT),
234        (path, FG_ACCENT),
235    ];
236    if !stat.is_empty() {
237        segments.push((" · ", FG_FAINT));
238        segments.push((stat, ""));
239    }
240    write_band(w, &segments)?;
241    if rows.is_empty() {
242        return Ok(());
243    }
244
245    let num_width = rows
246        .iter()
247        .map(|r| match r {
248            DiffRow::Line { num, .. } => *num,
249            DiffRow::Gap(_) => 0,
250        })
251        .max()
252        .unwrap_or(1)
253        .to_string()
254        .len()
255        .max(2);
256    // Columns left for source text after the gutter, sign, number and space.
257    let text_width = MAX_LINE_WIDTH.saturating_sub(GUTTER_WIDTH + num_width + 3);
258    let last = rows.len() - 1;
259
260    for (i, row) in rows.iter().enumerate() {
261        match row {
262            DiffRow::Line { kind, num, text } => {
263                let glyph = if i == last { FOOT } else { GUTTER };
264                let color = kind.color();
265                gutter_line(
266                    w,
267                    glyph,
268                    &format!(
269                        "{color}{sign}{RESET}{FG_FAINT}{num:>width$}{RESET} {color}{text}{RESET}",
270                        sign = kind.sign(),
271                        num = num,
272                        width = num_width,
273                        text = truncate_ellipsis(text, text_width)
274                    ),
275                )?;
276            }
277            // Gap rows keep the open gutter — the card isn't finished yet.
278            DiffRow::Gap(skipped) => {
279                gutter_line(
280                    w,
281                    GAP,
282                    &format!(
283                        "{FG_FAINT}{skipped} unchanged lines{RESET}",
284                        skipped = skipped
285                    ),
286                )?;
287            }
288        }
289    }
290    Ok(())
291}
292
293/// Count removed/added rows and format them as a band stat (`-3 +7`).
294fn stat_of(diff: &[DiffLine]) -> String {
295    let removals = diff
296        .iter()
297        .filter(|l| matches!(l, DiffLine::Remove(_)))
298        .count();
299    let additions = diff
300        .iter()
301        .filter(|l| matches!(l, DiffLine::Add(_)))
302        .count();
303    format!("{FG_ERR}-{removals}{RESET} {FG_OK}+{additions}{RESET}")
304}
305
306/// Show a unified-diff-style view of a write operation (full file).
307/// If the file already exists, reads it and shows a line-by-line diff
308/// with removed lines in red and added lines in green.
309/// If the file is new, shows a preview of the content that will be written.
310pub fn show_write_preview<W: Write>(
311    stdout: &mut W,
312    path: &str,
313    new_content: &str,
314) -> Result<(), Box<dyn Error>> {
315    let new_lines: Vec<&str> = new_content.lines().collect();
316
317    let Ok(existing) = std::fs::read_to_string(path) else {
318        // File doesn't exist — every line is an addition.
319        let rows: Vec<DiffRow> = new_lines
320            .iter()
321            .enumerate()
322            .map(|(i, t)| DiffRow::Line {
323                kind: Kind::Add,
324                num: i + 1,
325                text: (*t).to_string(),
326            })
327            .collect();
328        let stat = format!(
329            "{FG_OK}new file{RESET} {FG_FAINT}({} lines)",
330            new_lines.len()
331        );
332        write_diff_card(stdout, "write", path, &stat, &rows)?;
333        return Ok(());
334    };
335
336    let old_lines: Vec<&str> = existing.lines().collect();
337    let diff = compute_diff(&old_lines, &new_lines);
338    if !diff.iter().any(|l| !matches!(l, DiffLine::Keep(_))) {
339        write_diff_card(stdout, "write", path, "no changes", &[])?;
340        return Ok(());
341    }
342
343    let rows = hunked(&numbered(&diff), DIFF_CONTEXT_LINES);
344    let stat = stat_of(&diff);
345    write_diff_card(stdout, "write", path, &stat, &rows)?;
346    Ok(())
347}
348
349/// Show a unified-diff-style view of an edit operation.
350/// Reads the file, locates `old_str`, and prints context lines
351/// with the removed text in red and the replacement in green.
352pub fn show_edit_diff<W: Write>(
353    stdout: &mut W,
354    path: &str,
355    old_str: &str,
356    new_str: &str,
357) -> Result<(), Box<dyn Error>> {
358    let content = std::fs::read_to_string(path)
359        .map_err(|e| -> Box<dyn Error> { format!("Failed to read '{path}': {e}").into() })?;
360
361    // Find the byte offset of old_str in the content
362    let Some(offset) = content.find(old_str) else {
363        let rows = vec![DiffRow::Line {
364            kind: Kind::Remove,
365            num: 0,
366            text: "'old_str' not found in file — the edit would fail".to_string(),
367        }];
368        return write_diff_card(stdout, "edit", path, "match failed", &rows).map_err(Into::into);
369    };
370
371    // Count newlines before the match to get the line number (0-based)
372    let line_number = content[..offset].matches('\n').count();
373    let lines: Vec<&str> = content.lines().collect();
374    let old_lines: Vec<&str> = old_str.lines().collect();
375    let new_lines: Vec<&str> = new_str.lines().collect();
376
377    // Show a couple of lines of context around the replacement so the change
378    // has a location, not just a content.
379    let before_ctx = 2usize;
380    let after_ctx = 2usize;
381    let start_line = line_number.saturating_sub(before_ctx);
382
383    let mut rows: Vec<DiffRow> = Vec::new();
384    if start_line > 0 {
385        rows.push(DiffRow::Gap(start_line));
386    }
387    for (i, line) in lines
388        .iter()
389        .enumerate()
390        .take(line_number)
391        .skip(start_line)
392        .map(|(i, l)| (i + 1, l))
393    {
394        rows.push(DiffRow::Line {
395            kind: Kind::Keep,
396            num: i,
397            text: line.to_string(),
398        });
399    }
400    // The window is anchored on the old file, so removals and additions share
401    // one number column — the reader sees both sides of the swap in place.
402    for (i, line) in old_lines.iter().enumerate() {
403        rows.push(DiffRow::Line {
404            kind: Kind::Remove,
405            num: line_number + i + 1,
406            text: line.to_string(),
407        });
408    }
409    for (i, line) in new_lines.iter().enumerate() {
410        rows.push(DiffRow::Line {
411            kind: Kind::Add,
412            num: line_number + i + 1,
413            text: line.to_string(),
414        });
415    }
416    let after_start = line_number + old_lines.len();
417    let end_line = (after_start + after_ctx).min(lines.len());
418    for (i, line) in lines.iter().enumerate().take(end_line).skip(after_start) {
419        rows.push(DiffRow::Line {
420            kind: Kind::Keep,
421            num: i + 1,
422            text: line.to_string(),
423        });
424    }
425    let tail = lines.len().saturating_sub(end_line);
426    if tail > 0 {
427        rows.push(DiffRow::Gap(tail));
428    }
429
430    let stat = format!(
431        "{FG_ERR}-{n}{RESET} {FG_OK}+{m}{RESET}",
432        n = old_lines.len(),
433        m = new_lines.len()
434    );
435    write_diff_card(stdout, "edit", path, &stat, &rows)?;
436    Ok(())
437}
438
439/// Render a [`DiffLine`] sequence into a plain-text string (no ANSI codes).
440///
441/// Returns a string with lines prefixed by `  ` (keep), `- ` (remove), or `+ ` (add),
442/// and line numbers if requested.
443pub fn render_diff_plain(
444    old_lines: &[&str],
445    new_lines: &[&str],
446    diff: &[DiffLine],
447    show_line_numbers: bool,
448) -> String {
449    if diff.is_empty() {
450        return String::new();
451    }
452
453    let max_line = old_lines.len().max(new_lines.len()).max(1);
454    let num_width = if show_line_numbers {
455        max_line.to_string().len().max(2)
456    } else {
457        0
458    };
459
460    let mut result = String::new();
461    let mut old_num: usize = 0;
462    let mut new_num: usize = 0;
463
464    // Find change positions to determine hunks with context
465    let change_indices: Vec<usize> = diff
466        .iter()
467        .enumerate()
468        .filter_map(|(i, l)| matches!(l, DiffLine::Remove(_) | DiffLine::Add(_)).then_some(i))
469        .collect();
470
471    if change_indices.is_empty() {
472        return result;
473    }
474
475    // Merge overlapping/adjacent hunks
476    let mut hunk_ranges: Vec<(usize, usize)> = Vec::new();
477    let mut hunk_start = change_indices[0].saturating_sub(DIFF_CONTEXT_LINES);
478    let mut hunk_end = (change_indices[0] + DIFF_CONTEXT_LINES + 1).min(diff.len());
479
480    for &idx in &change_indices[1..] {
481        let ns = idx.saturating_sub(DIFF_CONTEXT_LINES);
482        let ne = (idx + DIFF_CONTEXT_LINES + 1).min(diff.len());
483        if ns <= hunk_end {
484            hunk_end = hunk_end.max(ne);
485        } else {
486            hunk_ranges.push((hunk_start, hunk_end));
487            hunk_start = ns;
488            hunk_end = ne;
489        }
490    }
491    hunk_ranges.push((hunk_start, hunk_end));
492
493    for (hunk_idx, &(start, end)) in hunk_ranges.iter().enumerate() {
494        // Separator between hunks
495        if hunk_idx > 0 {
496            result.push_str("  ┈\n");
497        }
498
499        // Count line numbers up to the start of this hunk
500        for item in diff.iter().take(start) {
501            match item {
502                DiffLine::Keep(_) => {
503                    old_num += 1;
504                    new_num += 1;
505                }
506                DiffLine::Remove(_) => {
507                    old_num += 1;
508                }
509                DiffLine::Add(_) => {
510                    new_num += 1;
511                }
512            }
513        }
514
515        for i in start..end {
516            if i >= diff.len() {
517                break;
518            }
519            match &diff[i] {
520                DiffLine::Keep(line) => {
521                    old_num += 1;
522                    new_num += 1;
523                    if show_line_numbers {
524                        result.push_str(&format!(
525                            "  {:>width$} │ {}\n",
526                            old_num,
527                            line,
528                            width = num_width
529                        ));
530                    } else {
531                        result.push_str(&format!("    {}\n", line));
532                    }
533                }
534                DiffLine::Remove(line) => {
535                    old_num += 1;
536                    if show_line_numbers {
537                        result.push_str(&format!(
538                            "-  {:>width$} │ {}\n",
539                            old_num,
540                            line,
541                            width = num_width
542                        ));
543                    } else {
544                        result.push_str(&format!("-   {}\n", line));
545                    }
546                }
547                DiffLine::Add(line) => {
548                    new_num += 1;
549                    if show_line_numbers {
550                        result.push_str(&format!(
551                            "+  {:>width$} │ {}\n",
552                            new_num,
553                            line,
554                            width = num_width
555                        ));
556                    } else {
557                        result.push_str(&format!("+   {}\n", line));
558                    }
559                }
560            }
561        }
562    }
563
564    result
565}
566
567/// Compute a unified diff between old and new content and return it as
568/// a plain-text string (no ANSI codes). Returns an empty string if the
569/// contents are identical.
570pub fn compute_edit_diff_plain(old_content: &str, new_content: &str) -> String {
571    let old_lines: Vec<&str> = old_content.lines().collect();
572    let new_lines: Vec<&str> = new_content.lines().collect();
573    let diff = compute_diff(&old_lines, &new_lines);
574
575    if diff.iter().all(|l| matches!(l, DiffLine::Keep(_))) {
576        return String::new();
577    }
578
579    render_diff_plain(&old_lines, &new_lines, &diff, true)
580}
581
582/// Compute a diff for a write operation (file creation or modification) and
583/// return it as a plain-text string (no ANSI codes).
584pub fn compute_write_diff_plain(path: &str, new_content: &str) -> String {
585    let existing = std::fs::read_to_string(path);
586
587    match existing {
588        Ok(old_content) => {
589            let old_lines: Vec<&str> = old_content.lines().collect();
590            let new_lines: Vec<&str> = new_content.lines().collect();
591            let diff = compute_diff(&old_lines, &new_lines);
592
593            if diff.iter().all(|l| matches!(l, DiffLine::Keep(_))) {
594                return String::new();
595            }
596
597            render_diff_plain(&old_lines, &new_lines, &diff, true)
598        }
599        Err(_) => {
600            // New file — show all lines as additions
601            let new_lines: Vec<&str> = new_content.lines().collect();
602            let num_width = new_lines.len().to_string().len().max(2);
603            let mut result = String::new();
604            for (i, line) in new_lines.iter().enumerate() {
605                result.push_str(&format!(
606                    "+  {:>width$} │ {}\n",
607                    i + 1,
608                    line,
609                    width = num_width
610                ));
611            }
612            result
613        }
614    }
615}
616
617/// Compute a diff for an edit operation and return it as a plain-text string
618/// (no ANSI codes). Reads the current file content to locate the edit.
619pub fn compute_edit_diff_from_path(path: &str, old_str: &str, new_str: &str) -> String {
620    let content = match std::fs::read_to_string(path) {
621        Ok(c) => c,
622        Err(_) => return String::new(),
623    };
624
625    let lines: Vec<&str> = content.lines().collect();
626
627    // Find the line number of old_str
628    let offset = match content.find(old_str) {
629        Some(o) => o,
630        None => return String::new(),
631    };
632    let line_number = content[..offset].matches('\n').count();
633
634    let old_lines: Vec<&str> = old_str.lines().collect();
635    let new_lines: Vec<&str> = new_str.lines().collect();
636
637    // Show context (2 lines before and after)
638    let before_ctx = 2usize;
639    let after_ctx = 2usize;
640    let start_line = line_number.saturating_sub(before_ctx);
641    let end_line = (line_number + old_lines.len() + after_ctx).min(lines.len());
642    let num_width = end_line.to_string().len().max(2);
643
644    let mut result = String::new();
645
646    // Context lines before
647    for (i, line) in lines.iter().enumerate().take(line_number).skip(start_line) {
648        result.push_str(&format!(
649            "  {:>width$} │ {}\n",
650            i + 1,
651            line,
652            width = num_width
653        ));
654    }
655
656    // Removed lines (old)
657    for line in old_lines.iter() {
658        result.push_str(&format!("-       │ {}\n", line));
659    }
660
661    // Added lines (new)
662    for line in new_lines.iter() {
663        result.push_str(&format!("+       │ {}\n", line));
664    }
665
666    // Context lines after
667    let after_start = line_number + old_lines.len();
668    for i in after_start..end_line {
669        if i < lines.len() {
670            result.push_str(&format!(
671                "  {:>width$} │ {}\n",
672                i + 1,
673                lines[i],
674                width = num_width
675            ));
676        }
677    }
678
679    result
680}
681
682#[cfg(test)]
683mod tests {
684    use super::*;
685
686    #[test]
687    fn test_compute_diff_identical() {
688        let old = vec!["a", "b", "c"];
689        let new = vec!["a", "b", "c"];
690        let diff = compute_diff(&old, &new);
691        assert_eq!(
692            diff,
693            vec![
694                DiffLine::Keep("a"),
695                DiffLine::Keep("b"),
696                DiffLine::Keep("c"),
697            ]
698        );
699    }
700
701    #[test]
702    fn test_compute_diff_empty_to_lines() {
703        let old: Vec<&str> = vec![];
704        let new = vec!["a", "b"];
705        let diff = compute_diff(&old, &new);
706        assert_eq!(diff, vec![DiffLine::Add("a"), DiffLine::Add("b")]);
707    }
708
709    #[test]
710    fn test_compute_diff_lines_to_empty() {
711        let old = vec!["a", "b"];
712        let new: Vec<&str> = vec![];
713        let diff = compute_diff(&old, &new);
714        assert_eq!(diff, vec![DiffLine::Remove("a"), DiffLine::Remove("b")]);
715    }
716
717    #[test]
718    fn test_compute_diff_simple_insertion() {
719        let old = vec!["a", "c"];
720        let new = vec!["a", "b", "c"];
721        let diff = compute_diff(&old, &new);
722        assert_eq!(
723            diff,
724            vec![DiffLine::Keep("a"), DiffLine::Add("b"), DiffLine::Keep("c"),]
725        );
726    }
727
728    #[test]
729    fn test_compute_diff_simple_deletion() {
730        let old = vec!["a", "b", "c"];
731        let new = vec!["a", "c"];
732        let diff = compute_diff(&old, &new);
733        assert_eq!(
734            diff,
735            vec![
736                DiffLine::Keep("a"),
737                DiffLine::Remove("b"),
738                DiffLine::Keep("c"),
739            ]
740        );
741    }
742
743    #[test]
744    fn test_compute_diff_replace() {
745        let old = vec!["a", "old", "c"];
746        let new = vec!["a", "new", "c"];
747        let diff = compute_diff(&old, &new);
748        assert_eq!(
749            diff,
750            vec![
751                DiffLine::Keep("a"),
752                DiffLine::Remove("old"),
753                DiffLine::Add("new"),
754                DiffLine::Keep("c"),
755            ]
756        );
757    }
758
759    #[test]
760    fn test_compute_diff_multiple_changes() {
761        let old = vec!["a", "b", "c", "d", "e"];
762        let new = vec!["a", "x", "c", "y", "e"];
763        let diff = compute_diff(&old, &new);
764        assert_eq!(
765            diff,
766            vec![
767                DiffLine::Keep("a"),
768                DiffLine::Remove("b"),
769                DiffLine::Add("x"),
770                DiffLine::Keep("c"),
771                DiffLine::Remove("d"),
772                DiffLine::Add("y"),
773                DiffLine::Keep("e"),
774            ]
775        );
776    }
777
778    #[test]
779    fn test_compute_diff_large_shift() {
780        // Lines rearranged: the old "middle" section is removed and new lines added
781        let old = vec!["keep1", "remove1", "remove2", "remove3", "keep2"];
782        let new = vec!["keep1", "add1", "add2", "keep2"];
783        let diff = compute_diff(&old, &new);
784        let keeps: Vec<_> = diff
785            .iter()
786            .filter(|l| matches!(l, DiffLine::Keep(_)))
787            .collect();
788        let removes: Vec<_> = diff
789            .iter()
790            .filter(|l| matches!(l, DiffLine::Remove(_)))
791            .collect();
792        let adds: Vec<_> = diff
793            .iter()
794            .filter(|l| matches!(l, DiffLine::Add(_)))
795            .collect();
796        assert_eq!(keeps.len(), 2);
797        assert_eq!(removes.len(), 3);
798        assert_eq!(adds.len(), 2);
799        // Keep lines should be in order
800        assert!(matches!(keeps[0], DiffLine::Keep("keep1")));
801        assert!(matches!(keeps[1], DiffLine::Keep("keep2")));
802    }
803
804    #[test]
805    fn test_compute_diff_both_empty() {
806        let old: Vec<&str> = vec![];
807        let new: Vec<&str> = vec![];
808        let diff = compute_diff(&old, &new);
809        assert!(diff.is_empty());
810    }
811
812    #[test]
813    fn test_compute_diff_single_line_change() {
814        let old = vec!["hello world"];
815        let new = vec!["hello rust"];
816        let diff = compute_diff(&old, &new);
817        assert_eq!(
818            diff,
819            vec![DiffLine::Remove("hello world"), DiffLine::Add("hello rust")]
820        );
821    }
822
823    #[test]
824    fn test_compute_diff_prepend_and_append() {
825        let old = vec!["b", "c"];
826        let new = vec!["a", "b", "c", "d"];
827        let diff = compute_diff(&old, &new);
828        assert_eq!(
829            diff,
830            vec![
831                DiffLine::Add("a"),
832                DiffLine::Keep("b"),
833                DiffLine::Keep("c"),
834                DiffLine::Add("d"),
835            ]
836        );
837    }
838
839    #[test]
840    fn test_compute_diff_minimality() {
841        // The diff should produce the minimum number of edits
842        let old = vec!["a", "b", "c", "d", "e", "f"];
843        let new = vec!["a", "c", "d", "e", "g"];
844        let diff = compute_diff(&old, &new);
845        let removes = diff
846            .iter()
847            .filter(|l| matches!(l, DiffLine::Remove(_)))
848            .count();
849        let adds = diff
850            .iter()
851            .filter(|l| matches!(l, DiffLine::Add(_)))
852            .count();
853        // Minimum: remove b, remove f, add g = 2 removes + 1 add = 3 edits
854        assert_eq!(removes, 2);
855        assert_eq!(adds, 1);
856    }
857
858    #[test]
859    fn test_compute_diff_longer_file() {
860        // A more realistic scenario with many lines
861        let old: Vec<String> = (0..50).map(|i| format!("line {}", i)).collect();
862        let mut new = old.clone();
863        // Change lines 10, 20, remove line 30, insert after line 40
864        new[10] = "line 10 modified".to_string();
865        new[20] = "line 20 modified".to_string();
866        new.remove(30);
867        new.insert(41, "inserted line".to_string());
868
869        let old_refs: Vec<&str> = old.iter().map(|s| s.as_str()).collect();
870        let new_refs: Vec<&str> = new.iter().map(|s| s.as_str()).collect();
871
872        let diff = compute_diff(&old_refs, &new_refs);
873
874        let removes = diff
875            .iter()
876            .filter(|l| matches!(l, DiffLine::Remove(_)))
877            .count();
878        let adds = diff
879            .iter()
880            .filter(|l| matches!(l, DiffLine::Add(_)))
881            .count();
882        // 3 removals (line 10 original, line 20 original, line 30) and 3 additions
883        // (modified 10, modified 20, inserted)
884        assert_eq!(removes, 3);
885        assert_eq!(adds, 3);
886    }
887
888    #[test]
889    fn test_compute_diff_reorder() {
890        // Swapping two unique lines
891        let old = vec!["alpha", "beta"];
892        let new = vec!["beta", "alpha"];
893        let diff = compute_diff(&old, &new);
894        // Both lines exist in both files, so one should be kept.
895        // The minimal diff removes and re-adds the reordered line.
896        let keeps = diff
897            .iter()
898            .filter(|l| matches!(l, DiffLine::Keep(_)))
899            .count();
900        assert!(keeps >= 1, "At least one line should be kept in a reorder");
901    }
902
903    #[test]
904    fn test_compute_diff_all_same_then_change() {
905        // Large common prefix, then a change
906        let old: Vec<&str> = vec!["line1", "line2", "line3", "line4", "line5", "old_ending"];
907        let new: Vec<&str> = vec!["line1", "line2", "line3", "line4", "line5", "new_ending"];
908        let diff = compute_diff(&old, &new);
909        assert_eq!(
910            diff,
911            vec![
912                DiffLine::Keep("line1"),
913                DiffLine::Keep("line2"),
914                DiffLine::Keep("line3"),
915                DiffLine::Keep("line4"),
916                DiffLine::Keep("line5"),
917                DiffLine::Remove("old_ending"),
918                DiffLine::Add("new_ending"),
919            ]
920        );
921    }
922}