diffutilslib/
normal_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    pub expected_missing_nl: bool,
18    pub actual_missing_nl: bool,
19}
20
21impl Mismatch {
22    fn new(line_number_expected: usize, line_number_actual: usize) -> Mismatch {
23        Mismatch {
24            line_number_expected,
25            line_number_actual,
26            expected: Vec::new(),
27            actual: Vec::new(),
28            expected_missing_nl: false,
29            actual_missing_nl: false,
30        }
31    }
32}
33
34// Produces a diff between the expected output and actual output.
35fn make_diff(expected: &[u8], actual: &[u8], stop_early: bool) -> Vec<Mismatch> {
36    let mut line_number_expected = 1;
37    let mut line_number_actual = 1;
38    let mut results = Vec::new();
39    let mut mismatch = Mismatch::new(line_number_expected, line_number_actual);
40
41    let mut expected_lines: Vec<&[u8]> = expected.split(|&c| c == b'\n').collect();
42    let mut actual_lines: Vec<&[u8]> = actual.split(|&c| c == b'\n').collect();
43
44    debug_assert_eq!(b"".split(|&c| c == b'\n').count(), 1);
45    // ^ means that underflow here is impossible
46    let expected_lines_count = expected_lines.len() - 1;
47    let actual_lines_count = actual_lines.len() - 1;
48
49    if expected_lines.last() == Some(&&b""[..]) {
50        expected_lines.pop();
51    }
52
53    if actual_lines.last() == Some(&&b""[..]) {
54        actual_lines.pop();
55    }
56
57    for result in diff::slice(&expected_lines, &actual_lines) {
58        match result {
59            diff::Result::Left(str) => {
60                if !mismatch.actual.is_empty() && !mismatch.actual_missing_nl {
61                    results.push(mismatch);
62                    mismatch = Mismatch::new(line_number_expected, line_number_actual);
63                }
64                mismatch.expected.push(str.to_vec());
65                mismatch.expected_missing_nl = line_number_expected > expected_lines_count;
66                line_number_expected += 1;
67            }
68            diff::Result::Right(str) => {
69                mismatch.actual.push(str.to_vec());
70                mismatch.actual_missing_nl = line_number_actual > actual_lines_count;
71                line_number_actual += 1;
72            }
73            diff::Result::Both(str, _) => {
74                match (
75                    line_number_expected > expected_lines_count,
76                    line_number_actual > actual_lines_count,
77                ) {
78                    (true, false) => {
79                        line_number_expected += 1;
80                        line_number_actual += 1;
81                        mismatch.expected.push(str.to_vec());
82                        mismatch.expected_missing_nl = true;
83                        mismatch.actual.push(str.to_vec());
84                    }
85                    (false, true) => {
86                        line_number_expected += 1;
87                        line_number_actual += 1;
88                        mismatch.actual.push(str.to_vec());
89                        mismatch.actual_missing_nl = true;
90                        mismatch.expected.push(str.to_vec());
91                    }
92                    (true, true) | (false, false) => {
93                        line_number_expected += 1;
94                        line_number_actual += 1;
95                        if !mismatch.actual.is_empty() || !mismatch.expected.is_empty() {
96                            results.push(mismatch);
97                            mismatch = Mismatch::new(line_number_expected, line_number_actual);
98                        } else {
99                            mismatch.line_number_expected = line_number_expected;
100                            mismatch.line_number_actual = line_number_actual;
101                        }
102                    }
103                }
104            }
105        }
106        if stop_early && !results.is_empty() {
107            // Optimization: stop analyzing the files as soon as there are any differences
108            return results;
109        }
110    }
111
112    if !mismatch.actual.is_empty() || !mismatch.expected.is_empty() {
113        results.push(mismatch);
114    }
115
116    results
117}
118
119#[must_use]
120pub fn diff(expected: &[u8], actual: &[u8], params: &Params) -> Vec<u8> {
121    // See https://www.gnu.org/software/diffutils/manual/html_node/Detailed-Normal.html
122    // for details on the syntax of the normal format.
123    let mut output = Vec::new();
124    let diff_results = make_diff(expected, actual, params.brief);
125    if params.brief && !diff_results.is_empty() {
126        write!(&mut output, "\0").unwrap();
127        return output;
128    }
129    for result in diff_results {
130        let line_number_expected = result.line_number_expected;
131        let line_number_actual = result.line_number_actual;
132        let expected_count = result.expected.len();
133        let actual_count = result.actual.len();
134        match (expected_count, actual_count) {
135            (0, 0) => unreachable!(),
136            (0, _) => writeln!(
137                // 'a' stands for "Add lines"
138                &mut output,
139                "{}a{},{}",
140                line_number_expected - 1,
141                line_number_actual,
142                line_number_actual + actual_count - 1
143            )
144            .unwrap(),
145            (_, 0) => writeln!(
146                // 'd' stands for "Delete lines"
147                &mut output,
148                "{},{}d{}",
149                line_number_expected,
150                expected_count + line_number_expected - 1,
151                line_number_actual - 1
152            )
153            .unwrap(),
154            (1, 1) => writeln!(
155                // 'c' stands for "Change lines"
156                // exactly one line replaced by one line
157                &mut output,
158                "{line_number_expected}c{line_number_actual}"
159            )
160            .unwrap(),
161            (1, _) => writeln!(
162                // one line replaced by multiple lines
163                &mut output,
164                "{}c{},{}",
165                line_number_expected,
166                line_number_actual,
167                actual_count + line_number_actual - 1
168            )
169            .unwrap(),
170            (_, 1) => writeln!(
171                // multiple lines replaced by one line
172                &mut output,
173                "{},{}c{}",
174                line_number_expected,
175                expected_count + line_number_expected - 1,
176                line_number_actual
177            )
178            .unwrap(),
179            _ => writeln!(
180                // general case: multiple lines replaced by multiple lines
181                &mut output,
182                "{},{}c{},{}",
183                line_number_expected,
184                expected_count + line_number_expected - 1,
185                line_number_actual,
186                actual_count + line_number_actual - 1
187            )
188            .unwrap(),
189        }
190        for expected in &result.expected {
191            write!(&mut output, "< ").unwrap();
192            do_write_line(&mut output, expected, params.expand_tabs, params.tabsize).unwrap();
193            writeln!(&mut output).unwrap();
194        }
195        if result.expected_missing_nl {
196            writeln!(&mut output, r"\ No newline at end of file").unwrap();
197        }
198        if expected_count != 0 && actual_count != 0 {
199            writeln!(&mut output, "---").unwrap();
200        }
201        for actual in &result.actual {
202            write!(&mut output, "> ").unwrap();
203            do_write_line(&mut output, actual, params.expand_tabs, params.tabsize).unwrap();
204            writeln!(&mut output).unwrap();
205        }
206        if result.actual_missing_nl {
207            writeln!(&mut output, r"\ No newline at end of file").unwrap();
208        }
209    }
210    output
211}
212
213#[cfg(test)]
214mod tests {
215    use super::*;
216    use pretty_assertions::assert_eq;
217
218    #[test]
219    fn test_basic() {
220        let mut a = Vec::new();
221        a.write_all(b"a\n").unwrap();
222        let mut b = Vec::new();
223        b.write_all(b"b\n").unwrap();
224        let diff = diff(&a, &b, &Params::default());
225        let expected = b"1c1\n< a\n---\n> b\n".to_vec();
226        assert_eq!(diff, expected);
227    }
228
229    #[test]
230    fn test_permutations() {
231        let target = "target/normal-diff/";
232        // test all possible six-line files.
233        let _ = std::fs::create_dir(target);
234        for &a in &[0, 1, 2] {
235            for &b in &[0, 1, 2] {
236                for &c in &[0, 1, 2] {
237                    for &d in &[0, 1, 2] {
238                        for &e in &[0, 1, 2] {
239                            for &f in &[0, 1, 2] {
240                                use std::fs::{self, File};
241                                use std::io::Write;
242                                use std::process::Command;
243                                let mut alef = Vec::new();
244                                let mut bet = Vec::new();
245                                alef.write_all(if a == 0 { b"a\n" } else { b"b\n" })
246                                    .unwrap();
247                                if a != 2 {
248                                    bet.write_all(b"b\n").unwrap();
249                                }
250                                alef.write_all(if b == 0 { b"c\n" } else { b"d\n" })
251                                    .unwrap();
252                                if b != 2 {
253                                    bet.write_all(b"d\n").unwrap();
254                                }
255                                alef.write_all(if c == 0 { b"e\n" } else { b"f\n" })
256                                    .unwrap();
257                                if c != 2 {
258                                    bet.write_all(b"f\n").unwrap();
259                                }
260                                alef.write_all(if d == 0 { b"g\n" } else { b"h\n" })
261                                    .unwrap();
262                                if d != 2 {
263                                    bet.write_all(b"h\n").unwrap();
264                                }
265                                alef.write_all(if e == 0 { b"i\n" } else { b"j\n" })
266                                    .unwrap();
267                                if e != 2 {
268                                    bet.write_all(b"j\n").unwrap();
269                                }
270                                alef.write_all(if f == 0 { b"k\n" } else { b"l\n" })
271                                    .unwrap();
272                                if f != 2 {
273                                    bet.write_all(b"l\n").unwrap();
274                                }
275                                // This test diff is intentionally reversed.
276                                // We want it to turn the alef into bet.
277                                let diff = diff(&alef, &bet, &Params::default());
278                                File::create(format!("{target}/ab.diff"))
279                                    .unwrap()
280                                    .write_all(&diff)
281                                    .unwrap();
282                                let mut fa = File::create(format!("{target}/alef")).unwrap();
283                                fa.write_all(&alef[..]).unwrap();
284                                let mut fb = File::create(format!("{target}/bet")).unwrap();
285                                fb.write_all(&bet[..]).unwrap();
286                                let _ = fa;
287                                let _ = fb;
288                                let output = Command::new("patch")
289                                    .arg("-p0")
290                                    .arg(format!("{target}/alef"))
291                                    .stdin(File::open(format!("{target}/ab.diff")).unwrap())
292                                    .output()
293                                    .unwrap();
294                                assert!(output.status.success(), "{output:?}");
295                                //println!("{}", String::from_utf8_lossy(&output.stdout));
296                                //println!("{}", String::from_utf8_lossy(&output.stderr));
297                                let alef = fs::read(format!("{target}/alef")).unwrap();
298                                assert_eq!(alef, bet);
299                            }
300                        }
301                    }
302                }
303            }
304        }
305    }
306
307    #[test]
308    fn test_permutations_missing_line_ending() {
309        let target = "target/normal-diff/";
310        // test all possible six-line files with missing newlines.
311        let _ = std::fs::create_dir(target);
312        for &a in &[0, 1, 2] {
313            for &b in &[0, 1, 2] {
314                for &c in &[0, 1, 2] {
315                    for &d in &[0, 1, 2] {
316                        for &e in &[0, 1, 2] {
317                            for &f in &[0, 1, 2] {
318                                for &g in &[0, 1, 2] {
319                                    use std::fs::{self, File};
320                                    use std::io::Write;
321                                    use std::process::Command;
322                                    let mut alef = Vec::new();
323                                    let mut bet = Vec::new();
324                                    alef.write_all(if a == 0 { b"a\n" } else { b"b\n" })
325                                        .unwrap();
326                                    if a != 2 {
327                                        bet.write_all(b"b\n").unwrap();
328                                    }
329                                    alef.write_all(if b == 0 { b"c\n" } else { b"d\n" })
330                                        .unwrap();
331                                    if b != 2 {
332                                        bet.write_all(b"d\n").unwrap();
333                                    }
334                                    alef.write_all(if c == 0 { b"e\n" } else { b"f\n" })
335                                        .unwrap();
336                                    if c != 2 {
337                                        bet.write_all(b"f\n").unwrap();
338                                    }
339                                    alef.write_all(if d == 0 { b"g\n" } else { b"h\n" })
340                                        .unwrap();
341                                    if d != 2 {
342                                        bet.write_all(b"h\n").unwrap();
343                                    }
344                                    alef.write_all(if e == 0 { b"i\n" } else { b"j\n" })
345                                        .unwrap();
346                                    if e != 2 {
347                                        bet.write_all(b"j\n").unwrap();
348                                    }
349                                    alef.write_all(if f == 0 { b"k\n" } else { b"l\n" })
350                                        .unwrap();
351                                    if f != 2 {
352                                        bet.write_all(b"l\n").unwrap();
353                                    }
354                                    match g {
355                                        0 => {
356                                            alef.pop();
357                                        }
358                                        1 => {
359                                            bet.pop();
360                                        }
361                                        2 => {
362                                            alef.pop();
363                                            bet.pop();
364                                        }
365                                        _ => unreachable!(),
366                                    }
367                                    // This test diff is intentionally reversed.
368                                    // We want it to turn the alef into bet.
369                                    let diff = diff(&alef, &bet, &Params::default());
370                                    File::create(format!("{target}/abn.diff"))
371                                        .unwrap()
372                                        .write_all(&diff)
373                                        .unwrap();
374                                    let mut fa = File::create(format!("{target}/alefn")).unwrap();
375                                    fa.write_all(&alef[..]).unwrap();
376                                    let mut fb = File::create(format!("{target}/betn")).unwrap();
377                                    fb.write_all(&bet[..]).unwrap();
378                                    let _ = fa;
379                                    let _ = fb;
380                                    let output = Command::new("patch")
381                                        .arg("-p0")
382                                        .arg("--normal")
383                                        .arg(format!("{target}/alefn"))
384                                        .stdin(File::open(format!("{target}/abn.diff")).unwrap())
385                                        .output()
386                                        .unwrap();
387                                    assert!(output.status.success(), "{output:?}");
388                                    //println!("{}", String::from_utf8_lossy(&output.stdout));
389                                    //println!("{}", String::from_utf8_lossy(&output.stderr));
390                                    let alef = fs::read(format!("{target}/alefn")).unwrap();
391                                    assert_eq!(alef, bet);
392                                }
393                            }
394                        }
395                    }
396                }
397            }
398        }
399    }
400
401    #[test]
402    fn test_permutations_empty_lines() {
403        let target = "target/normal-diff/";
404        // test all possible six-line files with missing newlines.
405        let _ = std::fs::create_dir(target);
406        for &a in &[0, 1, 2] {
407            for &b in &[0, 1, 2] {
408                for &c in &[0, 1, 2] {
409                    for &d in &[0, 1, 2] {
410                        for &e in &[0, 1, 2] {
411                            for &f in &[0, 1, 2] {
412                                use std::fs::{self, File};
413                                use std::io::Write;
414                                use std::process::Command;
415                                let mut alef = Vec::new();
416                                let mut bet = Vec::new();
417                                alef.write_all(if a == 0 { b"\n" } else { b"b\n" }).unwrap();
418                                if a != 2 {
419                                    bet.write_all(b"b\n").unwrap();
420                                }
421                                alef.write_all(if b == 0 { b"\n" } else { b"d\n" }).unwrap();
422                                if b != 2 {
423                                    bet.write_all(b"d\n").unwrap();
424                                }
425                                alef.write_all(if c == 0 { b"\n" } else { b"f\n" }).unwrap();
426                                if c != 2 {
427                                    bet.write_all(b"f\n").unwrap();
428                                }
429                                alef.write_all(if d == 0 { b"\n" } else { b"h\n" }).unwrap();
430                                if d != 2 {
431                                    bet.write_all(b"h\n").unwrap();
432                                }
433                                alef.write_all(if e == 0 { b"\n" } else { b"j\n" }).unwrap();
434                                if e != 2 {
435                                    bet.write_all(b"j\n").unwrap();
436                                }
437                                alef.write_all(if f == 0 { b"\n" } else { b"l\n" }).unwrap();
438                                if f != 2 {
439                                    bet.write_all(b"l\n").unwrap();
440                                }
441                                // This test diff is intentionally reversed.
442                                // We want it to turn the alef into bet.
443                                let diff = diff(&alef, &bet, &Params::default());
444                                File::create(format!("{target}/ab_.diff"))
445                                    .unwrap()
446                                    .write_all(&diff)
447                                    .unwrap();
448                                let mut fa = File::create(format!("{target}/alef_")).unwrap();
449                                fa.write_all(&alef[..]).unwrap();
450                                let mut fb = File::create(format!("{target}/bet_")).unwrap();
451                                fb.write_all(&bet[..]).unwrap();
452                                let _ = fa;
453                                let _ = fb;
454                                let output = Command::new("patch")
455                                    .arg("-p0")
456                                    .arg(format!("{target}/alef_"))
457                                    .stdin(File::open(format!("{target}/ab_.diff")).unwrap())
458                                    .output()
459                                    .unwrap();
460                                assert!(output.status.success(), "{output:?}");
461                                //println!("{}", String::from_utf8_lossy(&output.stdout));
462                                //println!("{}", String::from_utf8_lossy(&output.stderr));
463                                let alef = fs::read(format!("{target}/alef_")).unwrap();
464                                assert_eq!(alef, bet);
465                            }
466                        }
467                    }
468                }
469            }
470        }
471    }
472
473    #[test]
474    fn test_permutations_reverse() {
475        let target = "target/normal-diff/";
476        // test all possible six-line files.
477        let _ = std::fs::create_dir(target);
478        for &a in &[0, 1, 2] {
479            for &b in &[0, 1, 2] {
480                for &c in &[0, 1, 2] {
481                    for &d in &[0, 1, 2] {
482                        for &e in &[0, 1, 2] {
483                            for &f in &[0, 1, 2] {
484                                use std::fs::{self, File};
485                                use std::io::Write;
486                                use std::process::Command;
487                                let mut alef = Vec::new();
488                                let mut bet = Vec::new();
489                                alef.write_all(if a == 0 { b"a\n" } else { b"f\n" })
490                                    .unwrap();
491                                if a != 2 {
492                                    bet.write_all(b"a\n").unwrap();
493                                }
494                                alef.write_all(if b == 0 { b"b\n" } else { b"e\n" })
495                                    .unwrap();
496                                if b != 2 {
497                                    bet.write_all(b"b\n").unwrap();
498                                }
499                                alef.write_all(if c == 0 { b"c\n" } else { b"d\n" })
500                                    .unwrap();
501                                if c != 2 {
502                                    bet.write_all(b"c\n").unwrap();
503                                }
504                                alef.write_all(if d == 0 { b"d\n" } else { b"c\n" })
505                                    .unwrap();
506                                if d != 2 {
507                                    bet.write_all(b"d\n").unwrap();
508                                }
509                                alef.write_all(if e == 0 { b"e\n" } else { b"b\n" })
510                                    .unwrap();
511                                if e != 2 {
512                                    bet.write_all(b"e\n").unwrap();
513                                }
514                                alef.write_all(if f == 0 { b"f\n" } else { b"a\n" })
515                                    .unwrap();
516                                if f != 2 {
517                                    bet.write_all(b"f\n").unwrap();
518                                }
519                                // This test diff is intentionally reversed.
520                                // We want it to turn the alef into bet.
521                                let diff = diff(&alef, &bet, &Params::default());
522                                File::create(format!("{target}/abr.diff"))
523                                    .unwrap()
524                                    .write_all(&diff)
525                                    .unwrap();
526                                let mut fa = File::create(format!("{target}/alefr")).unwrap();
527                                fa.write_all(&alef[..]).unwrap();
528                                let mut fb = File::create(format!("{target}/betr")).unwrap();
529                                fb.write_all(&bet[..]).unwrap();
530                                let _ = fa;
531                                let _ = fb;
532                                let output = Command::new("patch")
533                                    .arg("-p0")
534                                    .arg(format!("{target}/alefr"))
535                                    .stdin(File::open(format!("{target}/abr.diff")).unwrap())
536                                    .output()
537                                    .unwrap();
538                                assert!(output.status.success(), "{output:?}");
539                                //println!("{}", String::from_utf8_lossy(&output.stdout));
540                                //println!("{}", String::from_utf8_lossy(&output.stderr));
541                                let alef = fs::read(format!("{target}/alefr")).unwrap();
542                                assert_eq!(alef, bet);
543                            }
544                        }
545                    }
546                }
547            }
548        }
549    }
550
551    #[test]
552    fn test_stop_early() {
553        let from = ["a", "b", "c"].join("\n");
554        let to = ["a", "d", "c"].join("\n");
555
556        let diff_full = diff(from.as_bytes(), to.as_bytes(), &Params::default());
557        let expected_full = ["2c2", "< b", "---", "> d", ""].join("\n");
558        assert_eq!(diff_full, expected_full.as_bytes());
559
560        let diff_brief = diff(
561            from.as_bytes(),
562            to.as_bytes(),
563            &Params {
564                brief: true,
565                ..Default::default()
566            },
567        );
568        let expected_brief = "\0".as_bytes();
569        assert_eq!(diff_brief, expected_brief);
570
571        let nodiff_full = diff(from.as_bytes(), from.as_bytes(), &Params::default());
572        assert!(nodiff_full.is_empty());
573
574        let nodiff_brief = diff(
575            from.as_bytes(),
576            from.as_bytes(),
577            &Params {
578                brief: true,
579                ..Default::default()
580            },
581        );
582        assert!(nodiff_brief.is_empty());
583    }
584}