1 /* Analyze file differences for GNU DIFF.
2
3 Copyright (C) 1988-1989, 1992-1995, 1998, 2001-2002, 2004, 2006-2007,
4 2009-2013, 2015-2018 Free Software Foundation, Inc.
5
6 This file is part of GNU DIFF.
7
8 This program is free software: you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation, either version 3 of the License, or
11 (at your option) any later version.
12
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with this program. If not, see <http://www.gnu.org/licenses/>. */
20
21 #include "diff.h"
22 #include <cmpbuf.h>
23 #include <error.h>
24 #include <file-type.h>
25 #include <xalloc.h>
26
27 /* The core of the Diff algorithm. */
28 #define ELEMENT lin
29 #define EQUAL(x,y) ((x) == (y))
30 #define OFFSET lin
31 #define EXTRA_CONTEXT_FIELDS /* none */
32 #define NOTE_DELETE(c, xoff) (files[0].changed[files[0].realindexes[xoff]] = 1)
33 #define NOTE_INSERT(c, yoff) (files[1].changed[files[1].realindexes[yoff]] = 1)
34 #define USE_HEURISTIC 1
35 #include <diffseq.h>
36
37 /* Discard lines from one file that have no matches in the other file.
38
39 A line which is discarded will not be considered by the actual
40 comparison algorithm; it will be as if that line were not in the file.
41 The file's 'realindexes' table maps virtual line numbers
42 (which don't count the discarded lines) into real line numbers;
43 this is how the actual comparison algorithm produces results
44 that are comprehensible when the discarded lines are counted.
45
46 When we discard a line, we also mark it as a deletion or insertion
47 so that it will be printed in the output. */
48
49 static void
discard_confusing_lines(struct file_data filevec[])50 discard_confusing_lines (struct file_data filevec[])
51 {
52 int f;
53 lin i;
54 char *discarded[2];
55 lin *equiv_count[2];
56 lin *p;
57
58 /* Allocate our results. */
59 p = xmalloc ((filevec[0].buffered_lines + filevec[1].buffered_lines)
60 * (2 * sizeof *p));
61 for (f = 0; f < 2; f++)
62 {
63 filevec[f].undiscarded = p; p += filevec[f].buffered_lines;
64 filevec[f].realindexes = p; p += filevec[f].buffered_lines;
65 }
66
67 /* Set up equiv_count[F][I] as the number of lines in file F
68 that fall in equivalence class I. */
69
70 p = zalloc (filevec[0].equiv_max * (2 * sizeof *p));
71 equiv_count[0] = p;
72 equiv_count[1] = p + filevec[0].equiv_max;
73
74 for (i = 0; i < filevec[0].buffered_lines; ++i)
75 ++equiv_count[0][filevec[0].equivs[i]];
76 for (i = 0; i < filevec[1].buffered_lines; ++i)
77 ++equiv_count[1][filevec[1].equivs[i]];
78
79 /* Set up tables of which lines are going to be discarded. */
80
81 discarded[0] = zalloc (filevec[0].buffered_lines
82 + filevec[1].buffered_lines);
83 discarded[1] = discarded[0] + filevec[0].buffered_lines;
84
85 /* Mark to be discarded each line that matches no line of the other file.
86 If a line matches many lines, mark it as provisionally discardable. */
87
88 for (f = 0; f < 2; f++)
89 {
90 size_t end = filevec[f].buffered_lines;
91 char *discards = discarded[f];
92 lin *counts = equiv_count[1 - f];
93 lin *equivs = filevec[f].equivs;
94 size_t many = 5;
95 size_t tem = end / 64;
96
97 /* Multiply MANY by approximate square root of number of lines.
98 That is the threshold for provisionally discardable lines. */
99 while ((tem = tem >> 2) > 0)
100 many *= 2;
101
102 for (i = 0; i < end; i++)
103 {
104 lin nmatch;
105 if (equivs[i] == 0)
106 continue;
107 nmatch = counts[equivs[i]];
108 if (nmatch == 0)
109 discards[i] = 1;
110 else if (nmatch > many)
111 discards[i] = 2;
112 }
113 }
114
115 /* Don't really discard the provisional lines except when they occur
116 in a run of discardables, with nonprovisionals at the beginning
117 and end. */
118
119 for (f = 0; f < 2; f++)
120 {
121 lin end = filevec[f].buffered_lines;
122 register char *discards = discarded[f];
123
124 for (i = 0; i < end; i++)
125 {
126 /* Cancel provisional discards not in middle of run of discards. */
127 if (discards[i] == 2)
128 discards[i] = 0;
129 else if (discards[i] != 0)
130 {
131 /* We have found a nonprovisional discard. */
132 register lin j;
133 lin length;
134 lin provisional = 0;
135
136 /* Find end of this run of discardable lines.
137 Count how many are provisionally discardable. */
138 for (j = i; j < end; j++)
139 {
140 if (discards[j] == 0)
141 break;
142 if (discards[j] == 2)
143 ++provisional;
144 }
145
146 /* Cancel provisional discards at end, and shrink the run. */
147 while (j > i && discards[j - 1] == 2)
148 discards[--j] = 0, --provisional;
149
150 /* Now we have the length of a run of discardable lines
151 whose first and last are not provisional. */
152 length = j - i;
153
154 /* If 1/4 of the lines in the run are provisional,
155 cancel discarding of all provisional lines in the run. */
156 if (provisional * 4 > length)
157 {
158 while (j > i)
159 if (discards[--j] == 2)
160 discards[j] = 0;
161 }
162 else
163 {
164 register lin consec;
165 lin minimum = 1;
166 lin tem = length >> 2;
167
168 /* MINIMUM is approximate square root of LENGTH/4.
169 A subrun of two or more provisionals can stand
170 when LENGTH is at least 16.
171 A subrun of 4 or more can stand when LENGTH >= 64. */
172 while (0 < (tem >>= 2))
173 minimum <<= 1;
174 minimum++;
175
176 /* Cancel any subrun of MINIMUM or more provisionals
177 within the larger run. */
178 for (j = 0, consec = 0; j < length; j++)
179 if (discards[i + j] != 2)
180 consec = 0;
181 else if (minimum == ++consec)
182 /* Back up to start of subrun, to cancel it all. */
183 j -= consec;
184 else if (minimum < consec)
185 discards[i + j] = 0;
186
187 /* Scan from beginning of run
188 until we find 3 or more nonprovisionals in a row
189 or until the first nonprovisional at least 8 lines in.
190 Until that point, cancel any provisionals. */
191 for (j = 0, consec = 0; j < length; j++)
192 {
193 if (j >= 8 && discards[i + j] == 1)
194 break;
195 if (discards[i + j] == 2)
196 consec = 0, discards[i + j] = 0;
197 else if (discards[i + j] == 0)
198 consec = 0;
199 else
200 consec++;
201 if (consec == 3)
202 break;
203 }
204
205 /* I advances to the last line of the run. */
206 i += length - 1;
207
208 /* Same thing, from end. */
209 for (j = 0, consec = 0; j < length; j++)
210 {
211 if (j >= 8 && discards[i - j] == 1)
212 break;
213 if (discards[i - j] == 2)
214 consec = 0, discards[i - j] = 0;
215 else if (discards[i - j] == 0)
216 consec = 0;
217 else
218 consec++;
219 if (consec == 3)
220 break;
221 }
222 }
223 }
224 }
225 }
226
227 /* Actually discard the lines. */
228 for (f = 0; f < 2; f++)
229 {
230 char *discards = discarded[f];
231 lin end = filevec[f].buffered_lines;
232 lin j = 0;
233 for (i = 0; i < end; ++i)
234 if (minimal || discards[i] == 0)
235 {
236 filevec[f].undiscarded[j] = filevec[f].equivs[i];
237 filevec[f].realindexes[j++] = i;
238 }
239 else
240 filevec[f].changed[i] = 1;
241 filevec[f].nondiscarded_lines = j;
242 }
243
244 free (discarded[0]);
245 free (equiv_count[0]);
246 }
247
248 /* Adjust inserts/deletes of identical lines to join changes
249 as much as possible.
250
251 We do something when a run of changed lines include a
252 line at one end and have an excluded, identical line at the other.
253 We are free to choose which identical line is included.
254 'compareseq' usually chooses the one at the beginning,
255 but usually it is cleaner to consider the following identical line
256 to be the "change". */
257
258 static void
shift_boundaries(struct file_data filevec[])259 shift_boundaries (struct file_data filevec[])
260 {
261 int f;
262
263 for (f = 0; f < 2; f++)
264 {
265 char *changed = filevec[f].changed;
266 char *other_changed = filevec[1 - f].changed;
267 lin const *equivs = filevec[f].equivs;
268 lin i = 0;
269 lin j = 0;
270 lin i_end = filevec[f].buffered_lines;
271
272 while (1)
273 {
274 lin runlength, start, corresponding;
275
276 /* Scan forwards to find beginning of another run of changes.
277 Also keep track of the corresponding point in the other file. */
278
279 while (i < i_end && !changed[i])
280 {
281 while (other_changed[j++])
282 continue;
283 i++;
284 }
285
286 if (i == i_end)
287 break;
288
289 start = i;
290
291 /* Find the end of this run of changes. */
292
293 while (changed[++i])
294 continue;
295 while (other_changed[j])
296 j++;
297
298 do
299 {
300 /* Record the length of this run of changes, so that
301 we can later determine whether the run has grown. */
302 runlength = i - start;
303
304 /* Move the changed region back, so long as the
305 previous unchanged line matches the last changed one.
306 This merges with previous changed regions. */
307
308 while (start && equivs[start - 1] == equivs[i - 1])
309 {
310 changed[--start] = 1;
311 changed[--i] = 0;
312 while (changed[start - 1])
313 start--;
314 while (other_changed[--j])
315 continue;
316 }
317
318 /* Set CORRESPONDING to the end of the changed run, at the last
319 point where it corresponds to a changed run in the other file.
320 CORRESPONDING == I_END means no such point has been found. */
321 corresponding = other_changed[j - 1] ? i : i_end;
322
323 /* Move the changed region forward, so long as the
324 first changed line matches the following unchanged one.
325 This merges with following changed regions.
326 Do this second, so that if there are no merges,
327 the changed region is moved forward as far as possible. */
328
329 while (i != i_end && equivs[start] == equivs[i])
330 {
331 changed[start++] = 0;
332 changed[i++] = 1;
333 while (changed[i])
334 i++;
335 while (other_changed[++j])
336 corresponding = i;
337 }
338 }
339 while (runlength != i - start);
340
341 /* If possible, move the fully-merged run of changes
342 back to a corresponding run in the other file. */
343
344 while (corresponding < i)
345 {
346 changed[--start] = 1;
347 changed[--i] = 0;
348 while (other_changed[--j])
349 continue;
350 }
351 }
352 }
353 }
354
355 /* Cons an additional entry onto the front of an edit script OLD.
356 LINE0 and LINE1 are the first affected lines in the two files (origin 0).
357 DELETED is the number of lines deleted here from file 0.
358 INSERTED is the number of lines inserted here in file 1.
359
360 If DELETED is 0 then LINE0 is the number of the line before
361 which the insertion was done; vice versa for INSERTED and LINE1. */
362
363 static struct change *
add_change(lin line0,lin line1,lin deleted,lin inserted,struct change * old)364 add_change (lin line0, lin line1, lin deleted, lin inserted,
365 struct change *old)
366 {
367 struct change *new = xmalloc (sizeof *new);
368
369 new->line0 = line0;
370 new->line1 = line1;
371 new->inserted = inserted;
372 new->deleted = deleted;
373 new->link = old;
374 return new;
375 }
376
377 /* Scan the tables of which lines are inserted and deleted,
378 producing an edit script in reverse order. */
379
380 static struct change *
build_reverse_script(struct file_data const filevec[])381 build_reverse_script (struct file_data const filevec[])
382 {
383 struct change *script = 0;
384 char *changed0 = filevec[0].changed;
385 char *changed1 = filevec[1].changed;
386 lin len0 = filevec[0].buffered_lines;
387 lin len1 = filevec[1].buffered_lines;
388
389 /* Note that changedN[lenN] does exist, and is 0. */
390
391 lin i0 = 0, i1 = 0;
392
393 while (i0 < len0 || i1 < len1)
394 {
395 if (changed0[i0] | changed1[i1])
396 {
397 lin line0 = i0, line1 = i1;
398
399 /* Find # lines changed here in each file. */
400 while (changed0[i0]) ++i0;
401 while (changed1[i1]) ++i1;
402
403 /* Record this change. */
404 script = add_change (line0, line1, i0 - line0, i1 - line1, script);
405 }
406
407 /* We have reached lines in the two files that match each other. */
408 i0++, i1++;
409 }
410
411 return script;
412 }
413
414 /* Scan the tables of which lines are inserted and deleted,
415 producing an edit script in forward order. */
416
417 static struct change *
build_script(struct file_data const filevec[])418 build_script (struct file_data const filevec[])
419 {
420 struct change *script = 0;
421 char *changed0 = filevec[0].changed;
422 char *changed1 = filevec[1].changed;
423 lin i0 = filevec[0].buffered_lines, i1 = filevec[1].buffered_lines;
424
425 /* Note that changedN[-1] does exist, and is 0. */
426
427 while (i0 >= 0 || i1 >= 0)
428 {
429 if (changed0[i0 - 1] | changed1[i1 - 1])
430 {
431 lin line0 = i0, line1 = i1;
432
433 /* Find # lines changed here in each file. */
434 while (changed0[i0 - 1]) --i0;
435 while (changed1[i1 - 1]) --i1;
436
437 /* Record this change. */
438 script = add_change (i0, i1, line0 - i0, line1 - i1, script);
439 }
440
441 /* We have reached lines in the two files that match each other. */
442 i0--, i1--;
443 }
444
445 return script;
446 }
447
448 /* If CHANGES, briefly report that two files differed. */
449 static void
briefly_report(int changes,struct file_data const filevec[])450 briefly_report (int changes, struct file_data const filevec[])
451 {
452 if (changes)
453 message ((brief
454 ? _("Files %s and %s differ\n")
455 : _("Binary files %s and %s differ\n")),
456 file_label[0] ? file_label[0] : filevec[0].name,
457 file_label[1] ? file_label[1] : filevec[1].name);
458 }
459
460 /* Report the differences of two files. */
461 int
diff_2_files(struct comparison * cmp)462 diff_2_files (struct comparison *cmp)
463 {
464 int f;
465 struct change *e, *p;
466 struct change *script;
467 int changes;
468
469
470 /* If we have detected that either file is binary,
471 compare the two files as binary. This can happen
472 only when the first chunk is read.
473 Also, --brief without any --ignore-* options means
474 we can speed things up by treating the files as binary. */
475
476 if (read_files (cmp->file, files_can_be_treated_as_binary))
477 {
478 /* Files with different lengths must be different. */
479 if (cmp->file[0].stat.st_size != cmp->file[1].stat.st_size
480 && 0 < cmp->file[0].stat.st_size
481 && 0 < cmp->file[1].stat.st_size
482 && (cmp->file[0].desc < 0 || S_ISREG (cmp->file[0].stat.st_mode))
483 && (cmp->file[1].desc < 0 || S_ISREG (cmp->file[1].stat.st_mode)))
484 changes = 1;
485
486 /* Standard input equals itself. */
487 else if (cmp->file[0].desc == cmp->file[1].desc)
488 changes = 0;
489
490 else
491 /* Scan both files, a buffer at a time, looking for a difference. */
492 {
493 /* Allocate same-sized buffers for both files. */
494 size_t lcm_max = PTRDIFF_MAX - 1;
495 size_t buffer_size =
496 buffer_lcm (sizeof (word),
497 buffer_lcm (STAT_BLOCKSIZE (cmp->file[0].stat),
498 STAT_BLOCKSIZE (cmp->file[1].stat),
499 lcm_max),
500 lcm_max);
501 for (f = 0; f < 2; f++)
502 cmp->file[f].buffer = xrealloc (cmp->file[f].buffer, buffer_size);
503
504 for (;; cmp->file[0].buffered = cmp->file[1].buffered = 0)
505 {
506 /* Read a buffer's worth from both files. */
507 for (f = 0; f < 2; f++)
508 if (0 <= cmp->file[f].desc)
509 file_block_read (&cmp->file[f],
510 buffer_size - cmp->file[f].buffered);
511
512 /* If the buffers differ, the files differ. */
513 if (cmp->file[0].buffered != cmp->file[1].buffered
514 || memcmp (cmp->file[0].buffer,
515 cmp->file[1].buffer,
516 cmp->file[0].buffered))
517 {
518 changes = 1;
519 break;
520 }
521
522 /* If we reach end of file, the files are the same. */
523 if (cmp->file[0].buffered != buffer_size)
524 {
525 changes = 0;
526 break;
527 }
528 }
529 }
530
531 briefly_report (changes, cmp->file);
532 }
533 else
534 {
535 struct context ctxt;
536 lin diags;
537 lin too_expensive;
538
539 /* Allocate vectors for the results of comparison:
540 a flag for each line of each file, saying whether that line
541 is an insertion or deletion.
542 Allocate an extra element, always 0, at each end of each vector. */
543
544 size_t s = cmp->file[0].buffered_lines + cmp->file[1].buffered_lines + 4;
545 char *flag_space = zalloc (s);
546 cmp->file[0].changed = flag_space + 1;
547 cmp->file[1].changed = flag_space + cmp->file[0].buffered_lines + 3;
548
549 /* Some lines are obviously insertions or deletions
550 because they don't match anything. Detect them now, and
551 avoid even thinking about them in the main comparison algorithm. */
552
553 discard_confusing_lines (cmp->file);
554
555 /* Now do the main comparison algorithm, considering just the
556 undiscarded lines. */
557
558 ctxt.xvec = cmp->file[0].undiscarded;
559 ctxt.yvec = cmp->file[1].undiscarded;
560 diags = (cmp->file[0].nondiscarded_lines
561 + cmp->file[1].nondiscarded_lines + 3);
562 ctxt.fdiag = xmalloc (diags * (2 * sizeof *ctxt.fdiag));
563 ctxt.bdiag = ctxt.fdiag + diags;
564 ctxt.fdiag += cmp->file[1].nondiscarded_lines + 1;
565 ctxt.bdiag += cmp->file[1].nondiscarded_lines + 1;
566
567 ctxt.heuristic = speed_large_files;
568
569 /* Set TOO_EXPENSIVE to be the approximate square root of the
570 input size, bounded below by 4096. 4096 seems to be good for
571 circa-2016 CPUs; see Bug#16848 and Bug#24715. */
572 too_expensive = 1;
573 for (; diags != 0; diags >>= 2)
574 too_expensive <<= 1;
575 ctxt.too_expensive = MAX (4096, too_expensive);
576
577 files[0] = cmp->file[0];
578 files[1] = cmp->file[1];
579
580 compareseq (0, cmp->file[0].nondiscarded_lines,
581 0, cmp->file[1].nondiscarded_lines, minimal, &ctxt);
582
583 free (ctxt.fdiag - (cmp->file[1].nondiscarded_lines + 1));
584
585 /* Modify the results slightly to make them prettier
586 in cases where that can validly be done. */
587
588 shift_boundaries (cmp->file);
589
590 /* Get the results of comparison in the form of a chain
591 of 'struct change's -- an edit script. */
592
593 if (output_style == OUTPUT_ED)
594 script = build_reverse_script (cmp->file);
595 else
596 script = build_script (cmp->file);
597
598 /* Set CHANGES if we had any diffs.
599 If some changes are ignored, we must scan the script to decide. */
600 if (ignore_blank_lines || ignore_regexp.fastmap)
601 {
602 struct change *next = script;
603 changes = 0;
604
605 while (next && changes == 0)
606 {
607 struct change *this, *end;
608 lin first0, last0, first1, last1;
609
610 /* Find a set of changes that belong together. */
611 this = next;
612 end = find_change (next);
613
614 /* Disconnect them from the rest of the changes, making them
615 a hunk, and remember the rest for next iteration. */
616 next = end->link;
617 end->link = 0;
618
619 /* Determine whether this hunk is really a difference. */
620 if (analyze_hunk (this, &first0, &last0, &first1, &last1))
621 changes = 1;
622
623 /* Reconnect the script so it will all be freed properly. */
624 end->link = next;
625 }
626 }
627 else
628 changes = (script != 0);
629
630 if (brief)
631 briefly_report (changes, cmp->file);
632 else
633 {
634 if (changes || !no_diff_means_no_output)
635 {
636 /* Record info for starting up output,
637 to be used if and when we have some output to print. */
638 setup_output (file_label[0] ? file_label[0] : cmp->file[0].name,
639 file_label[1] ? file_label[1] : cmp->file[1].name,
640 cmp->parent != 0);
641
642 switch (output_style)
643 {
644 case OUTPUT_CONTEXT:
645 print_context_script (script, false);
646 break;
647
648 case OUTPUT_UNIFIED:
649 print_context_script (script, true);
650 break;
651
652 case OUTPUT_ED:
653 print_ed_script (script);
654 break;
655
656 case OUTPUT_FORWARD_ED:
657 pr_forward_ed_script (script);
658 break;
659
660 case OUTPUT_RCS:
661 print_rcs_script (script);
662 break;
663
664 case OUTPUT_NORMAL:
665 print_normal_script (script);
666 break;
667
668 case OUTPUT_IFDEF:
669 print_ifdef_script (script);
670 break;
671
672 case OUTPUT_SDIFF:
673 print_sdiff_script (script);
674 break;
675
676 default:
677 abort ();
678 }
679
680 finish_output ();
681 }
682 }
683
684 free (cmp->file[0].undiscarded);
685
686 free (flag_space);
687
688 for (f = 0; f < 2; f++)
689 {
690 free (cmp->file[f].equivs);
691 free (cmp->file[f].linbuf + cmp->file[f].linbuf_base);
692 }
693
694 for (e = script; e; e = p)
695 {
696 p = e->link;
697 free (e);
698 }
699
700 if (! ROBUST_OUTPUT_STYLE (output_style))
701 for (f = 0; f < 2; ++f)
702 if (cmp->file[f].missing_newline)
703 {
704 error (0, 0, "%s: %s\n",
705 file_label[f] ? file_label[f] : cmp->file[f].name,
706 _("No newline at end of file"));
707 changes = 2;
708 }
709 }
710
711 if (cmp->file[0].buffer != cmp->file[1].buffer)
712 free (cmp->file[0].buffer);
713 free (cmp->file[1].buffer);
714
715 return changes;
716 }
717