1 /* Analyze file differences for GNU DIFF.
3 Copyright (C) 1988-1989, 1992-1995, 1998, 2001-2002, 2004, 2006-2007,
4 2009-2013 Free Software Foundation, Inc.
6 This file is part of GNU DIFF.
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.
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.
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/>. */
24 #include <file-type.h>
27 /* The core of the Diff algorithm. */
29 #define EQUAL(x,y) ((x) == (y))
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
37 /* Discard lines from one file that have no matches in the other file.
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.
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. */
50 discard_confusing_lines (struct file_data filevec[])
58 /* Allocate our results. */
59 p = xmalloc ((filevec[0].buffered_lines + filevec[1].buffered_lines)
61 for (f = 0; f < 2; f++)
63 filevec[f].undiscarded = p; p += filevec[f].buffered_lines;
64 filevec[f].realindexes = p; p += filevec[f].buffered_lines;
67 /* Set up equiv_count[F][I] as the number of lines in file F
68 that fall in equivalence class I. */
70 p = zalloc (filevec[0].equiv_max * (2 * sizeof *p));
72 equiv_count[1] = p + filevec[0].equiv_max;
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]];
79 /* Set up tables of which lines are going to be discarded. */
81 discarded[0] = zalloc (filevec[0].buffered_lines
82 + filevec[1].buffered_lines);
83 discarded[1] = discarded[0] + filevec[0].buffered_lines;
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. */
88 for (f = 0; f < 2; f++)
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;
95 size_t tem = end / 64;
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)
102 for (i = 0; i < end; i++)
107 nmatch = counts[equivs[i]];
110 else if (nmatch > many)
115 /* Don't really discard the provisional lines except when they occur
116 in a run of discardables, with nonprovisionals at the beginning
119 for (f = 0; f < 2; f++)
121 lin end = filevec[f].buffered_lines;
122 register char *discards = discarded[f];
124 for (i = 0; i < end; i++)
126 /* Cancel provisional discards not in middle of run of discards. */
127 if (discards[i] == 2)
129 else if (discards[i] != 0)
131 /* We have found a nonprovisional discard. */
136 /* Find end of this run of discardable lines.
137 Count how many are provisionally discardable. */
138 for (j = i; j < end; j++)
140 if (discards[j] == 0)
142 if (discards[j] == 2)
146 /* Cancel provisional discards at end, and shrink the run. */
147 while (j > i && discards[j - 1] == 2)
148 discards[--j] = 0, --provisional;
150 /* Now we have the length of a run of discardable lines
151 whose first and last are not provisional. */
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)
159 if (discards[--j] == 2)
166 lin tem = length >> 2;
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))
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)
181 else if (minimum == ++consec)
182 /* Back up to start of subrun, to cancel it all. */
184 else if (minimum < consec)
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++)
193 if (j >= 8 && discards[i + j] == 1)
195 if (discards[i + j] == 2)
196 consec = 0, discards[i + j] = 0;
197 else if (discards[i + j] == 0)
205 /* I advances to the last line of the run. */
208 /* Same thing, from end. */
209 for (j = 0, consec = 0; j < length; j++)
211 if (j >= 8 && discards[i - j] == 1)
213 if (discards[i - j] == 2)
214 consec = 0, discards[i - j] = 0;
215 else if (discards[i - j] == 0)
227 /* Actually discard the lines. */
228 for (f = 0; f < 2; f++)
230 char *discards = discarded[f];
231 lin end = filevec[f].buffered_lines;
233 for (i = 0; i < end; ++i)
234 if (minimal || discards[i] == 0)
236 filevec[f].undiscarded[j] = filevec[f].equivs[i];
237 filevec[f].realindexes[j++] = i;
240 filevec[f].changed[i] = 1;
241 filevec[f].nondiscarded_lines = j;
245 free (equiv_count[0]);
248 /* Adjust inserts/deletes of identical lines to join changes
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". */
259 shift_boundaries (struct file_data filevec[])
263 for (f = 0; f < 2; f++)
265 char *changed = filevec[f].changed;
266 char *other_changed = filevec[1 - f].changed;
267 lin const *equivs = filevec[f].equivs;
270 lin i_end = filevec[f].buffered_lines;
274 lin runlength, start, corresponding;
276 /* Scan forwards to find beginning of another run of changes.
277 Also keep track of the corresponding point in the other file. */
279 while (i < i_end && !changed[i])
281 while (other_changed[j++])
291 /* Find the end of this run of changes. */
295 while (other_changed[j])
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;
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. */
308 while (start && equivs[start - 1] == equivs[i - 1])
310 changed[--start] = 1;
312 while (changed[start - 1])
314 while (other_changed[--j])
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;
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. */
329 while (i != i_end && equivs[start] == equivs[i])
331 changed[start++] = 0;
335 while (other_changed[++j])
339 while (runlength != i - start);
341 /* If possible, move the fully-merged run of changes
342 back to a corresponding run in the other file. */
344 while (corresponding < i)
346 changed[--start] = 1;
348 while (other_changed[--j])
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.
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. */
363 static struct change *
364 add_change (lin line0, lin line1, lin deleted, lin inserted,
367 struct change *new = xmalloc (sizeof *new);
371 new->inserted = inserted;
372 new->deleted = deleted;
377 /* Scan the tables of which lines are inserted and deleted,
378 producing an edit script in reverse order. */
380 static struct change *
381 build_reverse_script (struct file_data const filevec[])
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;
389 /* Note that changedN[lenN] does exist, and is 0. */
393 while (i0 < len0 || i1 < len1)
395 if (changed0[i0] | changed1[i1])
397 lin line0 = i0, line1 = i1;
399 /* Find # lines changed here in each file. */
400 while (changed0[i0]) ++i0;
401 while (changed1[i1]) ++i1;
403 /* Record this change. */
404 script = add_change (line0, line1, i0 - line0, i1 - line1, script);
407 /* We have reached lines in the two files that match each other. */
414 /* Scan the tables of which lines are inserted and deleted,
415 producing an edit script in forward order. */
417 static struct change *
418 build_script (struct file_data const filevec[])
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;
425 /* Note that changedN[-1] does exist, and is 0. */
427 while (i0 >= 0 || i1 >= 0)
429 if (changed0[i0 - 1] | changed1[i1 - 1])
431 lin line0 = i0, line1 = i1;
433 /* Find # lines changed here in each file. */
434 while (changed0[i0 - 1]) --i0;
435 while (changed1[i1 - 1]) --i1;
437 /* Record this change. */
438 script = add_change (i0, i1, line0 - i0, line1 - i1, script);
441 /* We have reached lines in the two files that match each other. */
448 /* If CHANGES, briefly report that two files differed.
449 Return 2 if trouble, CHANGES otherwise. */
451 briefly_report (int changes, struct file_data const filevec[])
455 char const *label0 = file_label[0] ? file_label[0] : filevec[0].name;
456 char const *label1 = file_label[1] ? file_label[1] : filevec[1].name;
459 message ("Files %s and %s differ\n", label0, label1);
462 message ("Binary files %s and %s differ\n", label0, label1);
470 /* Report the differences of two files. */
472 diff_2_files (struct comparison *cmp)
475 struct change *e, *p;
476 struct change *script;
480 /* If we have detected that either file is binary,
481 compare the two files as binary. This can happen
482 only when the first chunk is read.
483 Also, --brief without any --ignore-* options means
484 we can speed things up by treating the files as binary. */
486 if (read_files (cmp->file, files_can_be_treated_as_binary))
488 /* Files with different lengths must be different. */
489 if (cmp->file[0].stat.st_size != cmp->file[1].stat.st_size
490 && (cmp->file[0].desc < 0 || S_ISREG (cmp->file[0].stat.st_mode))
491 && (cmp->file[1].desc < 0 || S_ISREG (cmp->file[1].stat.st_mode)))
494 /* Standard input equals itself. */
495 else if (cmp->file[0].desc == cmp->file[1].desc)
499 /* Scan both files, a buffer at a time, looking for a difference. */
501 /* Allocate same-sized buffers for both files. */
502 size_t lcm_max = PTRDIFF_MAX - 1;
504 buffer_lcm (sizeof (word),
505 buffer_lcm (STAT_BLOCKSIZE (cmp->file[0].stat),
506 STAT_BLOCKSIZE (cmp->file[1].stat),
509 for (f = 0; f < 2; f++)
510 cmp->file[f].buffer = xrealloc (cmp->file[f].buffer, buffer_size);
512 for (;; cmp->file[0].buffered = cmp->file[1].buffered = 0)
514 /* Read a buffer's worth from both files. */
515 for (f = 0; f < 2; f++)
516 if (0 <= cmp->file[f].desc)
517 file_block_read (&cmp->file[f],
518 buffer_size - cmp->file[f].buffered);
520 /* If the buffers differ, the files differ. */
521 if (cmp->file[0].buffered != cmp->file[1].buffered
522 || memcmp (cmp->file[0].buffer,
524 cmp->file[0].buffered))
530 /* If we reach end of file, the files are the same. */
531 if (cmp->file[0].buffered != buffer_size)
539 changes = briefly_report (changes, cmp->file);
547 /* Allocate vectors for the results of comparison:
548 a flag for each line of each file, saying whether that line
549 is an insertion or deletion.
550 Allocate an extra element, always 0, at each end of each vector. */
552 size_t s = cmp->file[0].buffered_lines + cmp->file[1].buffered_lines + 4;
553 char *flag_space = zalloc (s);
554 cmp->file[0].changed = flag_space + 1;
555 cmp->file[1].changed = flag_space + cmp->file[0].buffered_lines + 3;
557 /* Some lines are obviously insertions or deletions
558 because they don't match anything. Detect them now, and
559 avoid even thinking about them in the main comparison algorithm. */
561 discard_confusing_lines (cmp->file);
563 /* Now do the main comparison algorithm, considering just the
564 undiscarded lines. */
566 ctxt.xvec = cmp->file[0].undiscarded;
567 ctxt.yvec = cmp->file[1].undiscarded;
568 diags = (cmp->file[0].nondiscarded_lines
569 + cmp->file[1].nondiscarded_lines + 3);
570 ctxt.fdiag = xmalloc (diags * (2 * sizeof *ctxt.fdiag));
571 ctxt.bdiag = ctxt.fdiag + diags;
572 ctxt.fdiag += cmp->file[1].nondiscarded_lines + 1;
573 ctxt.bdiag += cmp->file[1].nondiscarded_lines + 1;
575 ctxt.heuristic = speed_large_files;
577 /* Set TOO_EXPENSIVE to be approximate square root of input size,
578 bounded below by 256. */
580 for (; diags != 0; diags >>= 2)
582 ctxt.too_expensive = MAX (256, too_expensive);
584 files[0] = cmp->file[0];
585 files[1] = cmp->file[1];
587 compareseq (0, cmp->file[0].nondiscarded_lines,
588 0, cmp->file[1].nondiscarded_lines, minimal, &ctxt);
590 free (ctxt.fdiag - (cmp->file[1].nondiscarded_lines + 1));
592 /* Modify the results slightly to make them prettier
593 in cases where that can validly be done. */
595 shift_boundaries (cmp->file);
597 /* Get the results of comparison in the form of a chain
598 of 'struct change's -- an edit script. */
600 if (output_style == OUTPUT_ED)
601 script = build_reverse_script (cmp->file);
603 script = build_script (cmp->file);
605 /* Set CHANGES if we had any diffs.
606 If some changes are ignored, we must scan the script to decide. */
607 if (ignore_blank_lines || ignore_regexp.fastmap)
609 struct change *next = script;
612 while (next && changes == 0)
614 struct change *this, *end;
615 lin first0, last0, first1, last1;
617 /* Find a set of changes that belong together. */
619 end = find_change (next);
621 /* Disconnect them from the rest of the changes, making them
622 a hunk, and remember the rest for next iteration. */
626 /* Determine whether this hunk is really a difference. */
627 if (analyze_hunk (this, &first0, &last0, &first1, &last1))
630 /* Reconnect the script so it will all be freed properly. */
635 changes = (script != 0);
638 changes = briefly_report (changes, cmp->file);
641 if (changes || !no_diff_means_no_output)
643 /* Record info for starting up output,
644 to be used if and when we have some output to print. */
645 setup_output (file_label[0] ? file_label[0] : cmp->file[0].name,
646 file_label[1] ? file_label[1] : cmp->file[1].name,
649 switch (output_style)
652 print_context_script (script, false);
656 print_context_script (script, true);
660 print_ed_script (script);
663 case OUTPUT_FORWARD_ED:
664 pr_forward_ed_script (script);
668 print_rcs_script (script);
672 print_normal_script (script);
676 print_ifdef_script (script);
680 print_sdiff_script (script);
691 free (cmp->file[0].undiscarded);
695 for (f = 0; f < 2; f++)
697 free (cmp->file[f].equivs);
698 free (cmp->file[f].linbuf + cmp->file[f].linbuf_base);
701 for (e = script; e; e = p)
707 if (! ROBUST_OUTPUT_STYLE (output_style))
708 for (f = 0; f < 2; ++f)
709 if (cmp->file[f].missing_newline)
711 error (0, 0, "%s: %s\n",
712 file_label[f] ? file_label[f] : cmp->file[f].name,
713 _("No newline at end of file"));
718 if (cmp->file[0].buffer != cmp->file[1].buffer)
719 free (cmp->file[0].buffer);
720 free (cmp->file[1].buffer);