diffutilslib/
ed_diff.rs

1// This file is part of the uutils diffutils package.
2//
3// For the full copyright and license information, please view the LICENSE-*
4// files that was distributed with this source code.
5
6use std::io::Write;
7
8use crate::params::Params;
9use crate::utils::do_write_line;
10
11#[derive(Debug, PartialEq)]
12struct Mismatch {
13    pub line_number_expected: usize,
14    pub line_number_actual: usize,
15    pub expected: Vec<Vec<u8>>,
16    pub actual: Vec<Vec<u8>>,
17}
18
19#[derive(Debug, PartialEq, Eq)]
20pub enum DiffError {
21    MissingNL,
22}
23
24impl std::fmt::Display for DiffError {
25    fn fmt(&self, f: &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> {
26        std::fmt::Display::fmt("No newline at end of file", f)
27    }
28}
29
30impl From<DiffError> for String {
31    fn from(_: DiffError) -> String {
32        "No newline at end of file".into()
33    }
34}
35
36impl Mismatch {
37    fn new(line_number_expected: usize, line_number_actual: usize) -> Mismatch {
38        Mismatch {
39            line_number_expected,
40            line_number_actual,
41            expected: Vec::new(),
42            actual: Vec::new(),
43        }
44    }
45}
46
47// Produces a diff between the expected output and actual output.
48fn make_diff(expected: &[u8], actual: &[u8], stop_early: bool) -> Result<Vec<Mismatch>, DiffError> {
49    let mut line_number_expected = 1;
50    let mut line_number_actual = 1;
51    let mut results = Vec::new();
52    let mut mismatch = Mismatch::new(line_number_expected, line_number_actual);
53
54    let mut expected_lines: Vec<&[u8]> = expected.split(|&c| c == b'\n').collect();
55    let mut actual_lines: Vec<&[u8]> = actual.split(|&c| c == b'\n').collect();
56
57    debug_assert_eq!(b"".split(|&c| c == b'\n').count(), 1);
58    // ^ means that underflow here is impossible
59    let _expected_lines_count = expected_lines.len() - 1;
60    let _actual_lines_count = actual_lines.len() - 1;
61
62    if expected_lines.last() == Some(&&b""[..]) {
63        expected_lines.pop();
64    } else {
65        return Err(DiffError::MissingNL);
66    }
67
68    if actual_lines.last() == Some(&&b""[..]) {
69        actual_lines.pop();
70    } else {
71        return Err(DiffError::MissingNL);
72    }
73
74    for result in diff::slice(&expected_lines, &actual_lines) {
75        match result {
76            diff::Result::Left(str) => {
77                if !mismatch.actual.is_empty() {
78                    results.push(mismatch);
79                    mismatch = Mismatch::new(line_number_expected, line_number_actual);
80                }
81                mismatch.expected.push(str.to_vec());
82                line_number_expected += 1;
83            }
84            diff::Result::Right(str) => {
85                mismatch.actual.push(str.to_vec());
86                line_number_actual += 1;
87            }
88            diff::Result::Both(_str, _) => {
89                line_number_expected += 1;
90                line_number_actual += 1;
91                if !mismatch.actual.is_empty() || !mismatch.expected.is_empty() {
92                    results.push(mismatch);
93                    mismatch = Mismatch::new(line_number_expected, line_number_actual);
94                } else {
95                    mismatch.line_number_expected = line_number_expected;
96                    mismatch.line_number_actual = line_number_actual;
97                }
98            }
99        }
100        if stop_early && !results.is_empty() {
101            // Optimization: stop analyzing the files as soon as there are any differences
102            return Ok(results);
103        }
104    }
105
106    if !mismatch.actual.is_empty() || !mismatch.expected.is_empty() {
107        results.push(mismatch);
108    }
109
110    Ok(results)
111}
112
113pub fn diff(expected: &[u8], actual: &[u8], params: &Params) -> Result<Vec<u8>, DiffError> {
114    let mut output = Vec::new();
115    let diff_results = make_diff(expected, actual, params.brief)?;
116    if params.brief && !diff_results.is_empty() {
117        write!(&mut output, "\0").unwrap();
118        return Ok(output);
119    }
120    let mut lines_offset = 0;
121    for result in diff_results {
122        let line_number_expected: isize = result.line_number_expected as isize + lines_offset;
123        let _line_number_actual: isize = result.line_number_actual as isize + lines_offset;
124        let expected_count: isize = result.expected.len() as isize;
125        let actual_count: isize = result.actual.len() as isize;
126        match (expected_count, actual_count) {
127            (0, 0) => unreachable!(),
128            (0, _) => writeln!(&mut output, "{}a", line_number_expected - 1).unwrap(),
129            (_, 0) => writeln!(
130                &mut output,
131                "{},{}d",
132                line_number_expected,
133                expected_count + line_number_expected - 1
134            )
135            .unwrap(),
136            (1, _) => writeln!(&mut output, "{line_number_expected}c").unwrap(),
137            _ => writeln!(
138                &mut output,
139                "{},{}c",
140                line_number_expected,
141                expected_count + line_number_expected - 1
142            )
143            .unwrap(),
144        }
145        lines_offset += actual_count - expected_count;
146        if actual_count != 0 {
147            for actual in &result.actual {
148                if actual == b"." {
149                    writeln!(&mut output, "..\n.\ns/.//\na").unwrap();
150                } else {
151                    do_write_line(&mut output, actual, params.expand_tabs, params.tabsize).unwrap();
152                    writeln!(&mut output).unwrap();
153                }
154            }
155            writeln!(&mut output, ".").unwrap();
156        }
157    }
158    Ok(output)
159}
160
161#[cfg(test)]
162mod tests {
163    use super::*;
164    use pretty_assertions::assert_eq;
165    pub fn diff_w(expected: &[u8], actual: &[u8], filename: &str) -> Result<Vec<u8>, DiffError> {
166        let mut output = diff(expected, actual, &Params::default())?;
167        writeln!(&mut output, "w {filename}").unwrap();
168        Ok(output)
169    }
170
171    #[test]
172    fn test_basic() {
173        let from = b"a\n";
174        let to = b"b\n";
175        let diff = diff(from, to, &Params::default()).unwrap();
176        let expected = ["1c", "b", ".", ""].join("\n");
177        assert_eq!(diff, expected.as_bytes());
178    }
179
180    #[test]
181    fn test_permutations() {
182        let target = "target/ed-diff/";
183        // test all possible six-line files.
184        let _ = std::fs::create_dir(target);
185        for &a in &[0, 1, 2] {
186            for &b in &[0, 1, 2] {
187                for &c in &[0, 1, 2] {
188                    for &d in &[0, 1, 2] {
189                        for &e in &[0, 1, 2] {
190                            for &f in &[0, 1, 2] {
191                                use std::fs::File;
192                                use std::io::Write;
193                                let mut alef = Vec::new();
194                                let mut bet = Vec::new();
195                                alef.write_all(if a == 0 { b"a\n" } else { b"b\n" })
196                                    .unwrap();
197                                if a != 2 {
198                                    bet.write_all(b"b\n").unwrap();
199                                }
200                                alef.write_all(if b == 0 { b"c\n" } else { b"d\n" })
201                                    .unwrap();
202                                if b != 2 {
203                                    bet.write_all(b"d\n").unwrap();
204                                }
205                                alef.write_all(if c == 0 { b"e\n" } else { b"f\n" })
206                                    .unwrap();
207                                if c != 2 {
208                                    bet.write_all(b"f\n").unwrap();
209                                }
210                                alef.write_all(if d == 0 { b"g\n" } else { b"h\n" })
211                                    .unwrap();
212                                if d != 2 {
213                                    bet.write_all(b"h\n").unwrap();
214                                }
215                                alef.write_all(if e == 0 { b"i\n" } else { b"j\n" })
216                                    .unwrap();
217                                if e != 2 {
218                                    bet.write_all(b"j\n").unwrap();
219                                }
220                                alef.write_all(if f == 0 { b"k\n" } else { b"l\n" })
221                                    .unwrap();
222                                if f != 2 {
223                                    bet.write_all(b"l\n").unwrap();
224                                }
225                                // This test diff is intentionally reversed.
226                                // We want it to turn the alef into bet.
227                                let diff = diff_w(&alef, &bet, &format!("{target}/alef")).unwrap();
228                                File::create(format!("{target}/ab.ed"))
229                                    .unwrap()
230                                    .write_all(&diff)
231                                    .unwrap();
232                                let mut fa = File::create(format!("{target}/alef")).unwrap();
233                                fa.write_all(&alef[..]).unwrap();
234                                let mut fb = File::create(format!("{target}/bet")).unwrap();
235                                fb.write_all(&bet[..]).unwrap();
236                                let _ = fa;
237                                let _ = fb;
238                                #[cfg(not(windows))] // there's no ed on windows
239                                {
240                                    use std::process::Command;
241                                    let output = Command::new("ed")
242                                        .arg(format!("{target}/alef"))
243                                        .stdin(File::open(format!("{target}/ab.ed")).unwrap())
244                                        .output()
245                                        .unwrap();
246                                    assert!(output.status.success(), "{output:?}");
247                                    //println!("{}", String::from_utf8_lossy(&output.stdout));
248                                    //println!("{}", String::from_utf8_lossy(&output.stderr));
249                                    let alef = std::fs::read(format!("{target}/alef")).unwrap();
250                                    assert_eq!(alef, bet);
251                                }
252                            }
253                        }
254                    }
255                }
256            }
257        }
258    }
259
260    #[test]
261    fn test_permutations_empty_lines() {
262        let target = "target/ed-diff/";
263        // test all possible six-line files with missing newlines.
264        let _ = std::fs::create_dir(target);
265        for &a in &[0, 1, 2] {
266            for &b in &[0, 1, 2] {
267                for &c in &[0, 1, 2] {
268                    for &d in &[0, 1, 2] {
269                        for &e in &[0, 1, 2] {
270                            for &f in &[0, 1, 2] {
271                                use std::fs::File;
272                                use std::io::Write;
273                                let mut alef = Vec::new();
274                                let mut bet = Vec::new();
275                                alef.write_all(if a == 0 { b"\n" } else { b"b\n" }).unwrap();
276                                if a != 2 {
277                                    bet.write_all(b"b\n").unwrap();
278                                }
279                                alef.write_all(if b == 0 { b"\n" } else { b"d\n" }).unwrap();
280                                if b != 2 {
281                                    bet.write_all(b"d\n").unwrap();
282                                }
283                                alef.write_all(if c == 0 { b"\n" } else { b"f\n" }).unwrap();
284                                if c != 2 {
285                                    bet.write_all(b"f\n").unwrap();
286                                }
287                                alef.write_all(if d == 0 { b"\n" } else { b"h\n" }).unwrap();
288                                if d != 2 {
289                                    bet.write_all(b"h\n").unwrap();
290                                }
291                                alef.write_all(if e == 0 { b"\n" } else { b"j\n" }).unwrap();
292                                if e != 2 {
293                                    bet.write_all(b"j\n").unwrap();
294                                }
295                                alef.write_all(if f == 0 { b"\n" } else { b"l\n" }).unwrap();
296                                if f != 2 {
297                                    bet.write_all(b"l\n").unwrap();
298                                }
299                                // This test diff is intentionally reversed.
300                                // We want it to turn the alef into bet.
301                                let diff = diff_w(&alef, &bet, &format!("{target}/alef_")).unwrap();
302                                File::create(format!("{target}/ab_.ed"))
303                                    .unwrap()
304                                    .write_all(&diff)
305                                    .unwrap();
306                                let mut fa = File::create(format!("{target}/alef_")).unwrap();
307                                fa.write_all(&alef[..]).unwrap();
308                                let mut fb = File::create(format!("{target}/bet_")).unwrap();
309                                fb.write_all(&bet[..]).unwrap();
310                                let _ = fa;
311                                let _ = fb;
312                                #[cfg(not(windows))] // there's no ed on windows
313                                {
314                                    use std::process::Command;
315                                    let output = Command::new("ed")
316                                        .arg(format!("{target}/alef_"))
317                                        .stdin(File::open(format!("{target}/ab_.ed")).unwrap())
318                                        .output()
319                                        .unwrap();
320                                    assert!(output.status.success(), "{output:?}");
321                                    //println!("{}", String::from_utf8_lossy(&output.stdout));
322                                    //println!("{}", String::from_utf8_lossy(&output.stderr));
323                                    let alef = std::fs::read(format!("{target}/alef_")).unwrap();
324                                    assert_eq!(alef, bet);
325                                }
326                            }
327                        }
328                    }
329                }
330            }
331        }
332    }
333
334    #[test]
335    fn test_permutations_reverse() {
336        let target = "target/ed-diff/";
337        // test all possible six-line files.
338        let _ = std::fs::create_dir(target);
339        for &a in &[0, 1, 2] {
340            for &b in &[0, 1, 2] {
341                for &c in &[0, 1, 2] {
342                    for &d in &[0, 1, 2] {
343                        for &e in &[0, 1, 2] {
344                            for &f in &[0, 1, 2] {
345                                use std::fs::File;
346                                use std::io::Write;
347                                let mut alef = Vec::new();
348                                let mut bet = Vec::new();
349                                alef.write_all(if a == 0 { b"a\n" } else { b"f\n" })
350                                    .unwrap();
351                                if a != 2 {
352                                    bet.write_all(b"a\n").unwrap();
353                                }
354                                alef.write_all(if b == 0 { b"b\n" } else { b"e\n" })
355                                    .unwrap();
356                                if b != 2 {
357                                    bet.write_all(b"b\n").unwrap();
358                                }
359                                alef.write_all(if c == 0 { b"c\n" } else { b"d\n" })
360                                    .unwrap();
361                                if c != 2 {
362                                    bet.write_all(b"c\n").unwrap();
363                                }
364                                alef.write_all(if d == 0 { b"d\n" } else { b"c\n" })
365                                    .unwrap();
366                                if d != 2 {
367                                    bet.write_all(b"d\n").unwrap();
368                                }
369                                alef.write_all(if e == 0 { b"e\n" } else { b"b\n" })
370                                    .unwrap();
371                                if e != 2 {
372                                    bet.write_all(b"e\n").unwrap();
373                                }
374                                alef.write_all(if f == 0 { b"f\n" } else { b"a\n" })
375                                    .unwrap();
376                                if f != 2 {
377                                    bet.write_all(b"f\n").unwrap();
378                                }
379                                // This test diff is intentionally reversed.
380                                // We want it to turn the alef into bet.
381                                let diff = diff_w(&alef, &bet, &format!("{target}/alefr")).unwrap();
382                                File::create(format!("{target}/abr.ed"))
383                                    .unwrap()
384                                    .write_all(&diff)
385                                    .unwrap();
386                                let mut fa = File::create(format!("{target}/alefr")).unwrap();
387                                fa.write_all(&alef[..]).unwrap();
388                                let mut fb = File::create(format!("{target}/betr")).unwrap();
389                                fb.write_all(&bet[..]).unwrap();
390                                let _ = fa;
391                                let _ = fb;
392                                #[cfg(not(windows))] // there's no ed on windows
393                                {
394                                    use std::process::Command;
395                                    let output = Command::new("ed")
396                                        .arg(format!("{target}/alefr"))
397                                        .stdin(File::open(format!("{target}/abr.ed")).unwrap())
398                                        .output()
399                                        .unwrap();
400                                    assert!(output.status.success(), "{output:?}");
401                                    //println!("{}", String::from_utf8_lossy(&output.stdout));
402                                    //println!("{}", String::from_utf8_lossy(&output.stderr));
403                                    let alef = std::fs::read(format!("{target}/alefr")).unwrap();
404                                    assert_eq!(alef, bet);
405                                }
406                            }
407                        }
408                    }
409                }
410            }
411        }
412    }
413
414    #[test]
415    fn test_stop_early() {
416        let from = ["a", "b", "c", ""].join("\n");
417        let to = ["a", "d", "c", ""].join("\n");
418
419        let diff_full = diff(from.as_bytes(), to.as_bytes(), &Params::default()).unwrap();
420        let expected_full = ["2c", "d", ".", ""].join("\n");
421        assert_eq!(diff_full, expected_full.as_bytes());
422
423        let diff_brief = diff(
424            from.as_bytes(),
425            to.as_bytes(),
426            &Params {
427                brief: true,
428                ..Default::default()
429            },
430        )
431        .unwrap();
432        let expected_brief = "\0".as_bytes();
433        assert_eq!(diff_brief, expected_brief);
434
435        let nodiff_full = diff(from.as_bytes(), from.as_bytes(), &Params::default()).unwrap();
436        assert!(nodiff_full.is_empty());
437
438        let nodiff_brief = diff(
439            from.as_bytes(),
440            from.as_bytes(),
441            &Params {
442                brief: true,
443                ..Default::default()
444            },
445        )
446        .unwrap();
447        assert!(nodiff_brief.is_empty());
448    }
449}