1 /* diff3 - compare three files line by line
3 Copyright (C) 1988-1989, 1992-1996, 1998, 2001-2002, 2004, 2006, 2009-2011
4 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>
29 #include <file-type.h>
33 #include <version-etc.h>
37 /* The official name of this program (e.g., no `g' prefix). */
38 #define PROGRAM_NAME "diff3"
41 proper_name ("Randy Smith")
43 /* Internal data structures and macros for the diff3 program; includes
44 data structures for both diff3 diffs and normal diffs. */
46 /* Different files within a three way diff. */
51 /* A three way diff is built from two two-way diffs; the file which
52 the two two-way diffs share is: */
55 /* Different files within a two way diff.
56 FC is the common file, FO the other file. */
60 /* The ranges are indexed by */
65 ERROR, /* Should not be used */
66 ADD, /* Two way diff add */
67 CHANGE, /* Two way diff change */
68 DELETE, /* Two way diff delete */
69 DIFF_ALL, /* All three are different */
70 DIFF_1ST, /* Only the first is different */
71 DIFF_2ND, /* Only the second */
72 DIFF_3RD /* Only the third */
77 lin ranges[2][2]; /* Ranges are inclusive */
78 char **lines[2]; /* The actual lines (may contain nulls) */
79 size_t *lengths[2]; /* Line lengths (including newlines, if any) */
80 struct diff_block *next;
86 enum diff_type correspond; /* Type of diff */
87 lin ranges[3][2]; /* Ranges are inclusive */
88 char **lines[3]; /* The actual lines (may contain nulls) */
89 size_t *lengths[3]; /* Line lengths (including newlines, if any) */
90 struct diff3_block *next;
93 /* Access the ranges on a diff block. */
94 #define D_LOWLINE(diff, filenum) \
95 ((diff)->ranges[filenum][RANGE_START])
96 #define D_HIGHLINE(diff, filenum) \
97 ((diff)->ranges[filenum][RANGE_END])
98 #define D_NUMLINES(diff, filenum) \
99 (D_HIGHLINE (diff, filenum) - D_LOWLINE (diff, filenum) + 1)
101 /* Access the line numbers in a file in a diff by relative line
102 numbers (i.e. line number within the diff itself). Note that these
103 are lvalues and can be used for assignment. */
104 #define D_RELNUM(diff, filenum, linenum) \
105 ((diff)->lines[filenum][linenum])
106 #define D_RELLEN(diff, filenum, linenum) \
107 ((diff)->lengths[filenum][linenum])
109 /* And get at them directly, when that should be necessary. */
110 #define D_LINEARRAY(diff, filenum) \
111 ((diff)->lines[filenum])
112 #define D_LENARRAY(diff, filenum) \
113 ((diff)->lengths[filenum])
116 #define D_NEXT(diff) ((diff)->next)
118 /* Access the type of a diff3 block. */
119 #define D3_TYPE(diff) ((diff)->correspond)
121 /* Line mappings based on diffs. The first maps off the top of the
122 diff, the second off of the bottom. */
123 #define D_HIGH_MAPLINE(diff, fromfile, tofile, linenum) \
125 - D_HIGHLINE ((diff), (fromfile)) \
126 + D_HIGHLINE ((diff), (tofile)))
128 #define D_LOW_MAPLINE(diff, fromfile, tofile, linenum) \
130 - D_LOWLINE ((diff), (fromfile)) \
131 + D_LOWLINE ((diff), (tofile)))
133 /* Options variables for flags set on command line. */
135 /* If nonzero, treat all files as text files, never as binary. */
138 /* Remove trailing carriage returns from input. */
139 static bool strip_trailing_cr;
141 /* If nonzero, write out an ed script instead of the standard diff3 format. */
142 static bool edscript;
144 /* If nonzero, in the case of overlapping diffs (type DIFF_ALL),
145 preserve the lines which would normally be deleted from
146 file 1 with a special flagging mechanism. */
147 static bool flagging;
149 /* Use a tab to align output lines (-T). */
150 static bool initial_tab;
152 /* If nonzero, do not output information for overlapping diffs. */
153 static bool simple_only;
155 /* If nonzero, do not output information for non-overlapping diffs. */
156 static bool overlap_only;
158 /* If nonzero, show information for DIFF_2ND diffs. */
159 static bool show_2nd;
161 /* If nonzero, include `:wq' at the end of the script
162 to write out the file being edited. */
163 static bool finalwrite;
165 /* If nonzero, output a merged file. */
168 static char *read_diff (char const *, char const *, char **);
169 static char *scan_diff_line (char *, char **, size_t *, char *, char);
170 static enum diff_type process_diff_control (char **, struct diff_block *);
171 static bool compare_line_list (char * const[], size_t const[], char * const[], size_t const[], lin);
172 static bool copy_stringlist (char * const[], size_t const[], char *[], size_t[], lin);
173 static bool output_diff3_edscript (FILE *, struct diff3_block *, int const[3], int const[3], char const *, char const *, char const *);
174 static bool output_diff3_merge (FILE *, FILE *, struct diff3_block *, int const[3], int const[3], char const *, char const *, char const *);
175 static struct diff3_block *create_diff3_block (lin, lin, lin, lin, lin, lin);
176 static struct diff3_block *make_3way_diff (struct diff_block *, struct diff_block *);
177 static struct diff3_block *reverse_diff3_blocklist (struct diff3_block *);
178 static struct diff3_block *using_to_diff3_block (struct diff_block *[2], struct diff_block *[2], int, int, struct diff3_block const *);
179 static struct diff_block *process_diff (char const *, char const *, struct diff_block **);
180 static void check_stdout (void);
181 static void fatal (char const *) __attribute__((noreturn));
182 static void output_diff3 (FILE *, struct diff3_block *, int const[3], int const[3]);
183 static void perror_with_exit (char const *) __attribute__((noreturn));
184 static void try_help (char const *, char const *) __attribute__((noreturn));
185 static void usage (void);
187 static char const *diff_program = DEFAULT_DIFF_PROGRAM;
189 /* Values for long options that do not have single-letter equivalents. */
192 DIFF_PROGRAM_OPTION = CHAR_MAX + 1,
194 STRIP_TRAILING_CR_OPTION
197 static struct option const longopts[] =
199 {"diff-program", 1, 0, DIFF_PROGRAM_OPTION},
200 {"easy-only", 0, 0, '3'},
202 {"help", 0, 0, HELP_OPTION},
203 {"initial-tab", 0, 0, 'T'},
204 {"label", 1, 0, 'L'},
205 {"merge", 0, 0, 'm'},
206 {"overlap-only", 0, 0, 'x'},
207 {"show-all", 0, 0, 'A'},
208 {"show-overlap", 0, 0, 'E'},
209 {"strip-trailing-cr", 0, 0, STRIP_TRAILING_CR_OPTION},
211 {"version", 0, 0, 'v'},
216 main (int argc, char **argv)
223 bool conflicts_found;
224 struct diff_block *thread0, *thread1, *last_block;
225 struct diff3_block *diff3;
227 char *tag_strings[3];
232 exit_failure = EXIT_TROUBLE;
233 initialize_main (&argc, &argv);
234 set_program_name (argv[0]);
235 setlocale (LC_ALL, "");
236 textdomain (PACKAGE);
239 while ((c = getopt_long (argc, argv, "aeimvx3AEL:TX", longopts, 0)) != -1)
277 case STRIP_TRAILING_CR_OPTION:
278 strip_trailing_cr = true;
281 version_etc (stdout, PROGRAM_NAME, PACKAGE_NAME, Version,
282 AUTHORS, (char *) NULL);
285 case DIFF_PROGRAM_OPTION:
286 diff_program = optarg;
293 /* Handle up to three -L options. */
296 tag_strings[tag_count++] = optarg;
299 try_help ("too many file label options", 0);
305 edscript = incompat & ~merge; /* -AeExX3 without -m implies ed script. */
306 show_2nd |= ~incompat & merge; /* -m without -AeExX3 implies -A. */
307 flagging |= ~incompat & merge;
309 if (incompat > 1 /* Ensure at most one of -AeExX3. */
310 || finalwrite & merge /* -i -m would rewrite input file. */
311 || (tag_count && ! flagging)) /* -L requires one of -AEX. */
312 try_help ("incompatible options", 0);
314 if (argc - optind != 3)
316 if (argc - optind < 3)
317 try_help ("missing operand after `%s'", argv[argc - 1]);
319 try_help ("extra operand `%s'", argv[optind + 3]);
322 file = &argv[optind];
324 for (i = tag_count; i < 3; i++)
325 tag_strings[i] = file[i];
327 /* Always compare file1 to file2, even if file2 is "-".
328 This is needed for -mAeExX3. Using the file0 as
329 the common file would produce wrong results, because if the
330 file0-file1 diffs didn't line up with the file0-file2 diffs
331 (which is entirely possible since we don't use diff's -n option),
332 diff3 might report phantom changes from file1 to file2.
334 Also, try to compare file0 to file1, because this is where
335 changes are expected to come from. Diffing between these pairs
336 of files is more likely to avoid phantom changes from file0 to file1.
338 Historically, the default common file was file2, so some older
339 applications (e.g. Emacs ediff) used file2 as the ancestor. So,
340 for compatibility, if this is a 3-way diff (not a merge or
341 edscript), prefer file2 as the common file. */
343 common = 2 - (edscript | merge);
345 if (STREQ (file[common], "-"))
347 /* Sigh. We've got standard input as the common file. We can't
348 call diff twice on stdin. Use the other arg as the common
351 if (STREQ (file[0], "-") || STREQ (file[common], "-"))
352 fatal ("`-' specified for more than one input file");
356 mapping[1] = 3 - common;
359 for (i = 0; i < 3; i++)
360 rev_mapping[mapping[i]] = i;
362 for (i = 0; i < 3; i++)
363 if (! STREQ (file[i], "-"))
365 if (stat (file[i], &statb) < 0)
366 perror_with_exit (file[i]);
367 else if (S_ISDIR (statb.st_mode))
368 error (EXIT_TROUBLE, EISDIR, "%s", file[i]);
372 /* System V fork+wait does not work if SIGCHLD is ignored. */
373 signal (SIGCHLD, SIG_DFL);
376 /* Invoke diff twice on two pairs of input files, combine the two
377 diffs, and output them. */
379 commonname = file[rev_mapping[FILEC]];
380 thread1 = process_diff (file[rev_mapping[FILE1]], commonname, &last_block);
381 thread0 = process_diff (file[rev_mapping[FILE0]], commonname, &last_block);
382 diff3 = make_3way_diff (thread0, thread1);
385 = output_diff3_edscript (stdout, diff3, mapping, rev_mapping,
386 tag_strings[0], tag_strings[1], tag_strings[2]);
389 xfreopen (file[rev_mapping[FILE0]], "r", stdin);
391 = output_diff3_merge (stdin, stdout, diff3, mapping, rev_mapping,
392 tag_strings[0], tag_strings[1], tag_strings[2]);
394 fatal ("read failed");
398 output_diff3 (stdout, diff3, mapping, rev_mapping);
399 conflicts_found = false;
403 exit (conflicts_found);
404 return conflicts_found;
408 try_help (char const *reason_msgid, char const *operand)
411 error (0, 0, _(reason_msgid), operand);
412 error (EXIT_TROUBLE, 0,
413 _("Try `%s --help' for more information."), program_name);
421 fatal ("write failed");
422 else if (fclose (stdout) != 0)
423 perror_with_exit (_("standard output"));
426 static char const * const option_help_msgid[] = {
427 N_("-A, --show-all output all changes, bracketing conflicts"),
429 N_("-e, --ed output ed script incorporating changes\n"
430 " from OLDFILE to YOURFILE into MYFILE"),
431 N_("-E, --show-overlap like -e, but bracket conflicts"),
432 N_("-3, --easy-only like -e, but incorporate only nonoverlapping changes"),
433 N_("-x, --overlap-only like -e, but incorporate only overlapping changes"),
434 N_("-X like -x, but bracket conflicts"),
435 N_("-i append `w' and `q' commands to ed scripts"),
437 N_("-m, --merge output actual merged file, according to\n"
438 " -A if no other options are given"),
440 N_("-a, --text treat all files as text"),
441 N_(" --strip-trailing-cr strip trailing carriage return on input"),
442 N_("-T, --initial-tab make tabs line up by prepending a tab"),
443 N_(" --diff-program=PROGRAM use PROGRAM to compare files"),
444 N_("-L, --label=LABEL use LABEL instead of file name\n"
445 " (can be repeated up to three times)"),
447 N_(" --help display this help and exit"),
448 N_("-v, --version output version information and exit"),
455 char const * const *p;
457 printf (_("Usage: %s [OPTION]... MYFILE OLDFILE YOURFILE\n"),
459 printf ("%s\n\n", _("Compare three files line by line."));
462 Mandatory arguments to long options are mandatory for short options too.\n\
464 for (p = option_help_msgid; *p; p++)
466 printf (" %s\n", _(*p));
470 The default output format is a somewhat human-readable representation of\n\
473 The -e, -E, -x, -X (and corresponding long) options cause an ed script\n\
474 to be output instead of the default.\n\
476 Finally, the -m (--merge) option causes diff3 to do the merge internally\n\
477 and output the actual merged file. For unusual input, this is more\n\
478 robust than using ed.\n"), stdout);
479 printf ("\n%s\n%s\n",
480 _("If a FILE is `-', read standard input."),
481 _("Exit status is 0 if successful, 1 if conflicts, 2 if trouble."));
482 emit_bug_reporting_address ();
485 /* Combine the two diffs together into one.
486 Here is the algorithm:
488 File2 is shared in common between the two diffs.
489 Diff02 is the diff between 0 and 2.
490 Diff12 is the diff between 1 and 2.
492 1) Find the range for the first block in File2.
493 a) Take the lowest of the two ranges (in File2) in the two
494 current blocks (one from each diff) as being the low
495 water mark. Assign the upper end of this block as
496 being the high water mark and move the current block up
497 one. Mark the block just moved over as to be used.
498 b) Check the next block in the diff that the high water
501 *If* the high water mark is above
502 the low end of the range in that block,
504 mark that block as to be used and move the current
505 block up. Set the high water mark to the max of
506 the high end of this block and the current. Repeat b.
508 2) Find the corresponding ranges in File0 (from the blocks
509 in diff02; line per line outside of diffs) and in File1.
510 Create a diff3_block, reserving space as indicated by the ranges.
512 3) Copy all of the pointers for file2 in. At least for now,
513 do memcmp's between corresponding strings in the two diffs.
515 4) Copy all of the pointers for file0 and 1 in. Get what is
516 needed from file2 (when there isn't a diff block, it's
517 identical to file2 within the range between diff blocks).
519 5) If the diff blocks used came from only one of the two
520 strings of diffs, then that file (i.e. the one other than
521 the common file in that diff) is the odd person out. If
522 diff blocks are used from both sets, check to see if files
525 Same number of lines? If so, do a set of memcmp's (if
526 a memcmp matches; copy the pointer over; it'll be easier
527 later during comparisons). If they match, 0 & 1 are the
528 same. If not, all three different.
530 Then do it again, until the blocks are exhausted. */
533 /* Make a three way diff (chain of diff3_block's) from two two way
534 diffs (chains of diff_block's). Assume that each of the two diffs
535 passed are onto the same file (i.e. that each of the diffs were
536 made "to" the same file). Return a three way diff pointer with
537 numbering FILE0 = the other file in diff02, FILE1 = the other file
538 in diff12, and FILEC = the common file. */
540 static struct diff3_block *
541 make_3way_diff (struct diff_block *thread0, struct diff_block *thread1)
543 /* Work on the two diffs passed to it as threads. Thread number 0
544 is diff02, thread number 1 is diff12. USING is the base of the
545 list of blocks to be used to construct each block of the three
546 way diff; if no blocks from a particular thread are to be used,
547 that element of USING is 0. LAST_USING contains the last
548 elements on each of the using lists.
550 HIGH_WATER_MARK is the highest line number in the common file
551 described in any of the diffs in either of the USING lists.
552 HIGH_WATER_THREAD names the thread. Similarly BASE_WATER_MARK
553 and BASE_WATER_THREAD describe the lowest line number in the
554 common file described in any of the diffs in either of the USING
555 lists. HIGH_WATER_DIFF is the diff from which the
556 HIGH_WATER_MARK was taken.
558 HIGH_WATER_DIFF should always be equal to
559 LAST_USING[HIGH_WATER_THREAD]. OTHER_DIFF is the next diff to
560 check for higher water, and should always be equal to
561 CURRENT[HIGH_WATER_THREAD ^ 1]. OTHER_THREAD is the thread in
562 which the OTHER_DIFF is, and hence should always be equal to
563 HIGH_WATER_THREAD ^ 1.
565 LAST_DIFF is the last diff block produced by this routine, for
566 line correspondence purposes between that diff and the one
567 currently being worked on. It is ZERO_DIFF before any blocks
568 have been created. */
570 struct diff_block *using[2];
571 struct diff_block *last_using[2];
572 struct diff_block *current[2];
576 int high_water_thread;
577 int base_water_thread;
580 struct diff_block *high_water_diff;
581 struct diff_block *other_diff;
583 struct diff3_block *result;
584 struct diff3_block *tmpblock;
585 struct diff3_block **result_end;
587 struct diff3_block const *last_diff3;
589 static struct diff3_block const zero_diff3;
593 result_end = &result;
594 current[0] = thread0; current[1] = thread1;
595 last_diff3 = &zero_diff3;
597 /* Sniff up the threads until we reach the end */
599 while (current[0] || current[1])
601 using[0] = using[1] = last_using[0] = last_using[1] = 0;
603 /* Setup low and high water threads, diffs, and marks. */
605 base_water_thread = 1;
606 else if (!current[1])
607 base_water_thread = 0;
610 (D_LOWLINE (current[0], FC) > D_LOWLINE (current[1], FC));
612 high_water_thread = base_water_thread;
614 high_water_diff = current[high_water_thread];
616 high_water_mark = D_HIGHLINE (high_water_diff, FC);
618 /* Make the diff you just got info from into the using class */
619 using[high_water_thread]
620 = last_using[high_water_thread]
622 current[high_water_thread] = high_water_diff->next;
623 last_using[high_water_thread]->next = 0;
625 /* And mark the other diff */
626 other_thread = high_water_thread ^ 0x1;
627 other_diff = current[other_thread];
629 /* Shuffle up the ladder, checking the other diff to see if it
630 needs to be incorporated. */
632 && D_LOWLINE (other_diff, FC) <= high_water_mark + 1)
635 /* Incorporate this diff into the using list. Note that
636 this doesn't take it off the current list */
637 if (using[other_thread])
638 last_using[other_thread]->next = other_diff;
640 using[other_thread] = other_diff;
641 last_using[other_thread] = other_diff;
643 /* Take it off the current list. Note that this following
644 code assumes that other_diff enters it equal to
645 current[high_water_thread ^ 0x1] */
646 current[other_thread] = current[other_thread]->next;
647 other_diff->next = 0;
649 /* Set the high_water stuff
650 If this comparison is equal, then this is the last pass
651 through this loop; since diff blocks within a given
652 thread cannot overlap, the high_water_mark will be
653 *below* the range_start of either of the next diffs. */
655 if (high_water_mark < D_HIGHLINE (other_diff, FC))
657 high_water_thread ^= 1;
658 high_water_mark = D_HIGHLINE (other_diff, FC);
661 /* Set the other diff */
662 other_thread = high_water_thread ^ 0x1;
663 other_diff = current[other_thread];
666 /* The using lists contain a list of all of the blocks to be
667 included in this diff3_block. Create it. */
669 tmpblock = using_to_diff3_block (using, last_using,
670 base_water_thread, high_water_thread,
674 fatal ("internal error: screwup in format of diff blocks");
676 /* Put it on the list. */
677 *result_end = tmpblock;
678 result_end = &tmpblock->next;
680 /* Set up corresponding lines correctly. */
681 last_diff3 = tmpblock;
686 /* Take two lists of blocks (from two separate diff threads) and put
687 them together into one diff3 block. Return a pointer to this diff3
688 block or 0 for failure.
690 All arguments besides using are for the convenience of the routine;
691 they could be derived from the using array. LAST_USING is a pair
692 of pointers to the last blocks in the using structure. LOW_THREAD
693 and HIGH_THREAD tell which threads contain the lowest and highest
694 line numbers for File0. LAST_DIFF3 contains the last diff produced
695 in the calling routine. This is used for lines mappings that
696 would still be identical to the state that diff ended in.
698 A distinction should be made in this routine between the two diffs
699 that are part of a normal two diff block, and the three diffs that
700 are part of a diff3_block. */
702 static struct diff3_block *
703 using_to_diff3_block (struct diff_block *using[2],
704 struct diff_block *last_using[2],
705 int low_thread, int high_thread,
706 struct diff3_block const *last_diff3)
709 struct diff3_block *result;
710 struct diff_block *ptr;
714 /* Find the range in the common file. */
715 lin lowc = D_LOWLINE (using[low_thread], FC);
716 lin highc = D_HIGHLINE (last_using[high_thread], FC);
718 /* Find the ranges in the other files.
719 If using[d] is null, that means that the file to which that diff
720 refers is equivalent to the common file over this range. */
722 for (d = 0; d < 2; d++)
725 low[d] = D_LOW_MAPLINE (using[d], FC, FO, lowc);
726 high[d] = D_HIGH_MAPLINE (last_using[d], FC, FO, highc);
730 low[d] = D_HIGH_MAPLINE (last_diff3, FILEC, FILE0 + d, lowc);
731 high[d] = D_HIGH_MAPLINE (last_diff3, FILEC, FILE0 + d, highc);
734 /* Create a block with the appropriate sizes */
735 result = create_diff3_block (low[0], high[0], low[1], high[1], lowc, highc);
737 /* Copy information for the common file.
738 Return with a zero if any of the compares failed. */
740 for (d = 0; d < 2; d++)
741 for (ptr = using[d]; ptr; ptr = D_NEXT (ptr))
743 lin result_offset = D_LOWLINE (ptr, FC) - lowc;
745 if (!copy_stringlist (D_LINEARRAY (ptr, FC),
746 D_LENARRAY (ptr, FC),
747 D_LINEARRAY (result, FILEC) + result_offset,
748 D_LENARRAY (result, FILEC) + result_offset,
749 D_NUMLINES (ptr, FC)))
753 /* Copy information for file d. First deal with anything that might be
754 before the first diff. */
756 for (d = 0; d < 2; d++)
758 struct diff_block *u = using[d];
759 lin lo = low[d], hi = high[d];
762 i + lo < (u ? D_LOWLINE (u, FO) : hi + 1);
765 D_RELNUM (result, FILE0 + d, i) = D_RELNUM (result, FILEC, i);
766 D_RELLEN (result, FILE0 + d, i) = D_RELLEN (result, FILEC, i);
769 for (ptr = u; ptr; ptr = D_NEXT (ptr))
771 lin result_offset = D_LOWLINE (ptr, FO) - lo;
774 if (!copy_stringlist (D_LINEARRAY (ptr, FO),
775 D_LENARRAY (ptr, FO),
776 D_LINEARRAY (result, FILE0 + d) + result_offset,
777 D_LENARRAY (result, FILE0 + d) + result_offset,
778 D_NUMLINES (ptr, FO)))
781 /* Catch the lines between here and the next diff */
782 linec = D_HIGHLINE (ptr, FC) + 1 - lowc;
783 for (i = D_HIGHLINE (ptr, FO) + 1 - lo;
784 i < (D_NEXT (ptr) ? D_LOWLINE (D_NEXT (ptr), FO) : hi + 1) - lo;
787 D_RELNUM (result, FILE0 + d, i) = D_RELNUM (result, FILEC, linec);
788 D_RELLEN (result, FILE0 + d, i) = D_RELLEN (result, FILEC, linec);
796 D3_TYPE (result) = DIFF_2ND;
798 D3_TYPE (result) = DIFF_1ST;
801 lin nl0 = D_NUMLINES (result, FILE0);
802 lin nl1 = D_NUMLINES (result, FILE1);
805 || !compare_line_list (D_LINEARRAY (result, FILE0),
806 D_LENARRAY (result, FILE0),
807 D_LINEARRAY (result, FILE1),
808 D_LENARRAY (result, FILE1),
810 D3_TYPE (result) = DIFF_ALL;
812 D3_TYPE (result) = DIFF_3RD;
818 /* Copy pointers from a list of strings to a different list of
819 strings. If a spot in the second list is already filled, make sure
820 that it is filled with the same string; if not, return false, the copy
821 incomplete. Upon successful completion of the copy, return true. */
824 copy_stringlist (char * const fromptrs[], size_t const fromlengths[],
825 char *toptrs[], size_t tolengths[],
828 register char * const *f = fromptrs;
829 register char **t = toptrs;
830 register size_t const *fl = fromlengths;
831 register size_t *tl = tolengths;
837 if (*fl != *tl || memcmp (*f, *t, *fl) != 0)
846 t++; f++; tl++; fl++;
852 /* Create a diff3_block, with ranges as specified in the arguments.
853 Allocate the arrays for the various pointers (and zero them) based
854 on the arguments passed. Return the block as a result. */
856 static struct diff3_block *
857 create_diff3_block (lin low0, lin high0,
861 struct diff3_block *result = xmalloc (sizeof *result);
864 D3_TYPE (result) = ERROR;
868 D_LOWLINE (result, FILE0) = low0;
869 D_HIGHLINE (result, FILE0) = high0;
870 D_LOWLINE (result, FILE1) = low1;
871 D_HIGHLINE (result, FILE1) = high1;
872 D_LOWLINE (result, FILE2) = low2;
873 D_HIGHLINE (result, FILE2) = high2;
875 /* Allocate and zero space */
876 numlines = D_NUMLINES (result, FILE0);
879 D_LINEARRAY (result, FILE0) = xcalloc (numlines, sizeof (char *));
880 D_LENARRAY (result, FILE0) = xcalloc (numlines, sizeof (size_t));
884 D_LINEARRAY (result, FILE0) = 0;
885 D_LENARRAY (result, FILE0) = 0;
888 numlines = D_NUMLINES (result, FILE1);
891 D_LINEARRAY (result, FILE1) = xcalloc (numlines, sizeof (char *));
892 D_LENARRAY (result, FILE1) = xcalloc (numlines, sizeof (size_t));
896 D_LINEARRAY (result, FILE1) = 0;
897 D_LENARRAY (result, FILE1) = 0;
900 numlines = D_NUMLINES (result, FILE2);
903 D_LINEARRAY (result, FILE2) = xcalloc (numlines, sizeof (char *));
904 D_LENARRAY (result, FILE2) = xcalloc (numlines, sizeof (size_t));
908 D_LINEARRAY (result, FILE2) = 0;
909 D_LENARRAY (result, FILE2) = 0;
916 /* Compare two lists of lines of text.
917 Return 1 if they are equivalent, 0 if not. */
920 compare_line_list (char * const list1[], size_t const lengths1[],
921 char * const list2[], size_t const lengths2[],
924 char * const *l1 = list1;
925 char * const *l2 = list2;
926 size_t const *lgths1 = lengths1;
927 size_t const *lgths2 = lengths2;
930 if (!*l1 || !*l2 || *lgths1 != *lgths2++
931 || memcmp (*l1++, *l2++, *lgths1++) != 0)
936 /* Input and parse two way diffs. */
938 static struct diff_block *
939 process_diff (char const *filea,
941 struct diff_block **last_block)
948 struct diff_block *block_list;
949 struct diff_block **block_list_end = &block_list;
950 struct diff_block *bptr IF_LINT (= NULL);
951 size_t too_many_lines = (PTRDIFF_MAX
952 / MIN (sizeof *bptr->lines[1],
953 sizeof *bptr->lengths[1]));
955 diff_limit = read_diff (filea, fileb, &diff_contents);
956 scan_diff = diff_contents;
958 while (scan_diff < diff_limit)
960 bptr = xmalloc (sizeof *bptr);
961 bptr->lines[0] = bptr->lines[1] = 0;
962 bptr->lengths[0] = bptr->lengths[1] = 0;
964 dt = process_diff_control (&scan_diff, bptr);
965 if (dt == ERROR || *scan_diff != '\n')
967 fprintf (stderr, _("%s: diff failed: "), program_name);
970 putc (*scan_diff, stderr);
972 while (*scan_diff++ != '\n');
977 /* Force appropriate ranges to be null, if necessary */
981 bptr->ranges[0][0]++;
984 bptr->ranges[1][0]++;
989 fatal ("internal error: invalid diff type in process_diff");
993 /* Allocate space for the pointers for the lines from filea, and
994 parcel them out among these pointers */
997 lin numlines = D_NUMLINES (bptr, 0);
998 if (too_many_lines <= numlines)
1000 bptr->lines[0] = xmalloc (numlines * sizeof *bptr->lines[0]);
1001 bptr->lengths[0] = xmalloc (numlines * sizeof *bptr->lengths[0]);
1002 for (i = 0; i < numlines; i++)
1003 scan_diff = scan_diff_line (scan_diff,
1004 &(bptr->lines[0][i]),
1005 &(bptr->lengths[0][i]),
1010 /* Get past the separator for changes */
1013 if (strncmp (scan_diff, "---\n", 4))
1014 fatal ("invalid diff format; invalid change separator");
1018 /* Allocate space for the pointers for the lines from fileb, and
1019 parcel them out among these pointers */
1022 lin numlines = D_NUMLINES (bptr, 1);
1023 if (too_many_lines <= numlines)
1025 bptr->lines[1] = xmalloc (numlines * sizeof *bptr->lines[1]);
1026 bptr->lengths[1] = xmalloc (numlines * sizeof *bptr->lengths[1]);
1027 for (i = 0; i < numlines; i++)
1028 scan_diff = scan_diff_line (scan_diff,
1029 &(bptr->lines[1][i]),
1030 &(bptr->lengths[1][i]),
1035 /* Place this block on the blocklist. */
1036 *block_list_end = bptr;
1037 block_list_end = &bptr->next;
1040 *block_list_end = NULL;
1045 /* Skip tabs and spaces, and return the first character after them. */
1050 while (*s == ' ' || *s == '\t')
1055 /* Read a nonnegative line number from S, returning the address of the
1056 first character after the line number, and storing the number into
1057 *PNUM. Return 0 if S does not point to a valid line number. */
1060 readnum (char *s, lin *pnum)
1062 unsigned char c = *s;
1070 num = c - '0' + num * 10;
1073 while (ISDIGIT (c));
1079 /* Parse a normal format diff control string. Return the type of the
1080 diff (ERROR if the format is bad). All of the other important
1081 information is filled into to the structure pointed to by db, and
1082 the string pointer (whose location is passed to this routine) is
1083 updated to point beyond the end of the string parsed. Note that
1084 only the ranges in the diff_block will be set by this routine.
1086 If some specific pair of numbers has been reduced to a single
1087 number, then both corresponding numbers in the diff block are set
1088 to that number. In general these numbers are interpreted as ranges
1089 inclusive, unless being used by the ADD or DELETE commands. It is
1090 assumed that these will be special cased in a superior routine. */
1092 static enum diff_type
1093 process_diff_control (char **string, struct diff_block *db)
1096 enum diff_type type;
1098 /* Read first set of digits */
1099 s = readnum (skipwhite (s), &db->ranges[0][RANGE_START]);
1103 /* Was that the only digit? */
1107 s = readnum (s + 1, &db->ranges[0][RANGE_END]);
1112 db->ranges[0][RANGE_END] = db->ranges[0][RANGE_START];
1114 /* Get the letter */
1128 return ERROR; /* Bad format */
1130 s++; /* Past letter */
1132 /* Read second set of digits */
1133 s = readnum (skipwhite (s), &db->ranges[1][RANGE_START]);
1137 /* Was that the only digit? */
1141 s = readnum (s + 1, &db->ranges[1][RANGE_END]);
1144 s = skipwhite (s); /* To move to end */
1147 db->ranges[1][RANGE_END] = db->ranges[1][RANGE_START];
1154 read_diff (char const *filea,
1156 char **output_placement)
1159 size_t current_chunk_size, total;
1160 int fd, wstatus, status;
1162 struct stat pipestat;
1164 #if HAVE_WORKING_FORK
1166 char const *argv[9];
1172 *ap++ = diff_program;
1175 if (strip_trailing_cr)
1176 *ap++ = "--strip-trailing-cr";
1177 *ap++ = "--horizon-lines=100";
1183 if (pipe (fds) != 0)
1184 perror_with_exit ("pipe");
1191 if (fds[1] != STDOUT_FILENO)
1193 dup2 (fds[1], STDOUT_FILENO);
1197 /* The cast to (char **) is needed for portability to older
1198 hosts with a nonstandard prototype for execvp. */
1199 execvp (diff_program, (char **) argv);
1201 _exit (errno == ENOENT ? 127 : 126);
1205 perror_with_exit ("fork");
1207 close (fds[1]); /* Prevent erroneous lack of EOF */
1213 char const args[] = " --horizon-lines=100 -- ";
1214 char *command = xmalloc (shell_quote_length (diff_program)
1216 + sizeof "--strip-trailing-cr"
1218 + shell_quote_length (filea) + 1
1219 + shell_quote_length (fileb) + 1);
1221 p = shell_quote_copy (p, diff_program);
1227 if (strip_trailing_cr)
1229 strcpy (p, " --strip-trailing-cr");
1233 p += sizeof args - 1;
1234 p = shell_quote_copy (p, filea);
1236 p = shell_quote_copy (p, fileb);
1239 fpipe = popen (command, "r");
1241 perror_with_exit (command);
1243 fd = fileno (fpipe);
1247 if (fstat (fd, &pipestat) != 0)
1248 perror_with_exit ("fstat");
1249 current_chunk_size = MAX (1, STAT_BLOCKSIZE (pipestat));
1250 diff_result = xmalloc (current_chunk_size);
1255 size_t bytes_to_read = current_chunk_size - total;
1256 size_t bytes = block_read (fd, diff_result + total, bytes_to_read);
1258 if (bytes != bytes_to_read)
1260 if (bytes == SIZE_MAX)
1261 perror_with_exit (_("read failed"));
1264 if (PTRDIFF_MAX / 2 <= current_chunk_size)
1266 current_chunk_size *= 2;
1267 diff_result = xrealloc (diff_result, current_chunk_size);
1270 if (total != 0 && diff_result[total-1] != '\n')
1271 fatal ("invalid diff format; incomplete last line");
1273 *output_placement = diff_result;
1275 #if ! HAVE_WORKING_FORK
1277 wstatus = pclose (fpipe);
1283 if (close (fd) != 0)
1284 perror_with_exit ("close");
1285 if (waitpid (pid, &wstatus, 0) < 0)
1286 perror_with_exit ("waitpid");
1290 status = ! werrno && WIFEXITED (wstatus) ? WEXITSTATUS (wstatus) : INT_MAX;
1292 if (EXIT_TROUBLE <= status)
1293 error (EXIT_TROUBLE, werrno,
1295 ? "subsidiary program `%s' could not be invoked"
1297 ? "subsidiary program `%s' not found"
1299 ? "subsidiary program `%s' failed"
1300 : "subsidiary program `%s' failed (exit status %d)"),
1301 diff_program, status);
1303 return diff_result + total;
1307 /* Scan a regular diff line (consisting of > or <, followed by a
1308 space, followed by text (including nulls) up to a newline.
1310 This next routine began life as a macro and many parameters in it
1311 are used as call-by-reference values. */
1313 scan_diff_line (char *scan_ptr, char **set_start, size_t *set_length,
1314 char *limit, char leadingchar)
1318 if (!(scan_ptr[0] == leadingchar
1319 && scan_ptr[1] == ' '))
1320 fatal ("invalid diff format; incorrect leading line chars");
1322 *set_start = line_ptr = scan_ptr + 2;
1323 while (*line_ptr++ != '\n')
1326 /* Include newline if the original line ended in a newline,
1327 or if an edit script is being generated.
1328 Copy any missing newline message to stderr if an edit script is being
1329 generated, because edit scripts cannot handle missing newlines.
1330 Return the beginning of the next line. */
1331 *set_length = line_ptr - *set_start;
1332 if (line_ptr < limit && *line_ptr == '\\')
1335 fprintf (stderr, "%s:", program_name);
1342 putc (*line_ptr, stderr);
1344 while (*line_ptr++ != '\n');
1350 /* Output a three way diff passed as a list of diff3_block's. The
1351 argument MAPPING is indexed by external file number (in the
1352 argument list) and contains the internal file number (from the diff
1353 passed). This is important because the user expects outputs in
1354 terms of the argument list number, and the diff passed may have
1355 been done slightly differently (if the last argument was "-", for
1356 example). REV_MAPPING is the inverse of MAPPING. */
1359 output_diff3 (FILE *outputfile, struct diff3_block *diff,
1360 int const mapping[3], int const rev_mapping[3])
1365 struct diff3_block *ptr;
1369 static int skew_increment[3] = { 2, 3, 1 }; /* 0==>2==>1==>3 */
1370 char const *line_prefix = initial_tab ? "\t" : " ";
1372 for (ptr = diff; ptr; ptr = D_NEXT (ptr))
1376 switch (ptr->correspond)
1380 dontprint = 3; /* Print them all */
1381 oddoneout = 3; /* Nobody's odder than anyone else */
1386 oddoneout = rev_mapping[ptr->correspond - DIFF_1ST];
1388 x[0] = oddoneout + '1';
1390 dontprint = oddoneout == 0;
1393 fatal ("internal error: invalid diff type passed to output");
1395 fprintf (outputfile, "====%s\n", x);
1397 /* Go 0, 2, 1 if the first and third outputs are equivalent. */
1399 i = (oddoneout == 1 ? skew_increment[i] : i + 1))
1401 int realfile = mapping[i];
1402 lin lowt = D_LOWLINE (ptr, realfile);
1403 lin hight = D_HIGHLINE (ptr, realfile);
1404 long int llowt = lowt;
1405 long int lhight = hight;
1407 fprintf (outputfile, "%d:", i + 1);
1408 switch (lowt - hight)
1411 fprintf (outputfile, "%lda\n", llowt - 1);
1414 fprintf (outputfile, "%ldc\n", llowt);
1417 fprintf (outputfile, "%ld,%ldc\n", llowt, lhight);
1421 if (i == dontprint) continue;
1428 fputs (line_prefix, outputfile);
1429 cp = D_RELNUM (ptr, realfile, line);
1430 length = D_RELLEN (ptr, realfile, line);
1431 fwrite (cp, sizeof (char), length, outputfile);
1433 while (++line < hight - lowt + 1);
1434 if (cp[length - 1] != '\n')
1435 fprintf (outputfile, "\n\\ %s\n",
1436 _("No newline at end of file"));
1443 /* Output to OUTPUTFILE the lines of B taken from FILENUM. Double any
1444 initial '.'s; yield nonzero if any initial '.'s were doubled. */
1447 dotlines (FILE *outputfile, struct diff3_block *b, int filenum)
1450 bool leading_dot = false;
1453 i < D_NUMLINES (b, filenum);
1456 char *line = D_RELNUM (b, filenum, i);
1460 fputc ('.', outputfile);
1462 fwrite (line, sizeof (char),
1463 D_RELLEN (b, filenum, i), outputfile);
1469 /* Output to OUTPUTFILE a '.' line. If LEADING_DOT is true, also
1470 output a command that removes initial '.'s starting with line START
1471 and continuing for NUM lines. (START is long int, not lin, for
1472 convenience with printf %ld formats.) */
1475 undotlines (FILE *outputfile, bool leading_dot, long int start, lin num)
1477 fputs (".\n", outputfile);
1481 fprintf (outputfile, "%lds/^\\.//\n", start);
1483 fprintf (outputfile, "%ld,%lds/^\\.//\n", start, start + num - 1);
1487 /* Output a diff3 set of blocks as an ed script. This script applies
1488 the changes between file's 2 & 3 to file 1. Take the precise
1489 format of the ed script to be output from global variables set
1490 during options processing. Reverse the order of
1491 the set of diff3 blocks in DIFF; this gets
1492 around the problems involved with changing line numbers in an ed
1495 As in `output_diff3', the variable MAPPING maps from file number
1496 according to the argument list to file number according to the diff
1497 passed. All files listed below are in terms of the argument list.
1498 REV_MAPPING is the inverse of MAPPING.
1500 FILE0, FILE1 and FILE2 are the strings to print as the names of the
1501 three files. These may be the actual names, or may be the
1502 arguments specified with -L.
1504 Return 1 if conflicts were found. */
1507 output_diff3_edscript (FILE *outputfile, struct diff3_block *diff,
1508 int const mapping[3], int const rev_mapping[3],
1509 char const *file0, char const *file1, char const *file2)
1512 bool conflicts_found = false;
1514 struct diff3_block *b;
1516 for (b = reverse_diff3_blocklist (diff); b; b = b->next)
1518 /* Must do mapping correctly. */
1520 = (b->correspond == DIFF_ALL
1522 : DIFF_1ST + rev_mapping[b->correspond - DIFF_1ST]);
1524 long int low0, high0;
1526 /* If we aren't supposed to do this output block, skip it. */
1530 case DIFF_2ND: if (!show_2nd) continue; conflict = true; break;
1531 case DIFF_3RD: if (overlap_only) continue; conflict = false; break;
1532 case DIFF_ALL: if (simple_only) continue; conflict = flagging; break;
1535 low0 = D_LOWLINE (b, mapping[FILE0]);
1536 high0 = D_HIGHLINE (b, mapping[FILE0]);
1540 conflicts_found = true;
1543 /* Mark end of conflict. */
1545 fprintf (outputfile, "%lda\n", high0);
1546 leading_dot = false;
1547 if (type == DIFF_ALL)
1551 /* Append lines from FILE1. */
1552 fprintf (outputfile, "||||||| %s\n", file1);
1553 leading_dot = dotlines (outputfile, b, mapping[FILE1]);
1555 /* Append lines from FILE2. */
1556 fputs ("=======\n", outputfile);
1557 leading_dot |= dotlines (outputfile, b, mapping[FILE2]);
1559 fprintf (outputfile, ">>>>>>> %s\n", file2);
1560 undotlines (outputfile, leading_dot, high0 + 2,
1561 (D_NUMLINES (b, mapping[FILE1])
1562 + D_NUMLINES (b, mapping[FILE2]) + 1));
1565 /* Mark start of conflict. */
1567 fprintf (outputfile, "%lda\n<<<<<<< %s\n", low0 - 1,
1568 type == DIFF_ALL ? file0 : file1);
1569 leading_dot = false;
1570 if (type == DIFF_2ND)
1572 /* Prepend lines from FILE1. */
1573 leading_dot = dotlines (outputfile, b, mapping[FILE1]);
1574 fputs ("=======\n", outputfile);
1576 undotlines (outputfile, leading_dot, low0 + 1,
1577 D_NUMLINES (b, mapping[FILE1]));
1579 else if (D_NUMLINES (b, mapping[FILE2]) == 0)
1580 /* Write out a delete */
1583 fprintf (outputfile, "%ldd\n", low0);
1585 fprintf (outputfile, "%ld,%ldd\n", low0, high0);
1588 /* Write out an add or change */
1590 switch (high0 - low0)
1593 fprintf (outputfile, "%lda\n", high0);
1596 fprintf (outputfile, "%ldc\n", high0);
1599 fprintf (outputfile, "%ld,%ldc\n", low0, high0);
1603 undotlines (outputfile, dotlines (outputfile, b, mapping[FILE2]),
1604 low0, D_NUMLINES (b, mapping[FILE2]));
1608 fputs ("w\nq\n", outputfile);
1609 return conflicts_found;
1612 /* Read from INFILE and output to OUTPUTFILE a set of diff3_blocks
1613 DIFF as a merged file. This acts like 'ed file0
1614 <[output_diff3_edscript]', except that it works even for binary
1615 data or incomplete lines.
1617 As before, MAPPING maps from arg list file number to diff file
1618 number, REV_MAPPING is its inverse, and FILE0, FILE1, and FILE2 are
1619 the names of the files.
1621 Return 1 if conflicts were found. */
1624 output_diff3_merge (FILE *infile, FILE *outputfile, struct diff3_block *diff,
1625 int const mapping[3], int const rev_mapping[3],
1626 char const *file0, char const *file1, char const *file2)
1630 bool conflicts_found = false;
1632 struct diff3_block *b;
1635 for (b = diff; b; b = b->next)
1637 /* Must do mapping correctly. */
1639 = ((b->correspond == DIFF_ALL)
1641 : DIFF_1ST + rev_mapping[b->correspond - DIFF_1ST]);
1642 char const *format_2nd = "<<<<<<< %s\n";
1644 /* If we aren't supposed to do this output block, skip it. */
1648 case DIFF_2ND: if (!show_2nd) continue; conflict = true; break;
1649 case DIFF_3RD: if (overlap_only) continue; conflict = false; break;
1650 case DIFF_ALL: if (simple_only) continue; conflict = flagging;
1651 format_2nd = "||||||| %s\n";
1655 /* Copy I lines from file 0. */
1656 i = D_LOWLINE (b, FILE0) - linesread - 1;
1664 if (ferror (infile))
1665 perror_with_exit (_("read failed"));
1666 else if (feof (infile))
1667 fatal ("input file shrank");
1669 putc (c, outputfile);
1675 conflicts_found = true;
1677 if (type == DIFF_ALL)
1679 /* Put in lines from FILE0 with bracket. */
1680 fprintf (outputfile, "<<<<<<< %s\n", file0);
1682 i < D_NUMLINES (b, mapping[FILE0]);
1684 fwrite (D_RELNUM (b, mapping[FILE0], i), sizeof (char),
1685 D_RELLEN (b, mapping[FILE0], i), outputfile);
1690 /* Put in lines from FILE1 with bracket. */
1691 fprintf (outputfile, format_2nd, file1);
1693 i < D_NUMLINES (b, mapping[FILE1]);
1695 fwrite (D_RELNUM (b, mapping[FILE1], i), sizeof (char),
1696 D_RELLEN (b, mapping[FILE1], i), outputfile);
1699 fputs ("=======\n", outputfile);
1702 /* Put in lines from FILE2. */
1704 i < D_NUMLINES (b, mapping[FILE2]);
1706 fwrite (D_RELNUM (b, mapping[FILE2], i), sizeof (char),
1707 D_RELLEN (b, mapping[FILE2], i), outputfile);
1710 fprintf (outputfile, ">>>>>>> %s\n", file2);
1712 /* Skip I lines in file 0. */
1713 i = D_NUMLINES (b, FILE0);
1716 while ((c = getc (infile)) != '\n')
1719 if (ferror (infile))
1720 perror_with_exit (_("read failed"));
1721 else if (feof (infile))
1724 fatal ("input file shrank");
1725 return conflicts_found;
1729 /* Copy rest of common file. */
1730 while ((c = getc (infile)) != EOF || !(ferror (infile) | feof (infile)))
1731 putc (c, outputfile);
1732 return conflicts_found;
1735 /* Reverse the order of the list of diff3 blocks. */
1737 static struct diff3_block *
1738 reverse_diff3_blocklist (struct diff3_block *diff)
1740 register struct diff3_block *tmp, *next, *prev;
1742 for (tmp = diff, prev = 0; tmp; tmp = next)
1753 fatal (char const *msgid)
1755 error (EXIT_TROUBLE, 0, "%s", _(msgid));
1760 perror_with_exit (char const *string)
1762 error (EXIT_TROUBLE, errno, "%s", string);