1 /* diff3 - compare three files line by line
3 Copyright (C) 1988-1989, 1992-1996, 1998, 2001-2002, 2004, 2006, 2009-2013
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>
32 #include <system-quote.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. */
1047 static char * _GL_ATTRIBUTE_PURE
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;
1163 char const *argv[9];
1165 #if HAVE_WORKING_FORK
1174 *ap++ = diff_program;
1177 if (strip_trailing_cr)
1178 *ap++ = "--strip-trailing-cr";
1179 *ap++ = "--horizon-lines=100";
1185 #if HAVE_WORKING_FORK
1187 if (pipe (fds) != 0)
1188 perror_with_exit ("pipe");
1195 if (fds[1] != STDOUT_FILENO)
1197 dup2 (fds[1], STDOUT_FILENO);
1201 /* The cast to (char **) is needed for portability to older
1202 hosts with a nonstandard prototype for execvp. */
1203 execvp (diff_program, (char **) argv);
1205 _exit (errno == ENOENT ? 127 : 126);
1209 perror_with_exit ("fork");
1211 close (fds[1]); /* Prevent erroneous lack of EOF */
1216 command = system_quote_argv (SCI_SYSTEM, (char **) argv);
1218 fpipe = popen (command, "r");
1220 perror_with_exit (command);
1222 fd = fileno (fpipe);
1226 if (fstat (fd, &pipestat) != 0)
1227 perror_with_exit ("fstat");
1228 current_chunk_size = MAX (1, STAT_BLOCKSIZE (pipestat));
1229 diff_result = xmalloc (current_chunk_size);
1234 size_t bytes_to_read = current_chunk_size - total;
1235 size_t bytes = block_read (fd, diff_result + total, bytes_to_read);
1237 if (bytes != bytes_to_read)
1239 if (bytes == SIZE_MAX)
1240 perror_with_exit (_("read failed"));
1243 if (PTRDIFF_MAX / 2 <= current_chunk_size)
1245 current_chunk_size *= 2;
1246 diff_result = xrealloc (diff_result, current_chunk_size);
1249 if (total != 0 && diff_result[total-1] != '\n')
1250 fatal ("invalid diff format; incomplete last line");
1252 *output_placement = diff_result;
1254 #if ! HAVE_WORKING_FORK
1256 wstatus = pclose (fpipe);
1262 if (close (fd) != 0)
1263 perror_with_exit ("close");
1264 if (waitpid (pid, &wstatus, 0) < 0)
1265 perror_with_exit ("waitpid");
1269 status = ! werrno && WIFEXITED (wstatus) ? WEXITSTATUS (wstatus) : INT_MAX;
1271 if (EXIT_TROUBLE <= status)
1272 error (EXIT_TROUBLE, werrno,
1274 ? "subsidiary program '%s' could not be invoked"
1276 ? "subsidiary program '%s' not found"
1278 ? "subsidiary program '%s' failed"
1279 : "subsidiary program '%s' failed (exit status %d)"),
1280 diff_program, status);
1282 return diff_result + total;
1286 /* Scan a regular diff line (consisting of > or <, followed by a
1287 space, followed by text (including nulls) up to a newline.
1289 This next routine began life as a macro and many parameters in it
1290 are used as call-by-reference values. */
1292 scan_diff_line (char *scan_ptr, char **set_start, size_t *set_length,
1293 char *limit, char leadingchar)
1297 if (!(scan_ptr[0] == leadingchar
1298 && scan_ptr[1] == ' '))
1299 fatal ("invalid diff format; incorrect leading line chars");
1301 *set_start = line_ptr = scan_ptr + 2;
1302 while (*line_ptr++ != '\n')
1305 /* Include newline if the original line ended in a newline,
1306 or if an edit script is being generated.
1307 Copy any missing newline message to stderr if an edit script is being
1308 generated, because edit scripts cannot handle missing newlines.
1309 Return the beginning of the next line. */
1310 *set_length = line_ptr - *set_start;
1311 if (line_ptr < limit && *line_ptr == '\\')
1314 fprintf (stderr, "%s:", program_name);
1321 putc (*line_ptr, stderr);
1323 while (*line_ptr++ != '\n');
1329 /* Output a three way diff passed as a list of diff3_block's. The
1330 argument MAPPING is indexed by external file number (in the
1331 argument list) and contains the internal file number (from the diff
1332 passed). This is important because the user expects outputs in
1333 terms of the argument list number, and the diff passed may have
1334 been done slightly differently (if the last argument was "-", for
1335 example). REV_MAPPING is the inverse of MAPPING. */
1338 output_diff3 (FILE *outputfile, struct diff3_block *diff,
1339 int const mapping[3], int const rev_mapping[3])
1344 struct diff3_block *ptr;
1348 static int skew_increment[3] = { 2, 3, 1 }; /* 0==>2==>1==>3 */
1349 char const *line_prefix = initial_tab ? "\t" : " ";
1351 for (ptr = diff; ptr; ptr = D_NEXT (ptr))
1355 switch (ptr->correspond)
1359 dontprint = 3; /* Print them all */
1360 oddoneout = 3; /* Nobody's odder than anyone else */
1365 oddoneout = rev_mapping[ptr->correspond - DIFF_1ST];
1367 x[0] = oddoneout + '1';
1369 dontprint = oddoneout == 0;
1372 fatal ("internal error: invalid diff type passed to output");
1374 fprintf (outputfile, "====%s\n", x);
1376 /* Go 0, 2, 1 if the first and third outputs are equivalent. */
1378 i = (oddoneout == 1 ? skew_increment[i] : i + 1))
1380 int realfile = mapping[i];
1381 lin lowt = D_LOWLINE (ptr, realfile);
1382 lin hight = D_HIGHLINE (ptr, realfile);
1383 long int llowt = lowt;
1384 long int lhight = hight;
1386 fprintf (outputfile, "%d:", i + 1);
1387 switch (lowt - hight)
1390 fprintf (outputfile, "%lda\n", llowt - 1);
1393 fprintf (outputfile, "%ldc\n", llowt);
1396 fprintf (outputfile, "%ld,%ldc\n", llowt, lhight);
1400 if (i == dontprint) continue;
1407 fputs (line_prefix, outputfile);
1408 cp = D_RELNUM (ptr, realfile, line);
1409 length = D_RELLEN (ptr, realfile, line);
1410 fwrite (cp, sizeof (char), length, outputfile);
1412 while (++line < hight - lowt + 1);
1413 if (cp[length - 1] != '\n')
1414 fprintf (outputfile, "\n\\ %s\n",
1415 _("No newline at end of file"));
1422 /* Output to OUTPUTFILE the lines of B taken from FILENUM. Double any
1423 initial '.'s; yield nonzero if any initial '.'s were doubled. */
1426 dotlines (FILE *outputfile, struct diff3_block *b, int filenum)
1429 bool leading_dot = false;
1432 i < D_NUMLINES (b, filenum);
1435 char *line = D_RELNUM (b, filenum, i);
1439 fputc ('.', outputfile);
1441 fwrite (line, sizeof (char),
1442 D_RELLEN (b, filenum, i), outputfile);
1448 /* Output to OUTPUTFILE a '.' line. If LEADING_DOT is true, also
1449 output a command that removes initial '.'s starting with line START
1450 and continuing for NUM lines. (START is long int, not lin, for
1451 convenience with printf %ld formats.) */
1454 undotlines (FILE *outputfile, bool leading_dot, long int start, lin num)
1456 fputs (".\n", outputfile);
1460 fprintf (outputfile, "%lds/^\\.//\n", start);
1462 fprintf (outputfile, "%ld,%lds/^\\.//\n", start, start + num - 1);
1466 /* Output a diff3 set of blocks as an ed script. This script applies
1467 the changes between file's 2 & 3 to file 1. Take the precise
1468 format of the ed script to be output from global variables set
1469 during options processing. Reverse the order of
1470 the set of diff3 blocks in DIFF; this gets
1471 around the problems involved with changing line numbers in an ed
1474 As in 'output_diff3', the variable MAPPING maps from file number
1475 according to the argument list to file number according to the diff
1476 passed. All files listed below are in terms of the argument list.
1477 REV_MAPPING is the inverse of MAPPING.
1479 FILE0, FILE1 and FILE2 are the strings to print as the names of the
1480 three files. These may be the actual names, or may be the
1481 arguments specified with -L.
1483 Return 1 if conflicts were found. */
1486 output_diff3_edscript (FILE *outputfile, struct diff3_block *diff,
1487 int const mapping[3], int const rev_mapping[3],
1488 char const *file0, char const *file1, char const *file2)
1491 bool conflicts_found = false;
1493 struct diff3_block *b;
1495 for (b = reverse_diff3_blocklist (diff); b; b = b->next)
1497 /* Must do mapping correctly. */
1499 = (b->correspond == DIFF_ALL
1501 : DIFF_1ST + rev_mapping[b->correspond - DIFF_1ST]);
1503 long int low0, high0;
1505 /* If we aren't supposed to do this output block, skip it. */
1509 case DIFF_2ND: if (!show_2nd) continue; conflict = true; break;
1510 case DIFF_3RD: if (overlap_only) continue; conflict = false; break;
1511 case DIFF_ALL: if (simple_only) continue; conflict = flagging; break;
1514 low0 = D_LOWLINE (b, mapping[FILE0]);
1515 high0 = D_HIGHLINE (b, mapping[FILE0]);
1519 conflicts_found = true;
1522 /* Mark end of conflict. */
1524 fprintf (outputfile, "%lda\n", high0);
1525 leading_dot = false;
1526 if (type == DIFF_ALL)
1530 /* Append lines from FILE1. */
1531 fprintf (outputfile, "||||||| %s\n", file1);
1532 leading_dot = dotlines (outputfile, b, mapping[FILE1]);
1534 /* Append lines from FILE2. */
1535 fputs ("=======\n", outputfile);
1536 leading_dot |= dotlines (outputfile, b, mapping[FILE2]);
1538 fprintf (outputfile, ">>>>>>> %s\n", file2);
1539 undotlines (outputfile, leading_dot, high0 + 2,
1540 (D_NUMLINES (b, mapping[FILE1])
1541 + D_NUMLINES (b, mapping[FILE2]) + 1));
1544 /* Mark start of conflict. */
1546 fprintf (outputfile, "%lda\n<<<<<<< %s\n", low0 - 1,
1547 type == DIFF_ALL ? file0 : file1);
1548 leading_dot = false;
1549 if (type == DIFF_2ND)
1551 /* Prepend lines from FILE1. */
1552 leading_dot = dotlines (outputfile, b, mapping[FILE1]);
1553 fputs ("=======\n", outputfile);
1555 undotlines (outputfile, leading_dot, low0 + 1,
1556 D_NUMLINES (b, mapping[FILE1]));
1558 else if (D_NUMLINES (b, mapping[FILE2]) == 0)
1559 /* Write out a delete */
1562 fprintf (outputfile, "%ldd\n", low0);
1564 fprintf (outputfile, "%ld,%ldd\n", low0, high0);
1567 /* Write out an add or change */
1569 switch (high0 - low0)
1572 fprintf (outputfile, "%lda\n", high0);
1575 fprintf (outputfile, "%ldc\n", high0);
1578 fprintf (outputfile, "%ld,%ldc\n", low0, high0);
1582 undotlines (outputfile, dotlines (outputfile, b, mapping[FILE2]),
1583 low0, D_NUMLINES (b, mapping[FILE2]));
1587 fputs ("w\nq\n", outputfile);
1588 return conflicts_found;
1591 /* Read from INFILE and output to OUTPUTFILE a set of diff3_blocks
1592 DIFF as a merged file. This acts like 'ed file0
1593 <[output_diff3_edscript]', except that it works even for binary
1594 data or incomplete lines.
1596 As before, MAPPING maps from arg list file number to diff file
1597 number, REV_MAPPING is its inverse, and FILE0, FILE1, and FILE2 are
1598 the names of the files.
1600 Return 1 if conflicts were found. */
1603 output_diff3_merge (FILE *infile, FILE *outputfile, struct diff3_block *diff,
1604 int const mapping[3], int const rev_mapping[3],
1605 char const *file0, char const *file1, char const *file2)
1609 bool conflicts_found = false;
1611 struct diff3_block *b;
1614 for (b = diff; b; b = b->next)
1616 /* Must do mapping correctly. */
1618 = ((b->correspond == DIFF_ALL)
1620 : DIFF_1ST + rev_mapping[b->correspond - DIFF_1ST]);
1621 char const *format_2nd = "<<<<<<< %s\n";
1623 /* If we aren't supposed to do this output block, skip it. */
1627 case DIFF_2ND: if (!show_2nd) continue; conflict = true; break;
1628 case DIFF_3RD: if (overlap_only) continue; conflict = false; break;
1629 case DIFF_ALL: if (simple_only) continue; conflict = flagging;
1630 format_2nd = "||||||| %s\n";
1634 /* Copy I lines from file 0. */
1635 i = D_LOWLINE (b, FILE0) - linesread - 1;
1643 if (ferror (infile))
1644 perror_with_exit (_("read failed"));
1645 else if (feof (infile))
1646 fatal ("input file shrank");
1648 putc (c, outputfile);
1654 conflicts_found = true;
1656 if (type == DIFF_ALL)
1658 /* Put in lines from FILE0 with bracket. */
1659 fprintf (outputfile, "<<<<<<< %s\n", file0);
1661 i < D_NUMLINES (b, mapping[FILE0]);
1663 fwrite (D_RELNUM (b, mapping[FILE0], i), sizeof (char),
1664 D_RELLEN (b, mapping[FILE0], i), outputfile);
1669 /* Put in lines from FILE1 with bracket. */
1670 fprintf (outputfile, format_2nd, file1);
1672 i < D_NUMLINES (b, mapping[FILE1]);
1674 fwrite (D_RELNUM (b, mapping[FILE1], i), sizeof (char),
1675 D_RELLEN (b, mapping[FILE1], i), outputfile);
1678 fputs ("=======\n", outputfile);
1681 /* Put in lines from FILE2. */
1683 i < D_NUMLINES (b, mapping[FILE2]);
1685 fwrite (D_RELNUM (b, mapping[FILE2], i), sizeof (char),
1686 D_RELLEN (b, mapping[FILE2], i), outputfile);
1689 fprintf (outputfile, ">>>>>>> %s\n", file2);
1691 /* Skip I lines in file 0. */
1692 i = D_NUMLINES (b, FILE0);
1695 while ((c = getc (infile)) != '\n')
1698 if (ferror (infile))
1699 perror_with_exit (_("read failed"));
1700 else if (feof (infile))
1703 fatal ("input file shrank");
1704 return conflicts_found;
1708 /* Copy rest of common file. */
1709 while ((c = getc (infile)) != EOF || !(ferror (infile) | feof (infile)))
1710 putc (c, outputfile);
1711 return conflicts_found;
1714 /* Reverse the order of the list of diff3 blocks. */
1716 static struct diff3_block *
1717 reverse_diff3_blocklist (struct diff3_block *diff)
1719 register struct diff3_block *tmp, *next, *prev;
1721 for (tmp = diff, prev = 0; tmp; tmp = next)
1732 fatal (char const *msgid)
1734 error (EXIT_TROUBLE, 0, "%s", _(msgid));
1739 perror_with_exit (char const *string)
1741 error (EXIT_TROUBLE, errno, "%s", string);