1//! Basic diff functions
2use crate::lcs;
3use std::fmt;
4use owo_colors::OwoColorize;
5
6/// Single change in original slice needed to get new slice
7#[derive(Debug, PartialEq, Eq)]
8pub enum DiffOp<'a, T: 'a> {
9 /// Appears only in second slice
10 Insert(&'a [T]),
11 /// Appears in both slices, but changed
12 Replace(&'a [T], &'a [T]),
13 /// Appears only in first slice
14 Remove(&'a [T]),
15 /// Appears on both slices
16 Equal(&'a [T]),
17}
18
19/// Diffs any slices which implements PartialEq
20pub fn diff<'a, T: PartialEq>(x: &'a [T], y: &'a [T]) -> Vec<DiffOp<'a, T>> {
21 let mut ops: Vec<DiffOp<T>> = Vec::new();
22 let table = lcs::Table::new(x, y);
23
24 let mut i = 0;
25 let mut j = 0;
26
27 for m in table.matches_zero() {
28 let x_seq = &x[i..m.x];
29 let y_seq = &y[j..m.y];
30
31 if i < m.x && j < m.y {
32 ops.push(DiffOp::Replace(x_seq, y_seq));
33 } else if i < m.x {
34 ops.push(DiffOp::Remove(x_seq));
35 } else if j < m.y {
36 ops.push(DiffOp::Insert(y_seq));
37 }
38
39 i = m.x + m.len;
40 j = m.y + m.len;
41
42 if m.len > 0 {
43 ops.push(DiffOp::Equal(&x[m.x..i]));
44 }
45 }
46 ops
47}
48
49/// Container for slice diff result. Can be pretty-printed by Display trait.
50#[derive(Debug, PartialEq, Eq)]
51pub struct SliceChangeset<'a, T> {
52 pub diff: Vec<DiffOp<'a, T>>,
53}
54
55impl<'a, T: fmt::Display> SliceChangeset<'a, T> {
56 pub fn format(&self, skip_same: bool) -> String {
57 let mut out: Vec<String> = Vec::with_capacity(self.diff.len());
58 for op in &self.diff {
59 match op {
60 DiffOp::Equal(a) => {
61 if !skip_same || a.len() == 1 {
62 for i in a.iter() {
63 out.push(format!(" {}", i))
64 }
65 } else if a.len() > 1 {
66 out.push(format!(" ... skip({}) ...", a.len()));
67 }
68 }
69
70 DiffOp::Insert(a) => {
71 for i in a.iter() {
72 out.push((format!("+ {}", i).green()).to_string());
73 }
74 }
75
76 DiffOp::Remove(a) => {
77 for i in a.iter() {
78 out.push(format!("- {}", i).red().to_string());
79 }
80 }
81 DiffOp::Replace(a, b) => {
82 let min_len = std::cmp::min(a.len(), b.len());
83 let max_len = std::cmp::max(a.len(), b.len());
84
85 for i in 0..min_len {
86 out.push(
87 format!("~ {} -> {}", a[i], b[i])
88 .yellow()
89 .to_string(),
90 );
91 }
92 for i in min_len..max_len {
93 if max_len == a.len() {
94 out.push(format!("- {}", a[i]).red().to_string());
95 } else {
96 out.push(format!("+ {}", b[i]).green().to_string());
97 }
98 }
99 }
100 }
101 }
102 format!("[\n{}\n]", out.join(",\n"))
103 }
104}
105
106impl<'a, T: fmt::Display> fmt::Display for SliceChangeset<'a, T> {
107 fn fmt(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
108 write!(formatter, "{}", self.format(true))
109 }
110}
111
112/// Diff two arbitary slices with elements that support Display trait
113pub fn diff_slice<'a, T: PartialEq + std::fmt::Display>(
114 x: &'a [T],
115 y: &'a [T],
116) -> SliceChangeset<'a, T> {
117 let diff: Vec> = diff(x, y);
118 SliceChangeset { diff }
119}
120
121#[test]
122fn test_basic() {
123 assert_eq!(
124 diff(&[1, 2, 3, 4, 5, 6], &[2, 3, 5, 7]),
125 vec![
126 DiffOp::Remove(&[1]),
127 DiffOp::Equal(&[2, 3]),
128 DiffOp::Remove(&[4]),
129 DiffOp::Equal(&[5]),
130 DiffOp::Replace(&[6], &[7]),
131 ]
132 );
133
134 assert_eq!(
135 diff_slice(
136 &["q", "a", "b", "x", "c", "d"],
137 &["a", "b", "y", "c", "d", "f"],
138 )
139 .diff,
140 vec![
141 DiffOp::Remove(&["q"]),
142 DiffOp::Equal(&["a", "b"]),
143 DiffOp::Replace(&["x"], &["y"]),
144 DiffOp::Equal(&["c", "d"]),
145 DiffOp::Insert(&["f"]),
146 ]
147 );
148
149 assert_eq!(
150 diff(&["a", "c", "d", "b"], &["a", "e", "b"]),
151 vec![
152 DiffOp::Equal(&["a"]),
153 DiffOp::Replace(&["c", "d"], &["e"]),
154 DiffOp::Equal(&["b"]),
155 ]
156 );
157 println!("Diff: {}", diff_slice(&[1, 2, 3, 4, 5, 6], &[2, 3, 5, 7]));
158 println!(
159 "Diff: {}",
160 diff_slice(
161 &["q", "a", "b", "x", "c", "d"],
162 &["a", "b", "y", "c", "d", "f"]
163 )
164 );
165 println!(
166 "Diff: {}",
167 diff_slice(&["a", "c", "d", "b"], &["a", "e", "b"])
168 );
169}
170