1 /* GNU diff3 - compare three files line by line
3 Copyright (C) 1988-1989, 1992-1996, 1998, 2001-2002, 2004, 2006, 2009-2013,
4 2015-2021 Free Software Foundation, Inc.
6 This program is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>. */
23 #include <unlocked-io.h>
30 #include <file-type.h>
33 #include <system-quote.h>
34 #include <version-etc.h>
39 /* The official name of this program (e.g., no 'g' prefix). */
40 #define PROGRAM_NAME "diff3"
43 proper_name ("Randy Smith")
45 /* Internal data structures and macros for the diff3 program; includes
46 data structures for both diff3 diffs and normal diffs. */
48 /* Different files within a three way diff. */
53 /* A three way diff is built from two two-way diffs; the file which
54 the two two-way diffs share is: */
57 /* Different files within a two way diff.
58 FC is the common file, FO the other file. */
62 /* The ranges are indexed by */
67 ERROR, /* Should not be used */
68 ADD, /* Two way diff add */
69 CHANGE, /* Two way diff change */
70 DELETE, /* Two way diff delete */
71 DIFF_ALL, /* All three are different */
72 DIFF_1ST, /* Only the first is different */
73 DIFF_2ND, /* Only the second */
74 DIFF_3RD /* Only the third */
79 lin ranges[2][2]; /* Ranges are inclusive */
80 char **lines[2]; /* The actual lines (may contain nulls) */
81 size_t *lengths[2]; /* Line lengths (including newlines, if any) */
82 struct diff_block *next;
84 struct diff_block *n2; /* Used only when freeing. */
91 enum diff_type correspond; /* Type of diff */
92 lin ranges[3][2]; /* Ranges are inclusive */
93 char **lines[3]; /* The actual lines (may contain nulls) */
94 size_t *lengths[3]; /* Line lengths (including newlines, if any) */
95 struct diff3_block *next;
98 /* Access the ranges on a diff block. */
99 #define D_LOWLINE(diff, filenum) \
100 ((diff)->ranges[filenum][RANGE_START])
101 #define D_HIGHLINE(diff, filenum) \
102 ((diff)->ranges[filenum][RANGE_END])
103 #define D_NUMLINES(diff, filenum) \
104 (D_HIGHLINE (diff, filenum) - D_LOWLINE (diff, filenum) + 1)
106 /* Access the line numbers in a file in a diff by relative line
107 numbers (i.e. line number within the diff itself). Note that these
108 are lvalues and can be used for assignment. */
109 #define D_RELNUM(diff, filenum, linenum) \
110 ((diff)->lines[filenum][linenum])
111 #define D_RELLEN(diff, filenum, linenum) \
112 ((diff)->lengths[filenum][linenum])
114 /* And get at them directly, when that should be necessary. */
115 #define D_LINEARRAY(diff, filenum) \
116 ((diff)->lines[filenum])
117 #define D_LENARRAY(diff, filenum) \
118 ((diff)->lengths[filenum])
121 #define D_NEXT(diff) ((diff)->next)
123 /* Access the type of a diff3 block. */
124 #define D3_TYPE(diff) ((diff)->correspond)
126 /* Line mappings based on diffs. The first maps off the top of the
127 diff, the second off of the bottom. */
128 #define D_HIGH_MAPLINE(diff, fromfile, tofile, linenum) \
130 - D_HIGHLINE ((diff), (fromfile)) \
131 + D_HIGHLINE ((diff), (tofile)))
133 #define D_LOW_MAPLINE(diff, fromfile, tofile, linenum) \
135 - D_LOWLINE ((diff), (fromfile)) \
136 + D_LOWLINE ((diff), (tofile)))
138 /* Options variables for flags set on command line. */
140 /* If nonzero, treat all files as text files, never as binary. */
143 /* Remove trailing carriage returns from input. */
144 static bool strip_trailing_cr;
146 /* If nonzero, write out an ed script instead of the standard diff3 format. */
147 static bool edscript;
149 /* If nonzero, in the case of overlapping diffs (type DIFF_ALL),
150 preserve the lines which would normally be deleted from
151 file 1 with a special flagging mechanism. */
152 static bool flagging;
154 /* Use a tab to align output lines (-T). */
155 static bool initial_tab;
157 /* If nonzero, do not output information for overlapping diffs. */
158 static bool simple_only;
160 /* If nonzero, do not output information for non-overlapping diffs. */
161 static bool overlap_only;
163 /* If nonzero, show information for DIFF_2ND diffs. */
164 static bool show_2nd;
166 /* If nonzero, include ':wq' at the end of the script
167 to write out the file being edited. */
168 static bool finalwrite;
170 /* If nonzero, output a merged file. */
173 static char *read_diff (char const *, char const *, char **);
174 static char *scan_diff_line (char *, char **, size_t *, char *, char);
175 static enum diff_type process_diff_control (char **, struct diff_block *);
176 static bool compare_line_list (char * const[], size_t const[], char * const[], size_t const[], lin);
177 static bool copy_stringlist (char * const[], size_t const[], char *[], size_t[], lin);
178 static bool output_diff3_edscript (FILE *, struct diff3_block *, int const[3], int const[3], char const *, char const *, char const *);
179 static bool output_diff3_merge (FILE *, FILE *, struct diff3_block *, int const[3], int const[3], char const *, char const *, char const *);
180 static struct diff3_block *create_diff3_block (lin, lin, lin, lin, lin, lin);
181 static struct diff3_block *make_3way_diff (struct diff_block *, struct diff_block *);
182 static struct diff3_block *reverse_diff3_blocklist (struct diff3_block *);
183 static struct diff3_block *using_to_diff3_block (struct diff_block *[2], struct diff_block *[2], int, int, struct diff3_block const *);
184 static struct diff_block *process_diff (char const *, char const *, struct diff_block **, char **);
185 static void check_stdout (void);
186 static void fatal (char const *) __attribute__((noreturn));
187 static void output_diff3 (FILE *, struct diff3_block *, int const[3], int const[3]);
188 static void perror_with_exit (char const *) __attribute__((noreturn));
189 static void try_help (char const *, char const *) __attribute__((noreturn));
190 static void usage (void);
192 static char const *diff_program = DEFAULT_DIFF_PROGRAM;
194 /* Values for long options that do not have single-letter equivalents. */
197 DIFF_PROGRAM_OPTION = CHAR_MAX + 1,
199 STRIP_TRAILING_CR_OPTION
202 static struct option const longopts[] =
204 {"diff-program", 1, 0, DIFF_PROGRAM_OPTION},
205 {"easy-only", 0, 0, '3'},
207 {"help", 0, 0, HELP_OPTION},
208 {"initial-tab", 0, 0, 'T'},
209 {"label", 1, 0, 'L'},
210 {"merge", 0, 0, 'm'},
211 {"overlap-only", 0, 0, 'x'},
212 {"show-all", 0, 0, 'A'},
213 {"show-overlap", 0, 0, 'E'},
214 {"strip-trailing-cr", 0, 0, STRIP_TRAILING_CR_OPTION},
216 {"version", 0, 0, 'v'},
221 free_diff_block (struct diff_block *p)
230 free (p->lengths[0]);
231 free (p->lengths[1]);
232 struct diff_block *next = p->n2;
239 /* Copy each next pointer to n2, since make_3way_diff would clobber the former,
240 yet we will still need something to free these buffers. */
242 next_to_n2 (struct diff_block *p)
253 main (int argc, char **argv)
260 enum { OPTION_3, OPTION_A, OPTION_E, OPTION_X, OPTION_e, OPTION_x };
261 bool conflicts_found;
262 struct diff_block *thread0, *thread1, *last_block;
263 struct diff3_block *diff3;
265 char *tag_strings[3];
270 exit_failure = EXIT_TROUBLE;
271 initialize_main (&argc, &argv);
272 set_program_name (argv[0]);
273 setlocale (LC_ALL, "");
274 bindtextdomain (PACKAGE, LOCALEDIR);
275 textdomain (PACKAGE);
279 while ((c = getopt_long (argc, argv, "aeimvx3AEL:TX", longopts, 0)) != -1)
289 incompat |= 1 << OPTION_A;
293 incompat |= 1 << OPTION_x;
297 incompat |= 1 << OPTION_3;
307 incompat |= 1 << OPTION_X;
311 incompat |= 1 << OPTION_E;
314 incompat |= 1 << OPTION_e;
319 case STRIP_TRAILING_CR_OPTION:
320 strip_trailing_cr = true;
323 version_etc (stdout, PROGRAM_NAME, PACKAGE_NAME, Version,
324 AUTHORS, (char *) NULL);
327 case DIFF_PROGRAM_OPTION:
328 diff_program = optarg;
335 /* Handle up to three -L options. */
338 tag_strings[tag_count++] = optarg;
341 try_help ("too many file label options", 0);
347 /* -AeExX3 without -m implies ed script. */
348 edscript = !!incompat & !merge;
350 show_2nd |= !incompat & merge; /* -m without -AeExX3 implies -A. */
351 flagging |= !incompat & merge;
353 if (incompat & (incompat - 1) /* Ensure at most one of -AeExX3. */
354 || finalwrite & merge /* -i -m would rewrite input file. */
355 || (tag_count && ! flagging)) /* -L requires one of -AEX. */
356 try_help ("incompatible options", 0);
358 if (argc - optind != 3)
360 if (argc - optind < 3)
361 try_help ("missing operand after '%s'", argv[argc - 1]);
363 try_help ("extra operand '%s'", argv[optind + 3]);
366 file = &argv[optind];
368 for (i = tag_count; i < 3; i++)
369 tag_strings[i] = file[i];
371 /* Always compare file1 to file2, even if file2 is "-".
372 This is needed for -mAeExX3. Using the file0 as
373 the common file would produce wrong results, because if the
374 file0-file1 diffs didn't line up with the file0-file2 diffs
375 (which is entirely possible since we don't use diff's -n option),
376 diff3 might report phantom changes from file1 to file2.
378 Also, try to compare file0 to file1, because this is where
379 changes are expected to come from. Diffing between these pairs
380 of files is more likely to avoid phantom changes from file0 to file1.
382 Historically, the default common file was file2, so some older
383 applications (e.g. Emacs ediff) used file2 as the ancestor. So,
384 for compatibility, if this is a 3-way diff (not a merge or
385 edscript), prefer file2 as the common file. */
387 common = 2 - (edscript | merge);
389 if (STREQ (file[common], "-"))
391 /* Sigh. We've got standard input as the common file. We can't
392 call diff twice on stdin. Use the other arg as the common
395 if (STREQ (file[0], "-") || STREQ (file[common], "-"))
396 fatal ("'-' specified for more than one input file");
400 mapping[1] = 3 - common;
403 for (i = 0; i < 3; i++)
404 rev_mapping[mapping[i]] = i;
406 for (i = 0; i < 3; i++)
407 if (! STREQ (file[i], "-"))
409 if (stat (file[i], &statb) < 0)
410 perror_with_exit (file[i]);
411 else if (S_ISDIR (statb.st_mode))
412 die (EXIT_TROUBLE, EISDIR, "%s", file[i]);
416 /* System V fork+wait does not work if SIGCHLD is ignored. */
417 signal (SIGCHLD, SIG_DFL);
420 /* Invoke diff twice on two pairs of input files, combine the two
421 diffs, and output them. */
424 commonname = file[rev_mapping[FILEC]];
425 thread1 = process_diff (file[rev_mapping[FILE1]], commonname, &last_block, &b1);
426 thread0 = process_diff (file[rev_mapping[FILE0]], commonname, &last_block, &b0);
428 next_to_n2 (thread0);
429 next_to_n2 (thread1);
431 diff3 = make_3way_diff (thread0, thread1);
433 free_diff_block (thread0);
434 free_diff_block (thread1);
438 = output_diff3_edscript (stdout, diff3, mapping, rev_mapping,
439 tag_strings[0], tag_strings[1], tag_strings[2]);
442 xfreopen (file[rev_mapping[FILE0]], "r", stdin);
444 = output_diff3_merge (stdin, stdout, diff3, mapping, rev_mapping,
445 tag_strings[0], tag_strings[1], tag_strings[2]);
447 fatal ("read failed");
451 output_diff3 (stdout, diff3, mapping, rev_mapping);
452 conflicts_found = false;
458 exit (conflicts_found);
462 try_help (char const *reason_msgid, char const *operand)
465 error (0, 0, _(reason_msgid), operand);
466 die (EXIT_TROUBLE, 0,
467 _("Try '%s --help' for more information."), program_name);
474 fatal ("write failed");
475 else if (fclose (stdout) != 0)
476 perror_with_exit (_("standard output"));
479 static char const * const option_help_msgid[] = {
480 N_("-A, --show-all output all changes, bracketing conflicts"),
482 N_("-e, --ed output ed script incorporating changes\n"
483 " from OLDFILE to YOURFILE into MYFILE"),
484 N_("-E, --show-overlap like -e, but bracket conflicts"),
485 N_("-3, --easy-only like -e, but incorporate only nonoverlapping changes"),
486 N_("-x, --overlap-only like -e, but incorporate only overlapping changes"),
487 N_("-X like -x, but bracket conflicts"),
488 N_("-i append 'w' and 'q' commands to ed scripts"),
490 N_("-m, --merge output actual merged file, according to\n"
491 " -A if no other options are given"),
493 N_("-a, --text treat all files as text"),
494 N_(" --strip-trailing-cr strip trailing carriage return on input"),
495 N_("-T, --initial-tab make tabs line up by prepending a tab"),
496 N_(" --diff-program=PROGRAM use PROGRAM to compare files"),
497 N_("-L, --label=LABEL use LABEL instead of file name\n"
498 " (can be repeated up to three times)"),
500 N_(" --help display this help and exit"),
501 N_("-v, --version output version information and exit"),
508 char const * const *p;
510 printf (_("Usage: %s [OPTION]... MYFILE OLDFILE YOURFILE\n"),
512 printf ("%s\n\n", _("Compare three files line by line."));
515 Mandatory arguments to long options are mandatory for short options too.\n\
517 for (p = option_help_msgid; *p; p++)
519 printf (" %s\n", _(*p));
523 The default output format is a somewhat human-readable representation of\n\
526 The -e, -E, -x, -X (and corresponding long) options cause an ed script\n\
527 to be output instead of the default.\n\
529 Finally, the -m (--merge) option causes diff3 to do the merge internally\n\
530 and output the actual merged file. For unusual input, this is more\n\
531 robust than using ed.\n"), stdout);
532 printf ("\n%s\n%s\n",
533 _("If a FILE is '-', read standard input."),
534 _("Exit status is 0 if successful, 1 if conflicts, 2 if trouble."));
535 emit_bug_reporting_address ();
538 /* Combine the two diffs together into one.
539 Here is the algorithm:
541 File2 is shared in common between the two diffs.
542 Diff02 is the diff between 0 and 2.
543 Diff12 is the diff between 1 and 2.
545 1) Find the range for the first block in File2.
546 a) Take the lowest of the two ranges (in File2) in the two
547 current blocks (one from each diff) as being the low
548 water mark. Assign the upper end of this block as
549 being the high water mark and move the current block up
550 one. Mark the block just moved over as to be used.
551 b) Check the next block in the diff that the high water
554 *If* the high water mark is above
555 the low end of the range in that block,
557 mark that block as to be used and move the current
558 block up. Set the high water mark to the max of
559 the high end of this block and the current. Repeat b.
561 2) Find the corresponding ranges in File0 (from the blocks
562 in diff02; line per line outside of diffs) and in File1.
563 Create a diff3_block, reserving space as indicated by the ranges.
565 3) Copy all of the pointers for file2 in. At least for now,
566 do memcmp's between corresponding strings in the two diffs.
568 4) Copy all of the pointers for file0 and 1 in. Get what is
569 needed from file2 (when there isn't a diff block, it's
570 identical to file2 within the range between diff blocks).
572 5) If the diff blocks used came from only one of the two
573 strings of diffs, then that file (i.e. the one other than
574 the common file in that diff) is the odd person out. If
575 diff blocks are used from both sets, check to see if files
578 Same number of lines? If so, do a set of memcmp's (if
579 a memcmp matches; copy the pointer over; it'll be easier
580 later during comparisons). If they match, 0 & 1 are the
581 same. If not, all three different.
583 Then do it again, until the blocks are exhausted. */
586 /* Make a three way diff (chain of diff3_block's) from two two way
587 diffs (chains of diff_block's). Assume that each of the two diffs
588 passed are onto the same file (i.e. that each of the diffs were
589 made "to" the same file). Return a three way diff pointer with
590 numbering FILE0 = the other file in diff02, FILE1 = the other file
591 in diff12, and FILEC = the common file. */
593 static struct diff3_block *
594 make_3way_diff (struct diff_block *thread0, struct diff_block *thread1)
596 /* Work on the two diffs passed to it as threads. Thread number 0
597 is diff02, thread number 1 is diff12. USING is the base of the
598 list of blocks to be used to construct each block of the three
599 way diff; if no blocks from a particular thread are to be used,
600 that element of USING is 0. LAST_USING contains the last
601 elements on each of the using lists.
603 HIGH_WATER_MARK is the highest line number in the common file
604 described in any of the diffs in either of the USING lists.
605 HIGH_WATER_THREAD names the thread. Similarly BASE_WATER_MARK
606 and BASE_WATER_THREAD describe the lowest line number in the
607 common file described in any of the diffs in either of the USING
608 lists. HIGH_WATER_DIFF is the diff from which the
609 HIGH_WATER_MARK was taken.
611 HIGH_WATER_DIFF should always be equal to
612 LAST_USING[HIGH_WATER_THREAD]. OTHER_DIFF is the next diff to
613 check for higher water, and should always be equal to
614 CURRENT[HIGH_WATER_THREAD ^ 1]. OTHER_THREAD is the thread in
615 which the OTHER_DIFF is, and hence should always be equal to
616 HIGH_WATER_THREAD ^ 1.
618 LAST_DIFF is the last diff block produced by this routine, for
619 line correspondence purposes between that diff and the one
620 currently being worked on. It is ZERO_DIFF before any blocks
621 have been created. */
623 struct diff_block *using[2];
624 struct diff_block *last_using[2];
625 struct diff_block *current[2];
629 int high_water_thread;
630 int base_water_thread;
633 struct diff_block *high_water_diff;
634 struct diff_block *other_diff;
636 struct diff3_block *result;
637 struct diff3_block *tmpblock;
638 struct diff3_block **result_end;
640 struct diff3_block const *last_diff3;
642 static struct diff3_block const zero_diff3;
646 result_end = &result;
647 current[0] = thread0; current[1] = thread1;
648 last_diff3 = &zero_diff3;
650 /* Sniff up the threads until we reach the end */
652 while (current[0] || current[1])
654 using[0] = using[1] = last_using[0] = last_using[1] = 0;
656 /* Setup low and high water threads, diffs, and marks. */
658 base_water_thread = 1;
659 else if (!current[1])
660 base_water_thread = 0;
663 (D_LOWLINE (current[0], FC) > D_LOWLINE (current[1], FC));
665 high_water_thread = base_water_thread;
667 high_water_diff = current[high_water_thread];
669 high_water_mark = D_HIGHLINE (high_water_diff, FC);
671 /* Make the diff you just got info from into the using class */
672 using[high_water_thread]
673 = last_using[high_water_thread]
675 current[high_water_thread] = high_water_diff->next;
676 last_using[high_water_thread]->next = 0;
678 /* And mark the other diff */
679 other_thread = high_water_thread ^ 0x1;
680 other_diff = current[other_thread];
682 /* Shuffle up the ladder, checking the other diff to see if it
683 needs to be incorporated. */
685 && D_LOWLINE (other_diff, FC) <= high_water_mark + 1)
688 /* Incorporate this diff into the using list. Note that
689 this doesn't take it off the current list */
690 if (using[other_thread])
691 last_using[other_thread]->next = other_diff;
693 using[other_thread] = other_diff;
694 last_using[other_thread] = other_diff;
696 /* Take it off the current list. Note that this following
697 code assumes that other_diff enters it equal to
698 current[high_water_thread ^ 0x1] */
699 current[other_thread] = current[other_thread]->next;
700 other_diff->next = 0;
702 /* Set the high_water stuff
703 If this comparison is equal, then this is the last pass
704 through this loop; since diff blocks within a given
705 thread cannot overlap, the high_water_mark will be
706 *below* the range_start of either of the next diffs. */
708 if (high_water_mark < D_HIGHLINE (other_diff, FC))
710 high_water_thread ^= 1;
711 high_water_mark = D_HIGHLINE (other_diff, FC);
714 /* Set the other diff */
715 other_thread = high_water_thread ^ 0x1;
716 other_diff = current[other_thread];
719 /* The using lists contain a list of all of the blocks to be
720 included in this diff3_block. Create it. */
722 tmpblock = using_to_diff3_block (using, last_using,
723 base_water_thread, high_water_thread,
727 fatal ("internal error: screwup in format of diff blocks");
729 /* Put it on the list. */
730 *result_end = tmpblock;
731 result_end = &tmpblock->next;
733 /* Set up corresponding lines correctly. */
734 last_diff3 = tmpblock;
739 /* Take two lists of blocks (from two separate diff threads) and put
740 them together into one diff3 block. Return a pointer to this diff3
741 block or 0 for failure.
743 All arguments besides using are for the convenience of the routine;
744 they could be derived from the using array. LAST_USING is a pair
745 of pointers to the last blocks in the using structure. LOW_THREAD
746 and HIGH_THREAD tell which threads contain the lowest and highest
747 line numbers for File0. LAST_DIFF3 contains the last diff produced
748 in the calling routine. This is used for lines mappings that
749 would still be identical to the state that diff ended in.
751 A distinction should be made in this routine between the two diffs
752 that are part of a normal two diff block, and the three diffs that
753 are part of a diff3_block. */
755 static struct diff3_block *
756 using_to_diff3_block (struct diff_block *using[2],
757 struct diff_block *last_using[2],
758 int low_thread, int high_thread,
759 struct diff3_block const *last_diff3)
762 struct diff3_block *result;
763 struct diff_block *ptr;
767 /* Find the range in the common file. */
768 lin lowc = D_LOWLINE (using[low_thread], FC);
769 lin highc = D_HIGHLINE (last_using[high_thread], FC);
771 /* Find the ranges in the other files.
772 If using[d] is null, that means that the file to which that diff
773 refers is equivalent to the common file over this range. */
775 for (d = 0; d < 2; d++)
778 low[d] = D_LOW_MAPLINE (using[d], FC, FO, lowc);
779 high[d] = D_HIGH_MAPLINE (last_using[d], FC, FO, highc);
783 low[d] = D_HIGH_MAPLINE (last_diff3, FILEC, FILE0 + d, lowc);
784 high[d] = D_HIGH_MAPLINE (last_diff3, FILEC, FILE0 + d, highc);
787 /* Create a block with the appropriate sizes */
788 result = create_diff3_block (low[0], high[0], low[1], high[1], lowc, highc);
790 /* Copy information for the common file.
791 Return with a zero if any of the compares failed. */
793 for (d = 0; d < 2; d++)
794 for (ptr = using[d]; ptr; ptr = D_NEXT (ptr))
796 lin result_offset = D_LOWLINE (ptr, FC) - lowc;
798 if (!copy_stringlist (D_LINEARRAY (ptr, FC),
799 D_LENARRAY (ptr, FC),
800 D_LINEARRAY (result, FILEC) + result_offset,
801 D_LENARRAY (result, FILEC) + result_offset,
802 D_NUMLINES (ptr, FC)))
806 /* Copy information for file d. First deal with anything that might be
807 before the first diff. */
809 for (d = 0; d < 2; d++)
811 struct diff_block *u = using[d];
812 lin lo = low[d], hi = high[d];
815 i + lo < (u ? D_LOWLINE (u, FO) : hi + 1);
818 D_RELNUM (result, FILE0 + d, i) = D_RELNUM (result, FILEC, i);
819 D_RELLEN (result, FILE0 + d, i) = D_RELLEN (result, FILEC, i);
822 for (ptr = u; ptr; ptr = D_NEXT (ptr))
824 lin result_offset = D_LOWLINE (ptr, FO) - lo;
827 if (!copy_stringlist (D_LINEARRAY (ptr, FO),
828 D_LENARRAY (ptr, FO),
829 D_LINEARRAY (result, FILE0 + d) + result_offset,
830 D_LENARRAY (result, FILE0 + d) + result_offset,
831 D_NUMLINES (ptr, FO)))
834 /* Catch the lines between here and the next diff */
835 linec = D_HIGHLINE (ptr, FC) + 1 - lowc;
836 for (i = D_HIGHLINE (ptr, FO) + 1 - lo;
837 i < (D_NEXT (ptr) ? D_LOWLINE (D_NEXT (ptr), FO) : hi + 1) - lo;
840 D_RELNUM (result, FILE0 + d, i) = D_RELNUM (result, FILEC, linec);
841 D_RELLEN (result, FILE0 + d, i) = D_RELLEN (result, FILEC, linec);
849 D3_TYPE (result) = DIFF_2ND;
851 D3_TYPE (result) = DIFF_1ST;
854 lin nl0 = D_NUMLINES (result, FILE0);
855 lin nl1 = D_NUMLINES (result, FILE1);
858 || !compare_line_list (D_LINEARRAY (result, FILE0),
859 D_LENARRAY (result, FILE0),
860 D_LINEARRAY (result, FILE1),
861 D_LENARRAY (result, FILE1),
863 D3_TYPE (result) = DIFF_ALL;
865 D3_TYPE (result) = DIFF_3RD;
871 /* Copy pointers from a list of strings to a different list of
872 strings. If a spot in the second list is already filled, make sure
873 that it is filled with the same string; if not, return false, the copy
874 incomplete. Upon successful completion of the copy, return true. */
877 copy_stringlist (char * const fromptrs[], size_t const fromlengths[],
878 char *toptrs[], size_t tolengths[],
881 register char * const *f = fromptrs;
882 register char **t = toptrs;
883 register size_t const *fl = fromlengths;
884 register size_t *tl = tolengths;
890 if (*fl != *tl || memcmp (*f, *t, *fl) != 0)
899 t++; f++; tl++; fl++;
905 /* Create a diff3_block, with ranges as specified in the arguments.
906 Allocate the arrays for the various pointers (and zero them) based
907 on the arguments passed. Return the block as a result. */
909 static struct diff3_block *
910 create_diff3_block (lin low0, lin high0,
914 struct diff3_block *result = xmalloc (sizeof *result);
917 D3_TYPE (result) = ERROR;
921 D_LOWLINE (result, FILE0) = low0;
922 D_HIGHLINE (result, FILE0) = high0;
923 D_LOWLINE (result, FILE1) = low1;
924 D_HIGHLINE (result, FILE1) = high1;
925 D_LOWLINE (result, FILE2) = low2;
926 D_HIGHLINE (result, FILE2) = high2;
928 /* Allocate and zero space */
929 numlines = D_NUMLINES (result, FILE0);
932 D_LINEARRAY (result, FILE0) = xcalloc (numlines, sizeof (char *));
933 D_LENARRAY (result, FILE0) = xcalloc (numlines, sizeof (size_t));
937 D_LINEARRAY (result, FILE0) = 0;
938 D_LENARRAY (result, FILE0) = 0;
941 numlines = D_NUMLINES (result, FILE1);
944 D_LINEARRAY (result, FILE1) = xcalloc (numlines, sizeof (char *));
945 D_LENARRAY (result, FILE1) = xcalloc (numlines, sizeof (size_t));
949 D_LINEARRAY (result, FILE1) = 0;
950 D_LENARRAY (result, FILE1) = 0;
953 numlines = D_NUMLINES (result, FILE2);
956 D_LINEARRAY (result, FILE2) = xcalloc (numlines, sizeof (char *));
957 D_LENARRAY (result, FILE2) = xcalloc (numlines, sizeof (size_t));
961 D_LINEARRAY (result, FILE2) = 0;
962 D_LENARRAY (result, FILE2) = 0;
969 /* Compare two lists of lines of text.
970 Return 1 if they are equivalent, 0 if not. */
973 compare_line_list (char * const list1[], size_t const lengths1[],
974 char * const list2[], size_t const lengths2[],
977 char * const *l1 = list1;
978 char * const *l2 = list2;
979 size_t const *lgths1 = lengths1;
980 size_t const *lgths2 = lengths2;
983 if (!*l1 || !*l2 || *lgths1 != *lgths2++
984 || memcmp (*l1++, *l2++, *lgths1++) != 0)
989 /* Input and parse two way diffs. */
991 static struct diff_block *
992 process_diff (char const *filea,
994 struct diff_block **last_block,
1002 struct diff_block *block_list;
1003 struct diff_block **block_list_end = &block_list;
1004 struct diff_block *bptr IF_LINT (= NULL);
1005 size_t too_many_lines = (PTRDIFF_MAX
1006 / MIN (sizeof *bptr->lines[1],
1007 sizeof *bptr->lengths[1]));
1009 diff_limit = read_diff (filea, fileb, &diff_contents);
1010 *buf_to_free = diff_contents;
1011 scan_diff = diff_contents;
1013 while (scan_diff < diff_limit)
1015 bptr = xmalloc (sizeof *bptr);
1016 bptr->lines[0] = bptr->lines[1] = 0;
1017 bptr->lengths[0] = bptr->lengths[1] = 0;
1019 dt = process_diff_control (&scan_diff, bptr);
1020 if (dt == ERROR || *scan_diff != '\n')
1022 fprintf (stderr, _("%s: diff failed: "), program_name);
1025 putc (*scan_diff, stderr);
1027 while (*scan_diff++ != '\n');
1028 exit (EXIT_TROUBLE);
1032 /* Force appropriate ranges to be null, if necessary */
1036 bptr->ranges[0][0]++;
1039 bptr->ranges[1][0]++;
1044 fatal ("internal error: invalid diff type in process_diff");
1048 /* Allocate space for the pointers for the lines from filea, and
1049 parcel them out among these pointers */
1052 lin numlines = D_NUMLINES (bptr, 0);
1053 if (too_many_lines <= numlines)
1055 bptr->lines[0] = xmalloc (numlines * sizeof *bptr->lines[0]);
1056 bptr->lengths[0] = xmalloc (numlines * sizeof *bptr->lengths[0]);
1057 for (i = 0; i < numlines; i++)
1058 scan_diff = scan_diff_line (scan_diff,
1059 &(bptr->lines[0][i]),
1060 &(bptr->lengths[0][i]),
1065 /* Get past the separator for changes */
1068 if (strncmp (scan_diff, "---\n", 4))
1069 fatal ("invalid diff format; invalid change separator");
1073 /* Allocate space for the pointers for the lines from fileb, and
1074 parcel them out among these pointers */
1077 lin numlines = D_NUMLINES (bptr, 1);
1078 if (too_many_lines <= numlines)
1080 bptr->lines[1] = xmalloc (numlines * sizeof *bptr->lines[1]);
1081 bptr->lengths[1] = xmalloc (numlines * sizeof *bptr->lengths[1]);
1082 for (i = 0; i < numlines; i++)
1083 scan_diff = scan_diff_line (scan_diff,
1084 &(bptr->lines[1][i]),
1085 &(bptr->lengths[1][i]),
1090 /* Place this block on the blocklist. */
1091 *block_list_end = bptr;
1092 block_list_end = &bptr->next;
1095 *block_list_end = NULL;
1100 /* Skip tabs and spaces, and return the first character after them. */
1102 static char * _GL_ATTRIBUTE_PURE
1105 while (*s == ' ' || *s == '\t')
1110 /* Read a nonnegative line number from S, returning the address of the
1111 first character after the line number, and storing the number into
1112 *PNUM. Return 0 if S does not point to a valid line number. */
1115 readnum (char *s, lin *pnum)
1117 unsigned char c = *s;
1125 num = c - '0' + num * 10;
1128 while (ISDIGIT (c));
1134 /* Parse a normal format diff control string. Return the type of the
1135 diff (ERROR if the format is bad). All of the other important
1136 information is filled into to the structure pointed to by db, and
1137 the string pointer (whose location is passed to this routine) is
1138 updated to point beyond the end of the string parsed. Note that
1139 only the ranges in the diff_block will be set by this routine.
1141 If some specific pair of numbers has been reduced to a single
1142 number, then both corresponding numbers in the diff block are set
1143 to that number. In general these numbers are interpreted as ranges
1144 inclusive, unless being used by the ADD or DELETE commands. It is
1145 assumed that these will be special cased in a superior routine. */
1147 static enum diff_type
1148 process_diff_control (char **string, struct diff_block *db)
1151 enum diff_type type;
1153 /* Read first set of digits */
1154 s = readnum (skipwhite (s), &db->ranges[0][RANGE_START]);
1158 /* Was that the only digit? */
1162 s = readnum (s + 1, &db->ranges[0][RANGE_END]);
1167 db->ranges[0][RANGE_END] = db->ranges[0][RANGE_START];
1169 /* Get the letter */
1183 return ERROR; /* Bad format */
1185 s++; /* Past letter */
1187 /* Read second set of digits */
1188 s = readnum (skipwhite (s), &db->ranges[1][RANGE_START]);
1192 /* Was that the only digit? */
1196 s = readnum (s + 1, &db->ranges[1][RANGE_END]);
1199 s = skipwhite (s); /* To move to end */
1202 db->ranges[1][RANGE_END] = db->ranges[1][RANGE_START];
1209 read_diff (char const *filea,
1211 char **output_placement)
1214 size_t current_chunk_size, total;
1215 int fd, wstatus, status;
1217 struct stat pipestat;
1218 char const *argv[9];
1220 #if HAVE_WORKING_FORK
1229 *ap++ = diff_program;
1232 if (strip_trailing_cr)
1233 *ap++ = "--strip-trailing-cr";
1234 *ap++ = "--horizon-lines=100";
1240 #if HAVE_WORKING_FORK
1242 if (pipe (fds) != 0)
1243 perror_with_exit ("pipe");
1250 if (fds[1] != STDOUT_FILENO)
1252 dup2 (fds[1], STDOUT_FILENO);
1256 /* The cast to (char **) is needed for portability to older
1257 hosts with a nonstandard prototype for execvp. */
1258 execvp (diff_program, (char **) argv);
1260 _exit (errno == ENOENT ? 127 : 126);
1264 perror_with_exit ("fork");
1266 close (fds[1]); /* Prevent erroneous lack of EOF */
1271 command = system_quote_argv (SCI_SYSTEM, (char **) argv);
1273 fpipe = popen (command, "r");
1275 perror_with_exit (command);
1277 fd = fileno (fpipe);
1281 if (fstat (fd, &pipestat) != 0)
1282 perror_with_exit ("fstat");
1283 current_chunk_size = MAX (1, STAT_BLOCKSIZE (pipestat));
1284 diff_result = xmalloc (current_chunk_size);
1289 size_t bytes_to_read = current_chunk_size - total;
1290 size_t bytes = block_read (fd, diff_result + total, bytes_to_read);
1292 if (bytes != bytes_to_read)
1294 if (bytes == SIZE_MAX)
1295 perror_with_exit (_("read failed"));
1298 if (PTRDIFF_MAX / 2 <= current_chunk_size)
1300 current_chunk_size *= 2;
1301 diff_result = xrealloc (diff_result, current_chunk_size);
1304 if (total != 0 && diff_result[total-1] != '\n')
1305 fatal ("invalid diff format; incomplete last line");
1307 *output_placement = diff_result;
1309 #if ! HAVE_WORKING_FORK
1311 wstatus = pclose (fpipe);
1317 if (close (fd) != 0)
1318 perror_with_exit ("close");
1319 if (waitpid (pid, &wstatus, 0) < 0)
1320 perror_with_exit ("waitpid");
1324 status = ! werrno && WIFEXITED (wstatus) ? WEXITSTATUS (wstatus) : INT_MAX;
1326 if (EXIT_TROUBLE <= status)
1327 die (EXIT_TROUBLE, werrno,
1329 ? "subsidiary program '%s' could not be invoked"
1331 ? "subsidiary program '%s' not found"
1333 ? "subsidiary program '%s' failed"
1334 : "subsidiary program '%s' failed (exit status %d)"),
1335 diff_program, status);
1337 return diff_result + total;
1341 /* Scan a regular diff line (consisting of > or <, followed by a
1342 space, followed by text (including nulls) up to a newline.
1344 This next routine began life as a macro and many parameters in it
1345 are used as call-by-reference values. */
1347 scan_diff_line (char *scan_ptr, char **set_start, size_t *set_length,
1348 char *limit, char leadingchar)
1352 if (!(scan_ptr[0] == leadingchar
1353 && scan_ptr[1] == ' '))
1354 fatal ("invalid diff format; incorrect leading line chars");
1356 *set_start = line_ptr = scan_ptr + 2;
1357 while (*line_ptr++ != '\n')
1360 /* Include newline if the original line ended in a newline,
1361 or if an edit script is being generated.
1362 Copy any missing newline message to stderr if an edit script is being
1363 generated, because edit scripts cannot handle missing newlines.
1364 Return the beginning of the next line. */
1365 *set_length = line_ptr - *set_start;
1366 if (line_ptr < limit && *line_ptr == '\\')
1369 fprintf (stderr, "%s:", program_name);
1376 putc (*line_ptr, stderr);
1378 while (*line_ptr++ != '\n');
1384 /* Output a three way diff passed as a list of diff3_block's. The
1385 argument MAPPING is indexed by external file number (in the
1386 argument list) and contains the internal file number (from the diff
1387 passed). This is important because the user expects outputs in
1388 terms of the argument list number, and the diff passed may have
1389 been done slightly differently (if the last argument was "-", for
1390 example). REV_MAPPING is the inverse of MAPPING. */
1393 output_diff3 (FILE *outputfile, struct diff3_block *diff,
1394 int const mapping[3], int const rev_mapping[3])
1399 struct diff3_block *ptr;
1403 static int skew_increment[3] = { 2, 3, 1 }; /* 0==>2==>1==>3 */
1404 char const *line_prefix = initial_tab ? "\t" : " ";
1406 for (ptr = diff; ptr; ptr = D_NEXT (ptr))
1410 switch (ptr->correspond)
1414 dontprint = 3; /* Print them all */
1415 oddoneout = 3; /* Nobody's odder than anyone else */
1420 oddoneout = rev_mapping[ptr->correspond - DIFF_1ST];
1422 x[0] = oddoneout + '1';
1424 dontprint = oddoneout == 0;
1427 fatal ("internal error: invalid diff type passed to output");
1429 fprintf (outputfile, "====%s\n", x);
1431 /* Go 0, 2, 1 if the first and third outputs are equivalent. */
1433 i = (oddoneout == 1 ? skew_increment[i] : i + 1))
1435 int realfile = mapping[i];
1436 lin lowt = D_LOWLINE (ptr, realfile);
1437 lin hight = D_HIGHLINE (ptr, realfile);
1438 printint llowt = lowt;
1439 printint lhight = hight;
1441 fprintf (outputfile, "%d:", i + 1);
1442 switch (lowt - hight)
1445 fprintf (outputfile, "%"pI"da\n", llowt - 1);
1448 fprintf (outputfile, "%"pI"dc\n", llowt);
1451 fprintf (outputfile, "%"pI"d,%"pI"dc\n", llowt, lhight);
1455 if (i == dontprint) continue;
1462 fputs (line_prefix, outputfile);
1463 cp = D_RELNUM (ptr, realfile, line);
1464 length = D_RELLEN (ptr, realfile, line);
1465 fwrite (cp, sizeof (char), length, outputfile);
1467 while (++line < hight - lowt + 1);
1468 if (cp[length - 1] != '\n')
1469 fprintf (outputfile, "\n\\ %s\n",
1470 _("No newline at end of file"));
1477 /* Output to OUTPUTFILE the lines of B taken from FILENUM. Double any
1478 initial '.'s; yield nonzero if any initial '.'s were doubled. */
1481 dotlines (FILE *outputfile, struct diff3_block *b, int filenum)
1484 bool leading_dot = false;
1487 i < D_NUMLINES (b, filenum);
1490 char *line = D_RELNUM (b, filenum, i);
1494 fputc ('.', outputfile);
1496 fwrite (line, sizeof (char),
1497 D_RELLEN (b, filenum, i), outputfile);
1503 /* Output to OUTPUTFILE a '.' line. If LEADING_DOT is true, also
1504 output a command that removes initial '.'s starting with line START
1505 and continuing for NUM lines. */
1508 undotlines (FILE *outputfile, bool leading_dot, printint start, printint num)
1510 fputs (".\n", outputfile);
1514 fprintf (outputfile, "%"pI"ds/^\\.//\n", start);
1516 fprintf (outputfile, "%"pI"d,%"pI"ds/^\\.//\n", start, start + num - 1);
1520 /* Output a diff3 set of blocks as an ed script. This script applies
1521 the changes between file's 2 & 3 to file 1. Take the precise
1522 format of the ed script to be output from global variables set
1523 during options processing. Reverse the order of
1524 the set of diff3 blocks in DIFF; this gets
1525 around the problems involved with changing line numbers in an ed
1528 As in 'output_diff3', the variable MAPPING maps from file number
1529 according to the argument list to file number according to the diff
1530 passed. All files listed below are in terms of the argument list.
1531 REV_MAPPING is the inverse of MAPPING.
1533 FILE0, FILE1 and FILE2 are the strings to print as the names of the
1534 three files. These may be the actual names, or may be the
1535 arguments specified with -L.
1537 Return 1 if conflicts were found. */
1540 output_diff3_edscript (FILE *outputfile, struct diff3_block *diff,
1541 int const mapping[3], int const rev_mapping[3],
1542 char const *file0, char const *file1, char const *file2)
1545 bool conflicts_found = false;
1547 struct diff3_block *b;
1549 for (b = reverse_diff3_blocklist (diff); b; b = b->next)
1551 /* Must do mapping correctly. */
1553 = (b->correspond == DIFF_ALL
1555 : DIFF_1ST + rev_mapping[b->correspond - DIFF_1ST]);
1557 printint low0, high0;
1559 /* If we aren't supposed to do this output block, skip it. */
1563 case DIFF_2ND: if (!show_2nd) continue; conflict = true; break;
1564 case DIFF_3RD: if (overlap_only) continue; conflict = false; break;
1565 case DIFF_ALL: if (simple_only) continue; conflict = flagging; break;
1568 low0 = D_LOWLINE (b, mapping[FILE0]);
1569 high0 = D_HIGHLINE (b, mapping[FILE0]);
1573 conflicts_found = true;
1576 /* Mark end of conflict. */
1578 fprintf (outputfile, "%"pI"da\n", high0);
1579 leading_dot = false;
1580 if (type == DIFF_ALL)
1584 /* Append lines from FILE1. */
1585 fprintf (outputfile, "||||||| %s\n", file1);
1586 leading_dot = dotlines (outputfile, b, mapping[FILE1]);
1588 /* Append lines from FILE2. */
1589 fputs ("=======\n", outputfile);
1590 leading_dot |= dotlines (outputfile, b, mapping[FILE2]);
1592 fprintf (outputfile, ">>>>>>> %s\n", file2);
1593 undotlines (outputfile, leading_dot, high0 + 2,
1594 (D_NUMLINES (b, mapping[FILE1])
1595 + D_NUMLINES (b, mapping[FILE2]) + 1));
1598 /* Mark start of conflict. */
1600 fprintf (outputfile, "%"pI"da\n<<<<<<< %s\n", low0 - 1,
1601 type == DIFF_ALL ? file0 : file1);
1602 leading_dot = false;
1603 if (type == DIFF_2ND)
1605 /* Prepend lines from FILE1. */
1606 leading_dot = dotlines (outputfile, b, mapping[FILE1]);
1607 fputs ("=======\n", outputfile);
1609 undotlines (outputfile, leading_dot, low0 + 1,
1610 D_NUMLINES (b, mapping[FILE1]));
1612 else if (D_NUMLINES (b, mapping[FILE2]) == 0)
1613 /* Write out a delete */
1616 fprintf (outputfile, "%"pI"dd\n", low0);
1618 fprintf (outputfile, "%"pI"d,%"pI"dd\n", low0, high0);
1621 /* Write out an add or change */
1623 switch (high0 - low0)
1626 fprintf (outputfile, "%"pI"da\n", high0);
1629 fprintf (outputfile, "%"pI"dc\n", high0);
1632 fprintf (outputfile, "%"pI"d,%"pI"dc\n", low0, high0);
1636 undotlines (outputfile, dotlines (outputfile, b, mapping[FILE2]),
1637 low0, D_NUMLINES (b, mapping[FILE2]));
1641 fputs ("w\nq\n", outputfile);
1642 return conflicts_found;
1645 /* Read from INFILE and output to OUTPUTFILE a set of diff3_blocks
1646 DIFF as a merged file. This acts like 'ed file0
1647 <[output_diff3_edscript]', except that it works even for binary
1648 data or incomplete lines.
1650 As before, MAPPING maps from arg list file number to diff file
1651 number, REV_MAPPING is its inverse, and FILE0, FILE1, and FILE2 are
1652 the names of the files.
1654 Return 1 if conflicts were found. */
1657 output_diff3_merge (FILE *infile, FILE *outputfile, struct diff3_block *diff,
1658 int const mapping[3], int const rev_mapping[3],
1659 char const *file0, char const *file1, char const *file2)
1663 bool conflicts_found = false;
1665 struct diff3_block *b;
1668 for (b = diff; b; b = b->next)
1670 /* Must do mapping correctly. */
1672 = ((b->correspond == DIFF_ALL)
1674 : DIFF_1ST + rev_mapping[b->correspond - DIFF_1ST]);
1675 char const *format_2nd = "<<<<<<< %s\n";
1677 /* If we aren't supposed to do this output block, skip it. */
1681 case DIFF_2ND: if (!show_2nd) continue; conflict = true; break;
1682 case DIFF_3RD: if (overlap_only) continue; conflict = false; break;
1683 case DIFF_ALL: if (simple_only) continue; conflict = flagging;
1684 format_2nd = "||||||| %s\n";
1688 /* Copy I lines from file 0. */
1689 i = D_LOWLINE (b, FILE0) - linesread - 1;
1697 if (ferror (infile))
1698 perror_with_exit (_("read failed"));
1699 else if (feof (infile))
1700 fatal ("input file shrank");
1702 putc (c, outputfile);
1708 conflicts_found = true;
1710 if (type == DIFF_ALL)
1712 /* Put in lines from FILE0 with bracket. */
1713 fprintf (outputfile, "<<<<<<< %s\n", file0);
1715 i < D_NUMLINES (b, mapping[FILE0]);
1717 fwrite (D_RELNUM (b, mapping[FILE0], i), sizeof (char),
1718 D_RELLEN (b, mapping[FILE0], i), outputfile);
1723 /* Put in lines from FILE1 with bracket. */
1724 fprintf (outputfile, format_2nd, file1);
1726 i < D_NUMLINES (b, mapping[FILE1]);
1728 fwrite (D_RELNUM (b, mapping[FILE1], i), sizeof (char),
1729 D_RELLEN (b, mapping[FILE1], i), outputfile);
1732 fputs ("=======\n", outputfile);
1735 /* Put in lines from FILE2. */
1737 i < D_NUMLINES (b, mapping[FILE2]);
1739 fwrite (D_RELNUM (b, mapping[FILE2], i), sizeof (char),
1740 D_RELLEN (b, mapping[FILE2], i), outputfile);
1743 fprintf (outputfile, ">>>>>>> %s\n", file2);
1745 /* Skip I lines in file 0. */
1746 i = D_NUMLINES (b, FILE0);
1749 while ((c = getc (infile)) != '\n')
1752 if (ferror (infile))
1753 perror_with_exit (_("read failed"));
1754 else if (feof (infile))
1757 fatal ("input file shrank");
1758 return conflicts_found;
1762 /* Copy rest of common file. */
1763 while ((c = getc (infile)) != EOF || !(ferror (infile) | feof (infile)))
1764 putc (c, outputfile);
1765 return conflicts_found;
1768 /* Reverse the order of the list of diff3 blocks. */
1770 static struct diff3_block *
1771 reverse_diff3_blocklist (struct diff3_block *diff)
1773 register struct diff3_block *tmp, *next, *prev;
1775 for (tmp = diff, prev = 0; tmp; tmp = next)
1786 fatal (char const *msgid)
1788 die (EXIT_TROUBLE, 0, "%s", _(msgid));
1792 perror_with_exit (char const *string)
1794 die (EXIT_TROUBLE, errno, "%s", string);