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-2018 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>
38 /* The official name of this program (e.g., no 'g' prefix). */
39 #define PROGRAM_NAME "diff3"
42 proper_name ("Randy Smith")
44 /* Internal data structures and macros for the diff3 program; includes
45 data structures for both diff3 diffs and normal diffs. */
47 /* Different files within a three way diff. */
52 /* A three way diff is built from two two-way diffs; the file which
53 the two two-way diffs share is: */
56 /* Different files within a two way diff.
57 FC is the common file, FO the other file. */
61 /* The ranges are indexed by */
66 ERROR, /* Should not be used */
67 ADD, /* Two way diff add */
68 CHANGE, /* Two way diff change */
69 DELETE, /* Two way diff delete */
70 DIFF_ALL, /* All three are different */
71 DIFF_1ST, /* Only the first is different */
72 DIFF_2ND, /* Only the second */
73 DIFF_3RD /* Only the third */
78 lin ranges[2][2]; /* Ranges are inclusive */
79 char **lines[2]; /* The actual lines (may contain nulls) */
80 size_t *lengths[2]; /* Line lengths (including newlines, if any) */
81 struct diff_block *next;
83 struct diff_block *n2; /* Used only when freeing. */
90 enum diff_type correspond; /* Type of diff */
91 lin ranges[3][2]; /* Ranges are inclusive */
92 char **lines[3]; /* The actual lines (may contain nulls) */
93 size_t *lengths[3]; /* Line lengths (including newlines, if any) */
94 struct diff3_block *next;
97 /* Access the ranges on a diff block. */
98 #define D_LOWLINE(diff, filenum) \
99 ((diff)->ranges[filenum][RANGE_START])
100 #define D_HIGHLINE(diff, filenum) \
101 ((diff)->ranges[filenum][RANGE_END])
102 #define D_NUMLINES(diff, filenum) \
103 (D_HIGHLINE (diff, filenum) - D_LOWLINE (diff, filenum) + 1)
105 /* Access the line numbers in a file in a diff by relative line
106 numbers (i.e. line number within the diff itself). Note that these
107 are lvalues and can be used for assignment. */
108 #define D_RELNUM(diff, filenum, linenum) \
109 ((diff)->lines[filenum][linenum])
110 #define D_RELLEN(diff, filenum, linenum) \
111 ((diff)->lengths[filenum][linenum])
113 /* And get at them directly, when that should be necessary. */
114 #define D_LINEARRAY(diff, filenum) \
115 ((diff)->lines[filenum])
116 #define D_LENARRAY(diff, filenum) \
117 ((diff)->lengths[filenum])
120 #define D_NEXT(diff) ((diff)->next)
122 /* Access the type of a diff3 block. */
123 #define D3_TYPE(diff) ((diff)->correspond)
125 /* Line mappings based on diffs. The first maps off the top of the
126 diff, the second off of the bottom. */
127 #define D_HIGH_MAPLINE(diff, fromfile, tofile, linenum) \
129 - D_HIGHLINE ((diff), (fromfile)) \
130 + D_HIGHLINE ((diff), (tofile)))
132 #define D_LOW_MAPLINE(diff, fromfile, tofile, linenum) \
134 - D_LOWLINE ((diff), (fromfile)) \
135 + D_LOWLINE ((diff), (tofile)))
137 /* Options variables for flags set on command line. */
139 /* If nonzero, treat all files as text files, never as binary. */
142 /* Remove trailing carriage returns from input. */
143 static bool strip_trailing_cr;
145 /* If nonzero, write out an ed script instead of the standard diff3 format. */
146 static bool edscript;
148 /* If nonzero, in the case of overlapping diffs (type DIFF_ALL),
149 preserve the lines which would normally be deleted from
150 file 1 with a special flagging mechanism. */
151 static bool flagging;
153 /* Use a tab to align output lines (-T). */
154 static bool initial_tab;
156 /* If nonzero, do not output information for overlapping diffs. */
157 static bool simple_only;
159 /* If nonzero, do not output information for non-overlapping diffs. */
160 static bool overlap_only;
162 /* If nonzero, show information for DIFF_2ND diffs. */
163 static bool show_2nd;
165 /* If nonzero, include ':wq' at the end of the script
166 to write out the file being edited. */
167 static bool finalwrite;
169 /* If nonzero, output a merged file. */
172 static char *read_diff (char const *, char const *, char **);
173 static char *scan_diff_line (char *, char **, size_t *, char *, char);
174 static enum diff_type process_diff_control (char **, struct diff_block *);
175 static bool compare_line_list (char * const[], size_t const[], char * const[], size_t const[], lin);
176 static bool copy_stringlist (char * const[], size_t const[], char *[], size_t[], lin);
177 static bool output_diff3_edscript (FILE *, struct diff3_block *, int const[3], int const[3], char const *, char const *, char const *);
178 static bool output_diff3_merge (FILE *, FILE *, struct diff3_block *, int const[3], int const[3], char const *, char const *, char const *);
179 static struct diff3_block *create_diff3_block (lin, lin, lin, lin, lin, lin);
180 static struct diff3_block *make_3way_diff (struct diff_block *, struct diff_block *);
181 static struct diff3_block *reverse_diff3_blocklist (struct diff3_block *);
182 static struct diff3_block *using_to_diff3_block (struct diff_block *[2], struct diff_block *[2], int, int, struct diff3_block const *);
183 static struct diff_block *process_diff (char const *, char const *, struct diff_block **, char **);
184 static void check_stdout (void);
185 static void fatal (char const *) __attribute__((noreturn));
186 static void output_diff3 (FILE *, struct diff3_block *, int const[3], int const[3]);
187 static void perror_with_exit (char const *) __attribute__((noreturn));
188 static void try_help (char const *, char const *) __attribute__((noreturn));
189 static void usage (void);
191 static char const *diff_program = DEFAULT_DIFF_PROGRAM;
193 /* Values for long options that do not have single-letter equivalents. */
196 DIFF_PROGRAM_OPTION = CHAR_MAX + 1,
198 STRIP_TRAILING_CR_OPTION
201 static struct option const longopts[] =
203 {"diff-program", 1, 0, DIFF_PROGRAM_OPTION},
204 {"easy-only", 0, 0, '3'},
206 {"help", 0, 0, HELP_OPTION},
207 {"initial-tab", 0, 0, 'T'},
208 {"label", 1, 0, 'L'},
209 {"merge", 0, 0, 'm'},
210 {"overlap-only", 0, 0, 'x'},
211 {"show-all", 0, 0, 'A'},
212 {"show-overlap", 0, 0, 'E'},
213 {"strip-trailing-cr", 0, 0, STRIP_TRAILING_CR_OPTION},
215 {"version", 0, 0, 'v'},
220 free_diff_block (struct diff_block *p)
229 free (p->lengths[0]);
230 free (p->lengths[1]);
231 struct diff_block *next = p->n2;
238 /* Copy each next pointer to n2, since make_3way_diff would clobber the former,
239 yet we will still need something to free these buffers. */
241 next_to_n2 (struct diff_block *p)
252 main (int argc, char **argv)
259 bool conflicts_found;
260 struct diff_block *thread0, *thread1, *last_block;
261 struct diff3_block *diff3;
263 char *tag_strings[3];
268 exit_failure = EXIT_TROUBLE;
269 initialize_main (&argc, &argv);
270 set_program_name (argv[0]);
271 setlocale (LC_ALL, "");
272 textdomain (PACKAGE);
275 while ((c = getopt_long (argc, argv, "aeimvx3AEL:TX", longopts, 0)) != -1)
313 case STRIP_TRAILING_CR_OPTION:
314 strip_trailing_cr = true;
317 version_etc (stdout, PROGRAM_NAME, PACKAGE_NAME, Version,
318 AUTHORS, (char *) NULL);
321 case DIFF_PROGRAM_OPTION:
322 diff_program = optarg;
329 /* Handle up to three -L options. */
332 tag_strings[tag_count++] = optarg;
335 try_help ("too many file label options", 0);
341 /* -AeExX3 without -m implies ed script. */
342 edscript = incompat & ~(int) merge;
344 show_2nd |= ~incompat & merge; /* -m without -AeExX3 implies -A. */
345 flagging |= ~incompat & merge;
347 if (incompat > 1 /* Ensure at most one of -AeExX3. */
348 || finalwrite & merge /* -i -m would rewrite input file. */
349 || (tag_count && ! flagging)) /* -L requires one of -AEX. */
350 try_help ("incompatible options", 0);
352 if (argc - optind != 3)
354 if (argc - optind < 3)
355 try_help ("missing operand after '%s'", argv[argc - 1]);
357 try_help ("extra operand '%s'", argv[optind + 3]);
360 file = &argv[optind];
362 for (i = tag_count; i < 3; i++)
363 tag_strings[i] = file[i];
365 /* Always compare file1 to file2, even if file2 is "-".
366 This is needed for -mAeExX3. Using the file0 as
367 the common file would produce wrong results, because if the
368 file0-file1 diffs didn't line up with the file0-file2 diffs
369 (which is entirely possible since we don't use diff's -n option),
370 diff3 might report phantom changes from file1 to file2.
372 Also, try to compare file0 to file1, because this is where
373 changes are expected to come from. Diffing between these pairs
374 of files is more likely to avoid phantom changes from file0 to file1.
376 Historically, the default common file was file2, so some older
377 applications (e.g. Emacs ediff) used file2 as the ancestor. So,
378 for compatibility, if this is a 3-way diff (not a merge or
379 edscript), prefer file2 as the common file. */
381 common = 2 - (edscript | merge);
383 if (STREQ (file[common], "-"))
385 /* Sigh. We've got standard input as the common file. We can't
386 call diff twice on stdin. Use the other arg as the common
389 if (STREQ (file[0], "-") || STREQ (file[common], "-"))
390 fatal ("'-' specified for more than one input file");
394 mapping[1] = 3 - common;
397 for (i = 0; i < 3; i++)
398 rev_mapping[mapping[i]] = i;
400 for (i = 0; i < 3; i++)
401 if (! STREQ (file[i], "-"))
403 if (stat (file[i], &statb) < 0)
404 perror_with_exit (file[i]);
405 else if (S_ISDIR (statb.st_mode))
406 die (EXIT_TROUBLE, EISDIR, "%s", file[i]);
410 /* System V fork+wait does not work if SIGCHLD is ignored. */
411 signal (SIGCHLD, SIG_DFL);
414 /* Invoke diff twice on two pairs of input files, combine the two
415 diffs, and output them. */
418 commonname = file[rev_mapping[FILEC]];
419 thread1 = process_diff (file[rev_mapping[FILE1]], commonname, &last_block, &b1);
420 thread0 = process_diff (file[rev_mapping[FILE0]], commonname, &last_block, &b0);
422 next_to_n2 (thread0);
423 next_to_n2 (thread1);
425 diff3 = make_3way_diff (thread0, thread1);
427 free_diff_block (thread0);
428 free_diff_block (thread1);
432 = output_diff3_edscript (stdout, diff3, mapping, rev_mapping,
433 tag_strings[0], tag_strings[1], tag_strings[2]);
436 xfreopen (file[rev_mapping[FILE0]], "r", stdin);
438 = output_diff3_merge (stdin, stdout, diff3, mapping, rev_mapping,
439 tag_strings[0], tag_strings[1], tag_strings[2]);
441 fatal ("read failed");
445 output_diff3 (stdout, diff3, mapping, rev_mapping);
446 conflicts_found = false;
452 exit (conflicts_found);
456 try_help (char const *reason_msgid, char const *operand)
459 error (0, 0, _(reason_msgid), operand);
460 die (EXIT_TROUBLE, 0,
461 _("Try '%s --help' for more information."), program_name);
468 fatal ("write failed");
469 else if (fclose (stdout) != 0)
470 perror_with_exit (_("standard output"));
473 static char const * const option_help_msgid[] = {
474 N_("-A, --show-all output all changes, bracketing conflicts"),
476 N_("-e, --ed output ed script incorporating changes\n"
477 " from OLDFILE to YOURFILE into MYFILE"),
478 N_("-E, --show-overlap like -e, but bracket conflicts"),
479 N_("-3, --easy-only like -e, but incorporate only nonoverlapping changes"),
480 N_("-x, --overlap-only like -e, but incorporate only overlapping changes"),
481 N_("-X like -x, but bracket conflicts"),
482 N_("-i append 'w' and 'q' commands to ed scripts"),
484 N_("-m, --merge output actual merged file, according to\n"
485 " -A if no other options are given"),
487 N_("-a, --text treat all files as text"),
488 N_(" --strip-trailing-cr strip trailing carriage return on input"),
489 N_("-T, --initial-tab make tabs line up by prepending a tab"),
490 N_(" --diff-program=PROGRAM use PROGRAM to compare files"),
491 N_("-L, --label=LABEL use LABEL instead of file name\n"
492 " (can be repeated up to three times)"),
494 N_(" --help display this help and exit"),
495 N_("-v, --version output version information and exit"),
502 char const * const *p;
504 printf (_("Usage: %s [OPTION]... MYFILE OLDFILE YOURFILE\n"),
506 printf ("%s\n\n", _("Compare three files line by line."));
509 Mandatory arguments to long options are mandatory for short options too.\n\
511 for (p = option_help_msgid; *p; p++)
513 printf (" %s\n", _(*p));
517 The default output format is a somewhat human-readable representation of\n\
520 The -e, -E, -x, -X (and corresponding long) options cause an ed script\n\
521 to be output instead of the default.\n\
523 Finally, the -m (--merge) option causes diff3 to do the merge internally\n\
524 and output the actual merged file. For unusual input, this is more\n\
525 robust than using ed.\n"), stdout);
526 printf ("\n%s\n%s\n",
527 _("If a FILE is '-', read standard input."),
528 _("Exit status is 0 if successful, 1 if conflicts, 2 if trouble."));
529 emit_bug_reporting_address ();
532 /* Combine the two diffs together into one.
533 Here is the algorithm:
535 File2 is shared in common between the two diffs.
536 Diff02 is the diff between 0 and 2.
537 Diff12 is the diff between 1 and 2.
539 1) Find the range for the first block in File2.
540 a) Take the lowest of the two ranges (in File2) in the two
541 current blocks (one from each diff) as being the low
542 water mark. Assign the upper end of this block as
543 being the high water mark and move the current block up
544 one. Mark the block just moved over as to be used.
545 b) Check the next block in the diff that the high water
548 *If* the high water mark is above
549 the low end of the range in that block,
551 mark that block as to be used and move the current
552 block up. Set the high water mark to the max of
553 the high end of this block and the current. Repeat b.
555 2) Find the corresponding ranges in File0 (from the blocks
556 in diff02; line per line outside of diffs) and in File1.
557 Create a diff3_block, reserving space as indicated by the ranges.
559 3) Copy all of the pointers for file2 in. At least for now,
560 do memcmp's between corresponding strings in the two diffs.
562 4) Copy all of the pointers for file0 and 1 in. Get what is
563 needed from file2 (when there isn't a diff block, it's
564 identical to file2 within the range between diff blocks).
566 5) If the diff blocks used came from only one of the two
567 strings of diffs, then that file (i.e. the one other than
568 the common file in that diff) is the odd person out. If
569 diff blocks are used from both sets, check to see if files
572 Same number of lines? If so, do a set of memcmp's (if
573 a memcmp matches; copy the pointer over; it'll be easier
574 later during comparisons). If they match, 0 & 1 are the
575 same. If not, all three different.
577 Then do it again, until the blocks are exhausted. */
580 /* Make a three way diff (chain of diff3_block's) from two two way
581 diffs (chains of diff_block's). Assume that each of the two diffs
582 passed are onto the same file (i.e. that each of the diffs were
583 made "to" the same file). Return a three way diff pointer with
584 numbering FILE0 = the other file in diff02, FILE1 = the other file
585 in diff12, and FILEC = the common file. */
587 static struct diff3_block *
588 make_3way_diff (struct diff_block *thread0, struct diff_block *thread1)
590 /* Work on the two diffs passed to it as threads. Thread number 0
591 is diff02, thread number 1 is diff12. USING is the base of the
592 list of blocks to be used to construct each block of the three
593 way diff; if no blocks from a particular thread are to be used,
594 that element of USING is 0. LAST_USING contains the last
595 elements on each of the using lists.
597 HIGH_WATER_MARK is the highest line number in the common file
598 described in any of the diffs in either of the USING lists.
599 HIGH_WATER_THREAD names the thread. Similarly BASE_WATER_MARK
600 and BASE_WATER_THREAD describe the lowest line number in the
601 common file described in any of the diffs in either of the USING
602 lists. HIGH_WATER_DIFF is the diff from which the
603 HIGH_WATER_MARK was taken.
605 HIGH_WATER_DIFF should always be equal to
606 LAST_USING[HIGH_WATER_THREAD]. OTHER_DIFF is the next diff to
607 check for higher water, and should always be equal to
608 CURRENT[HIGH_WATER_THREAD ^ 1]. OTHER_THREAD is the thread in
609 which the OTHER_DIFF is, and hence should always be equal to
610 HIGH_WATER_THREAD ^ 1.
612 LAST_DIFF is the last diff block produced by this routine, for
613 line correspondence purposes between that diff and the one
614 currently being worked on. It is ZERO_DIFF before any blocks
615 have been created. */
617 struct diff_block *using[2];
618 struct diff_block *last_using[2];
619 struct diff_block *current[2];
623 int high_water_thread;
624 int base_water_thread;
627 struct diff_block *high_water_diff;
628 struct diff_block *other_diff;
630 struct diff3_block *result;
631 struct diff3_block *tmpblock;
632 struct diff3_block **result_end;
634 struct diff3_block const *last_diff3;
636 static struct diff3_block const zero_diff3;
640 result_end = &result;
641 current[0] = thread0; current[1] = thread1;
642 last_diff3 = &zero_diff3;
644 /* Sniff up the threads until we reach the end */
646 while (current[0] || current[1])
648 using[0] = using[1] = last_using[0] = last_using[1] = 0;
650 /* Setup low and high water threads, diffs, and marks. */
652 base_water_thread = 1;
653 else if (!current[1])
654 base_water_thread = 0;
657 (D_LOWLINE (current[0], FC) > D_LOWLINE (current[1], FC));
659 high_water_thread = base_water_thread;
661 high_water_diff = current[high_water_thread];
663 high_water_mark = D_HIGHLINE (high_water_diff, FC);
665 /* Make the diff you just got info from into the using class */
666 using[high_water_thread]
667 = last_using[high_water_thread]
669 current[high_water_thread] = high_water_diff->next;
670 last_using[high_water_thread]->next = 0;
672 /* And mark the other diff */
673 other_thread = high_water_thread ^ 0x1;
674 other_diff = current[other_thread];
676 /* Shuffle up the ladder, checking the other diff to see if it
677 needs to be incorporated. */
679 && D_LOWLINE (other_diff, FC) <= high_water_mark + 1)
682 /* Incorporate this diff into the using list. Note that
683 this doesn't take it off the current list */
684 if (using[other_thread])
685 last_using[other_thread]->next = other_diff;
687 using[other_thread] = other_diff;
688 last_using[other_thread] = other_diff;
690 /* Take it off the current list. Note that this following
691 code assumes that other_diff enters it equal to
692 current[high_water_thread ^ 0x1] */
693 current[other_thread] = current[other_thread]->next;
694 other_diff->next = 0;
696 /* Set the high_water stuff
697 If this comparison is equal, then this is the last pass
698 through this loop; since diff blocks within a given
699 thread cannot overlap, the high_water_mark will be
700 *below* the range_start of either of the next diffs. */
702 if (high_water_mark < D_HIGHLINE (other_diff, FC))
704 high_water_thread ^= 1;
705 high_water_mark = D_HIGHLINE (other_diff, FC);
708 /* Set the other diff */
709 other_thread = high_water_thread ^ 0x1;
710 other_diff = current[other_thread];
713 /* The using lists contain a list of all of the blocks to be
714 included in this diff3_block. Create it. */
716 tmpblock = using_to_diff3_block (using, last_using,
717 base_water_thread, high_water_thread,
721 fatal ("internal error: screwup in format of diff blocks");
723 /* Put it on the list. */
724 *result_end = tmpblock;
725 result_end = &tmpblock->next;
727 /* Set up corresponding lines correctly. */
728 last_diff3 = tmpblock;
733 /* Take two lists of blocks (from two separate diff threads) and put
734 them together into one diff3 block. Return a pointer to this diff3
735 block or 0 for failure.
737 All arguments besides using are for the convenience of the routine;
738 they could be derived from the using array. LAST_USING is a pair
739 of pointers to the last blocks in the using structure. LOW_THREAD
740 and HIGH_THREAD tell which threads contain the lowest and highest
741 line numbers for File0. LAST_DIFF3 contains the last diff produced
742 in the calling routine. This is used for lines mappings that
743 would still be identical to the state that diff ended in.
745 A distinction should be made in this routine between the two diffs
746 that are part of a normal two diff block, and the three diffs that
747 are part of a diff3_block. */
749 static struct diff3_block *
750 using_to_diff3_block (struct diff_block *using[2],
751 struct diff_block *last_using[2],
752 int low_thread, int high_thread,
753 struct diff3_block const *last_diff3)
756 struct diff3_block *result;
757 struct diff_block *ptr;
761 /* Find the range in the common file. */
762 lin lowc = D_LOWLINE (using[low_thread], FC);
763 lin highc = D_HIGHLINE (last_using[high_thread], FC);
765 /* Find the ranges in the other files.
766 If using[d] is null, that means that the file to which that diff
767 refers is equivalent to the common file over this range. */
769 for (d = 0; d < 2; d++)
772 low[d] = D_LOW_MAPLINE (using[d], FC, FO, lowc);
773 high[d] = D_HIGH_MAPLINE (last_using[d], FC, FO, highc);
777 low[d] = D_HIGH_MAPLINE (last_diff3, FILEC, FILE0 + d, lowc);
778 high[d] = D_HIGH_MAPLINE (last_diff3, FILEC, FILE0 + d, highc);
781 /* Create a block with the appropriate sizes */
782 result = create_diff3_block (low[0], high[0], low[1], high[1], lowc, highc);
784 /* Copy information for the common file.
785 Return with a zero if any of the compares failed. */
787 for (d = 0; d < 2; d++)
788 for (ptr = using[d]; ptr; ptr = D_NEXT (ptr))
790 lin result_offset = D_LOWLINE (ptr, FC) - lowc;
792 if (!copy_stringlist (D_LINEARRAY (ptr, FC),
793 D_LENARRAY (ptr, FC),
794 D_LINEARRAY (result, FILEC) + result_offset,
795 D_LENARRAY (result, FILEC) + result_offset,
796 D_NUMLINES (ptr, FC)))
800 /* Copy information for file d. First deal with anything that might be
801 before the first diff. */
803 for (d = 0; d < 2; d++)
805 struct diff_block *u = using[d];
806 lin lo = low[d], hi = high[d];
809 i + lo < (u ? D_LOWLINE (u, FO) : hi + 1);
812 D_RELNUM (result, FILE0 + d, i) = D_RELNUM (result, FILEC, i);
813 D_RELLEN (result, FILE0 + d, i) = D_RELLEN (result, FILEC, i);
816 for (ptr = u; ptr; ptr = D_NEXT (ptr))
818 lin result_offset = D_LOWLINE (ptr, FO) - lo;
821 if (!copy_stringlist (D_LINEARRAY (ptr, FO),
822 D_LENARRAY (ptr, FO),
823 D_LINEARRAY (result, FILE0 + d) + result_offset,
824 D_LENARRAY (result, FILE0 + d) + result_offset,
825 D_NUMLINES (ptr, FO)))
828 /* Catch the lines between here and the next diff */
829 linec = D_HIGHLINE (ptr, FC) + 1 - lowc;
830 for (i = D_HIGHLINE (ptr, FO) + 1 - lo;
831 i < (D_NEXT (ptr) ? D_LOWLINE (D_NEXT (ptr), FO) : hi + 1) - lo;
834 D_RELNUM (result, FILE0 + d, i) = D_RELNUM (result, FILEC, linec);
835 D_RELLEN (result, FILE0 + d, i) = D_RELLEN (result, FILEC, linec);
843 D3_TYPE (result) = DIFF_2ND;
845 D3_TYPE (result) = DIFF_1ST;
848 lin nl0 = D_NUMLINES (result, FILE0);
849 lin nl1 = D_NUMLINES (result, FILE1);
852 || !compare_line_list (D_LINEARRAY (result, FILE0),
853 D_LENARRAY (result, FILE0),
854 D_LINEARRAY (result, FILE1),
855 D_LENARRAY (result, FILE1),
857 D3_TYPE (result) = DIFF_ALL;
859 D3_TYPE (result) = DIFF_3RD;
865 /* Copy pointers from a list of strings to a different list of
866 strings. If a spot in the second list is already filled, make sure
867 that it is filled with the same string; if not, return false, the copy
868 incomplete. Upon successful completion of the copy, return true. */
871 copy_stringlist (char * const fromptrs[], size_t const fromlengths[],
872 char *toptrs[], size_t tolengths[],
875 register char * const *f = fromptrs;
876 register char **t = toptrs;
877 register size_t const *fl = fromlengths;
878 register size_t *tl = tolengths;
884 if (*fl != *tl || memcmp (*f, *t, *fl) != 0)
893 t++; f++; tl++; fl++;
899 /* Create a diff3_block, with ranges as specified in the arguments.
900 Allocate the arrays for the various pointers (and zero them) based
901 on the arguments passed. Return the block as a result. */
903 static struct diff3_block *
904 create_diff3_block (lin low0, lin high0,
908 struct diff3_block *result = xmalloc (sizeof *result);
911 D3_TYPE (result) = ERROR;
915 D_LOWLINE (result, FILE0) = low0;
916 D_HIGHLINE (result, FILE0) = high0;
917 D_LOWLINE (result, FILE1) = low1;
918 D_HIGHLINE (result, FILE1) = high1;
919 D_LOWLINE (result, FILE2) = low2;
920 D_HIGHLINE (result, FILE2) = high2;
922 /* Allocate and zero space */
923 numlines = D_NUMLINES (result, FILE0);
926 D_LINEARRAY (result, FILE0) = xcalloc (numlines, sizeof (char *));
927 D_LENARRAY (result, FILE0) = xcalloc (numlines, sizeof (size_t));
931 D_LINEARRAY (result, FILE0) = 0;
932 D_LENARRAY (result, FILE0) = 0;
935 numlines = D_NUMLINES (result, FILE1);
938 D_LINEARRAY (result, FILE1) = xcalloc (numlines, sizeof (char *));
939 D_LENARRAY (result, FILE1) = xcalloc (numlines, sizeof (size_t));
943 D_LINEARRAY (result, FILE1) = 0;
944 D_LENARRAY (result, FILE1) = 0;
947 numlines = D_NUMLINES (result, FILE2);
950 D_LINEARRAY (result, FILE2) = xcalloc (numlines, sizeof (char *));
951 D_LENARRAY (result, FILE2) = xcalloc (numlines, sizeof (size_t));
955 D_LINEARRAY (result, FILE2) = 0;
956 D_LENARRAY (result, FILE2) = 0;
963 /* Compare two lists of lines of text.
964 Return 1 if they are equivalent, 0 if not. */
967 compare_line_list (char * const list1[], size_t const lengths1[],
968 char * const list2[], size_t const lengths2[],
971 char * const *l1 = list1;
972 char * const *l2 = list2;
973 size_t const *lgths1 = lengths1;
974 size_t const *lgths2 = lengths2;
977 if (!*l1 || !*l2 || *lgths1 != *lgths2++
978 || memcmp (*l1++, *l2++, *lgths1++) != 0)
983 /* Input and parse two way diffs. */
985 static struct diff_block *
986 process_diff (char const *filea,
988 struct diff_block **last_block,
996 struct diff_block *block_list;
997 struct diff_block **block_list_end = &block_list;
998 struct diff_block *bptr IF_LINT (= NULL);
999 size_t too_many_lines = (PTRDIFF_MAX
1000 / MIN (sizeof *bptr->lines[1],
1001 sizeof *bptr->lengths[1]));
1003 diff_limit = read_diff (filea, fileb, &diff_contents);
1004 *buf_to_free = diff_contents;
1005 scan_diff = diff_contents;
1007 while (scan_diff < diff_limit)
1009 bptr = xmalloc (sizeof *bptr);
1010 bptr->lines[0] = bptr->lines[1] = 0;
1011 bptr->lengths[0] = bptr->lengths[1] = 0;
1013 dt = process_diff_control (&scan_diff, bptr);
1014 if (dt == ERROR || *scan_diff != '\n')
1016 fprintf (stderr, _("%s: diff failed: "), program_name);
1019 putc (*scan_diff, stderr);
1021 while (*scan_diff++ != '\n');
1022 exit (EXIT_TROUBLE);
1026 /* Force appropriate ranges to be null, if necessary */
1030 bptr->ranges[0][0]++;
1033 bptr->ranges[1][0]++;
1038 fatal ("internal error: invalid diff type in process_diff");
1042 /* Allocate space for the pointers for the lines from filea, and
1043 parcel them out among these pointers */
1046 lin numlines = D_NUMLINES (bptr, 0);
1047 if (too_many_lines <= numlines)
1049 bptr->lines[0] = xmalloc (numlines * sizeof *bptr->lines[0]);
1050 bptr->lengths[0] = xmalloc (numlines * sizeof *bptr->lengths[0]);
1051 for (i = 0; i < numlines; i++)
1052 scan_diff = scan_diff_line (scan_diff,
1053 &(bptr->lines[0][i]),
1054 &(bptr->lengths[0][i]),
1059 /* Get past the separator for changes */
1062 if (strncmp (scan_diff, "---\n", 4))
1063 fatal ("invalid diff format; invalid change separator");
1067 /* Allocate space for the pointers for the lines from fileb, and
1068 parcel them out among these pointers */
1071 lin numlines = D_NUMLINES (bptr, 1);
1072 if (too_many_lines <= numlines)
1074 bptr->lines[1] = xmalloc (numlines * sizeof *bptr->lines[1]);
1075 bptr->lengths[1] = xmalloc (numlines * sizeof *bptr->lengths[1]);
1076 for (i = 0; i < numlines; i++)
1077 scan_diff = scan_diff_line (scan_diff,
1078 &(bptr->lines[1][i]),
1079 &(bptr->lengths[1][i]),
1084 /* Place this block on the blocklist. */
1085 *block_list_end = bptr;
1086 block_list_end = &bptr->next;
1089 *block_list_end = NULL;
1094 /* Skip tabs and spaces, and return the first character after them. */
1096 static char * _GL_ATTRIBUTE_PURE
1099 while (*s == ' ' || *s == '\t')
1104 /* Read a nonnegative line number from S, returning the address of the
1105 first character after the line number, and storing the number into
1106 *PNUM. Return 0 if S does not point to a valid line number. */
1109 readnum (char *s, lin *pnum)
1111 unsigned char c = *s;
1119 num = c - '0' + num * 10;
1122 while (ISDIGIT (c));
1128 /* Parse a normal format diff control string. Return the type of the
1129 diff (ERROR if the format is bad). All of the other important
1130 information is filled into to the structure pointed to by db, and
1131 the string pointer (whose location is passed to this routine) is
1132 updated to point beyond the end of the string parsed. Note that
1133 only the ranges in the diff_block will be set by this routine.
1135 If some specific pair of numbers has been reduced to a single
1136 number, then both corresponding numbers in the diff block are set
1137 to that number. In general these numbers are interpreted as ranges
1138 inclusive, unless being used by the ADD or DELETE commands. It is
1139 assumed that these will be special cased in a superior routine. */
1141 static enum diff_type
1142 process_diff_control (char **string, struct diff_block *db)
1145 enum diff_type type;
1147 /* Read first set of digits */
1148 s = readnum (skipwhite (s), &db->ranges[0][RANGE_START]);
1152 /* Was that the only digit? */
1156 s = readnum (s + 1, &db->ranges[0][RANGE_END]);
1161 db->ranges[0][RANGE_END] = db->ranges[0][RANGE_START];
1163 /* Get the letter */
1177 return ERROR; /* Bad format */
1179 s++; /* Past letter */
1181 /* Read second set of digits */
1182 s = readnum (skipwhite (s), &db->ranges[1][RANGE_START]);
1186 /* Was that the only digit? */
1190 s = readnum (s + 1, &db->ranges[1][RANGE_END]);
1193 s = skipwhite (s); /* To move to end */
1196 db->ranges[1][RANGE_END] = db->ranges[1][RANGE_START];
1203 read_diff (char const *filea,
1205 char **output_placement)
1208 size_t current_chunk_size, total;
1209 int fd, wstatus, status;
1211 struct stat pipestat;
1212 char const *argv[9];
1214 #if HAVE_WORKING_FORK
1223 *ap++ = diff_program;
1226 if (strip_trailing_cr)
1227 *ap++ = "--strip-trailing-cr";
1228 *ap++ = "--horizon-lines=100";
1234 #if HAVE_WORKING_FORK
1236 if (pipe (fds) != 0)
1237 perror_with_exit ("pipe");
1244 if (fds[1] != STDOUT_FILENO)
1246 dup2 (fds[1], STDOUT_FILENO);
1250 /* The cast to (char **) is needed for portability to older
1251 hosts with a nonstandard prototype for execvp. */
1252 execvp (diff_program, (char **) argv);
1254 _exit (errno == ENOENT ? 127 : 126);
1258 perror_with_exit ("fork");
1260 close (fds[1]); /* Prevent erroneous lack of EOF */
1265 command = system_quote_argv (SCI_SYSTEM, (char **) argv);
1267 fpipe = popen (command, "r");
1269 perror_with_exit (command);
1271 fd = fileno (fpipe);
1275 if (fstat (fd, &pipestat) != 0)
1276 perror_with_exit ("fstat");
1277 current_chunk_size = MAX (1, STAT_BLOCKSIZE (pipestat));
1278 diff_result = xmalloc (current_chunk_size);
1283 size_t bytes_to_read = current_chunk_size - total;
1284 size_t bytes = block_read (fd, diff_result + total, bytes_to_read);
1286 if (bytes != bytes_to_read)
1288 if (bytes == SIZE_MAX)
1289 perror_with_exit (_("read failed"));
1292 if (PTRDIFF_MAX / 2 <= current_chunk_size)
1294 current_chunk_size *= 2;
1295 diff_result = xrealloc (diff_result, current_chunk_size);
1298 if (total != 0 && diff_result[total-1] != '\n')
1299 fatal ("invalid diff format; incomplete last line");
1301 *output_placement = diff_result;
1303 #if ! HAVE_WORKING_FORK
1305 wstatus = pclose (fpipe);
1311 if (close (fd) != 0)
1312 perror_with_exit ("close");
1313 if (waitpid (pid, &wstatus, 0) < 0)
1314 perror_with_exit ("waitpid");
1318 status = ! werrno && WIFEXITED (wstatus) ? WEXITSTATUS (wstatus) : INT_MAX;
1320 if (EXIT_TROUBLE <= status)
1321 die (EXIT_TROUBLE, werrno,
1323 ? "subsidiary program '%s' could not be invoked"
1325 ? "subsidiary program '%s' not found"
1327 ? "subsidiary program '%s' failed"
1328 : "subsidiary program '%s' failed (exit status %d)"),
1329 diff_program, status);
1331 return diff_result + total;
1335 /* Scan a regular diff line (consisting of > or <, followed by a
1336 space, followed by text (including nulls) up to a newline.
1338 This next routine began life as a macro and many parameters in it
1339 are used as call-by-reference values. */
1341 scan_diff_line (char *scan_ptr, char **set_start, size_t *set_length,
1342 char *limit, char leadingchar)
1346 if (!(scan_ptr[0] == leadingchar
1347 && scan_ptr[1] == ' '))
1348 fatal ("invalid diff format; incorrect leading line chars");
1350 *set_start = line_ptr = scan_ptr + 2;
1351 while (*line_ptr++ != '\n')
1354 /* Include newline if the original line ended in a newline,
1355 or if an edit script is being generated.
1356 Copy any missing newline message to stderr if an edit script is being
1357 generated, because edit scripts cannot handle missing newlines.
1358 Return the beginning of the next line. */
1359 *set_length = line_ptr - *set_start;
1360 if (line_ptr < limit && *line_ptr == '\\')
1363 fprintf (stderr, "%s:", program_name);
1370 putc (*line_ptr, stderr);
1372 while (*line_ptr++ != '\n');
1378 /* Output a three way diff passed as a list of diff3_block's. The
1379 argument MAPPING is indexed by external file number (in the
1380 argument list) and contains the internal file number (from the diff
1381 passed). This is important because the user expects outputs in
1382 terms of the argument list number, and the diff passed may have
1383 been done slightly differently (if the last argument was "-", for
1384 example). REV_MAPPING is the inverse of MAPPING. */
1387 output_diff3 (FILE *outputfile, struct diff3_block *diff,
1388 int const mapping[3], int const rev_mapping[3])
1393 struct diff3_block *ptr;
1397 static int skew_increment[3] = { 2, 3, 1 }; /* 0==>2==>1==>3 */
1398 char const *line_prefix = initial_tab ? "\t" : " ";
1400 for (ptr = diff; ptr; ptr = D_NEXT (ptr))
1404 switch (ptr->correspond)
1408 dontprint = 3; /* Print them all */
1409 oddoneout = 3; /* Nobody's odder than anyone else */
1414 oddoneout = rev_mapping[ptr->correspond - DIFF_1ST];
1416 x[0] = oddoneout + '1';
1418 dontprint = oddoneout == 0;
1421 fatal ("internal error: invalid diff type passed to output");
1423 fprintf (outputfile, "====%s\n", x);
1425 /* Go 0, 2, 1 if the first and third outputs are equivalent. */
1427 i = (oddoneout == 1 ? skew_increment[i] : i + 1))
1429 int realfile = mapping[i];
1430 lin lowt = D_LOWLINE (ptr, realfile);
1431 lin hight = D_HIGHLINE (ptr, realfile);
1432 printint llowt = lowt;
1433 printint lhight = hight;
1435 fprintf (outputfile, "%d:", i + 1);
1436 switch (lowt - hight)
1439 fprintf (outputfile, "%"pI"da\n", llowt - 1);
1442 fprintf (outputfile, "%"pI"dc\n", llowt);
1445 fprintf (outputfile, "%"pI"d,%"pI"dc\n", llowt, lhight);
1449 if (i == dontprint) continue;
1456 fputs (line_prefix, outputfile);
1457 cp = D_RELNUM (ptr, realfile, line);
1458 length = D_RELLEN (ptr, realfile, line);
1459 fwrite (cp, sizeof (char), length, outputfile);
1461 while (++line < hight - lowt + 1);
1462 if (cp[length - 1] != '\n')
1463 fprintf (outputfile, "\n\\ %s\n",
1464 _("No newline at end of file"));
1471 /* Output to OUTPUTFILE the lines of B taken from FILENUM. Double any
1472 initial '.'s; yield nonzero if any initial '.'s were doubled. */
1475 dotlines (FILE *outputfile, struct diff3_block *b, int filenum)
1478 bool leading_dot = false;
1481 i < D_NUMLINES (b, filenum);
1484 char *line = D_RELNUM (b, filenum, i);
1488 fputc ('.', outputfile);
1490 fwrite (line, sizeof (char),
1491 D_RELLEN (b, filenum, i), outputfile);
1497 /* Output to OUTPUTFILE a '.' line. If LEADING_DOT is true, also
1498 output a command that removes initial '.'s starting with line START
1499 and continuing for NUM lines. */
1502 undotlines (FILE *outputfile, bool leading_dot, printint start, printint num)
1504 fputs (".\n", outputfile);
1508 fprintf (outputfile, "%"pI"ds/^\\.//\n", start);
1510 fprintf (outputfile, "%"pI"d,%"pI"ds/^\\.//\n", start, start + num - 1);
1514 /* Output a diff3 set of blocks as an ed script. This script applies
1515 the changes between file's 2 & 3 to file 1. Take the precise
1516 format of the ed script to be output from global variables set
1517 during options processing. Reverse the order of
1518 the set of diff3 blocks in DIFF; this gets
1519 around the problems involved with changing line numbers in an ed
1522 As in 'output_diff3', the variable MAPPING maps from file number
1523 according to the argument list to file number according to the diff
1524 passed. All files listed below are in terms of the argument list.
1525 REV_MAPPING is the inverse of MAPPING.
1527 FILE0, FILE1 and FILE2 are the strings to print as the names of the
1528 three files. These may be the actual names, or may be the
1529 arguments specified with -L.
1531 Return 1 if conflicts were found. */
1534 output_diff3_edscript (FILE *outputfile, struct diff3_block *diff,
1535 int const mapping[3], int const rev_mapping[3],
1536 char const *file0, char const *file1, char const *file2)
1539 bool conflicts_found = false;
1541 struct diff3_block *b;
1543 for (b = reverse_diff3_blocklist (diff); b; b = b->next)
1545 /* Must do mapping correctly. */
1547 = (b->correspond == DIFF_ALL
1549 : DIFF_1ST + rev_mapping[b->correspond - DIFF_1ST]);
1551 printint low0, high0;
1553 /* If we aren't supposed to do this output block, skip it. */
1557 case DIFF_2ND: if (!show_2nd) continue; conflict = true; break;
1558 case DIFF_3RD: if (overlap_only) continue; conflict = false; break;
1559 case DIFF_ALL: if (simple_only) continue; conflict = flagging; break;
1562 low0 = D_LOWLINE (b, mapping[FILE0]);
1563 high0 = D_HIGHLINE (b, mapping[FILE0]);
1567 conflicts_found = true;
1570 /* Mark end of conflict. */
1572 fprintf (outputfile, "%"pI"da\n", high0);
1573 leading_dot = false;
1574 if (type == DIFF_ALL)
1578 /* Append lines from FILE1. */
1579 fprintf (outputfile, "||||||| %s\n", file1);
1580 leading_dot = dotlines (outputfile, b, mapping[FILE1]);
1582 /* Append lines from FILE2. */
1583 fputs ("=======\n", outputfile);
1584 leading_dot |= dotlines (outputfile, b, mapping[FILE2]);
1586 fprintf (outputfile, ">>>>>>> %s\n", file2);
1587 undotlines (outputfile, leading_dot, high0 + 2,
1588 (D_NUMLINES (b, mapping[FILE1])
1589 + D_NUMLINES (b, mapping[FILE2]) + 1));
1592 /* Mark start of conflict. */
1594 fprintf (outputfile, "%"pI"da\n<<<<<<< %s\n", low0 - 1,
1595 type == DIFF_ALL ? file0 : file1);
1596 leading_dot = false;
1597 if (type == DIFF_2ND)
1599 /* Prepend lines from FILE1. */
1600 leading_dot = dotlines (outputfile, b, mapping[FILE1]);
1601 fputs ("=======\n", outputfile);
1603 undotlines (outputfile, leading_dot, low0 + 1,
1604 D_NUMLINES (b, mapping[FILE1]));
1606 else if (D_NUMLINES (b, mapping[FILE2]) == 0)
1607 /* Write out a delete */
1610 fprintf (outputfile, "%"pI"dd\n", low0);
1612 fprintf (outputfile, "%"pI"d,%"pI"dd\n", low0, high0);
1615 /* Write out an add or change */
1617 switch (high0 - low0)
1620 fprintf (outputfile, "%"pI"da\n", high0);
1623 fprintf (outputfile, "%"pI"dc\n", high0);
1626 fprintf (outputfile, "%"pI"d,%"pI"dc\n", low0, high0);
1630 undotlines (outputfile, dotlines (outputfile, b, mapping[FILE2]),
1631 low0, D_NUMLINES (b, mapping[FILE2]));
1635 fputs ("w\nq\n", outputfile);
1636 return conflicts_found;
1639 /* Read from INFILE and output to OUTPUTFILE a set of diff3_blocks
1640 DIFF as a merged file. This acts like 'ed file0
1641 <[output_diff3_edscript]', except that it works even for binary
1642 data or incomplete lines.
1644 As before, MAPPING maps from arg list file number to diff file
1645 number, REV_MAPPING is its inverse, and FILE0, FILE1, and FILE2 are
1646 the names of the files.
1648 Return 1 if conflicts were found. */
1651 output_diff3_merge (FILE *infile, FILE *outputfile, struct diff3_block *diff,
1652 int const mapping[3], int const rev_mapping[3],
1653 char const *file0, char const *file1, char const *file2)
1657 bool conflicts_found = false;
1659 struct diff3_block *b;
1662 for (b = diff; b; b = b->next)
1664 /* Must do mapping correctly. */
1666 = ((b->correspond == DIFF_ALL)
1668 : DIFF_1ST + rev_mapping[b->correspond - DIFF_1ST]);
1669 char const *format_2nd = "<<<<<<< %s\n";
1671 /* If we aren't supposed to do this output block, skip it. */
1675 case DIFF_2ND: if (!show_2nd) continue; conflict = true; break;
1676 case DIFF_3RD: if (overlap_only) continue; conflict = false; break;
1677 case DIFF_ALL: if (simple_only) continue; conflict = flagging;
1678 format_2nd = "||||||| %s\n";
1682 /* Copy I lines from file 0. */
1683 i = D_LOWLINE (b, FILE0) - linesread - 1;
1691 if (ferror (infile))
1692 perror_with_exit (_("read failed"));
1693 else if (feof (infile))
1694 fatal ("input file shrank");
1696 putc (c, outputfile);
1702 conflicts_found = true;
1704 if (type == DIFF_ALL)
1706 /* Put in lines from FILE0 with bracket. */
1707 fprintf (outputfile, "<<<<<<< %s\n", file0);
1709 i < D_NUMLINES (b, mapping[FILE0]);
1711 fwrite (D_RELNUM (b, mapping[FILE0], i), sizeof (char),
1712 D_RELLEN (b, mapping[FILE0], i), outputfile);
1717 /* Put in lines from FILE1 with bracket. */
1718 fprintf (outputfile, format_2nd, file1);
1720 i < D_NUMLINES (b, mapping[FILE1]);
1722 fwrite (D_RELNUM (b, mapping[FILE1], i), sizeof (char),
1723 D_RELLEN (b, mapping[FILE1], i), outputfile);
1726 fputs ("=======\n", outputfile);
1729 /* Put in lines from FILE2. */
1731 i < D_NUMLINES (b, mapping[FILE2]);
1733 fwrite (D_RELNUM (b, mapping[FILE2], i), sizeof (char),
1734 D_RELLEN (b, mapping[FILE2], i), outputfile);
1737 fprintf (outputfile, ">>>>>>> %s\n", file2);
1739 /* Skip I lines in file 0. */
1740 i = D_NUMLINES (b, FILE0);
1743 while ((c = getc (infile)) != '\n')
1746 if (ferror (infile))
1747 perror_with_exit (_("read failed"));
1748 else if (feof (infile))
1751 fatal ("input file shrank");
1752 return conflicts_found;
1756 /* Copy rest of common file. */
1757 while ((c = getc (infile)) != EOF || !(ferror (infile) | feof (infile)))
1758 putc (c, outputfile);
1759 return conflicts_found;
1762 /* Reverse the order of the list of diff3 blocks. */
1764 static struct diff3_block *
1765 reverse_diff3_blocklist (struct diff3_block *diff)
1767 register struct diff3_block *tmp, *next, *prev;
1769 for (tmp = diff, prev = 0; tmp; tmp = next)
1780 fatal (char const *msgid)
1782 die (EXIT_TROUBLE, 0, "%s", _(msgid));
1786 perror_with_exit (char const *string)
1788 die (EXIT_TROUBLE, errno, "%s", string);