1 /* diff3 - compare three files line by line
3 Copyright (C) 1988-1989, 1992-1996, 1998, 2001-2002, 2004, 2006, 2009-2010
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>
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;
87 enum diff_type correspond; /* Type of diff */
88 lin ranges[3][2]; /* Ranges are inclusive */
89 char **lines[3]; /* The actual lines (may contain nulls) */
90 size_t *lengths[3]; /* Line lengths (including newlines, if any) */
91 struct diff3_block *next;
94 /* Access the ranges on a diff block. */
95 #define D_LOWLINE(diff, filenum) \
96 ((diff)->ranges[filenum][RANGE_START])
97 #define D_HIGHLINE(diff, filenum) \
98 ((diff)->ranges[filenum][RANGE_END])
99 #define D_NUMLINES(diff, filenum) \
100 (D_HIGHLINE (diff, filenum) - D_LOWLINE (diff, filenum) + 1)
102 /* Access the line numbers in a file in a diff by relative line
103 numbers (i.e. line number within the diff itself). Note that these
104 are lvalues and can be used for assignment. */
105 #define D_RELNUM(diff, filenum, linenum) \
106 ((diff)->lines[filenum][linenum])
107 #define D_RELLEN(diff, filenum, linenum) \
108 ((diff)->lengths[filenum][linenum])
110 /* And get at them directly, when that should be necessary. */
111 #define D_LINEARRAY(diff, filenum) \
112 ((diff)->lines[filenum])
113 #define D_LENARRAY(diff, filenum) \
114 ((diff)->lengths[filenum])
117 #define D_NEXT(diff) ((diff)->next)
119 /* Access the type of a diff3 block. */
120 #define D3_TYPE(diff) ((diff)->correspond)
122 /* Line mappings based on diffs. The first maps off the top of the
123 diff, the second off of the bottom. */
124 #define D_HIGH_MAPLINE(diff, fromfile, tofile, linenum) \
126 - D_HIGHLINE ((diff), (fromfile)) \
127 + D_HIGHLINE ((diff), (tofile)))
129 #define D_LOW_MAPLINE(diff, fromfile, tofile, linenum) \
131 - D_LOWLINE ((diff), (fromfile)) \
132 + D_LOWLINE ((diff), (tofile)))
134 /* Options variables for flags set on command line. */
136 /* If nonzero, treat all files as text files, never as binary. */
139 /* Remove trailing carriage returns from input. */
140 static bool strip_trailing_cr;
142 /* If nonzero, write out an ed script instead of the standard diff3 format. */
143 static bool edscript;
145 /* If nonzero, in the case of overlapping diffs (type DIFF_ALL),
146 preserve the lines which would normally be deleted from
147 file 1 with a special flagging mechanism. */
148 static bool flagging;
150 /* Use a tab to align output lines (-T). */
151 static bool initial_tab;
153 /* If nonzero, do not output information for overlapping diffs. */
154 static bool simple_only;
156 /* If nonzero, do not output information for non-overlapping diffs. */
157 static bool overlap_only;
159 /* If nonzero, show information for DIFF_2ND diffs. */
160 static bool show_2nd;
162 /* If nonzero, include `:wq' at the end of the script
163 to write out the file being edited. */
164 static bool finalwrite;
166 /* If nonzero, output a merged file. */
169 static char *read_diff (char const *, char const *, char **);
170 static char *scan_diff_line (char *, char **, size_t *, char *, char);
171 static enum diff_type process_diff_control (char **, struct diff_block *);
172 static bool compare_line_list (char * const[], size_t const[], char * const[], size_t const[], lin);
173 static bool copy_stringlist (char * const[], size_t const[], char *[], size_t[], lin);
174 static bool output_diff3_edscript (FILE *, struct diff3_block *, int const[3], int const[3], char const *, char const *, char const *);
175 static bool output_diff3_merge (FILE *, FILE *, struct diff3_block *, int const[3], int const[3], char const *, char const *, char const *);
176 static struct diff3_block *create_diff3_block (lin, lin, lin, lin, lin, lin);
177 static struct diff3_block *make_3way_diff (struct diff_block *, struct diff_block *);
178 static struct diff3_block *reverse_diff3_blocklist (struct diff3_block *);
179 static struct diff3_block *using_to_diff3_block (struct diff_block *[2], struct diff_block *[2], int, int, struct diff3_block const *);
180 static struct diff_block *process_diff (char const *, char const *, struct diff_block **);
181 static void check_stdout (void);
182 static void fatal (char const *) __attribute__((noreturn));
183 static void output_diff3 (FILE *, struct diff3_block *, int const[3], int const[3]);
184 static void perror_with_exit (char const *) __attribute__((noreturn));
185 static void try_help (char const *, char const *) __attribute__((noreturn));
186 static void usage (void);
188 static char const *diff_program = DEFAULT_DIFF_PROGRAM;
190 /* Values for long options that do not have single-letter equivalents. */
193 DIFF_PROGRAM_OPTION = CHAR_MAX + 1,
195 STRIP_TRAILING_CR_OPTION
198 static struct option const longopts[] =
200 {"diff-program", 1, 0, DIFF_PROGRAM_OPTION},
201 {"easy-only", 0, 0, '3'},
203 {"help", 0, 0, HELP_OPTION},
204 {"initial-tab", 0, 0, 'T'},
205 {"label", 1, 0, 'L'},
206 {"merge", 0, 0, 'm'},
207 {"overlap-only", 0, 0, 'x'},
208 {"show-all", 0, 0, 'A'},
209 {"show-overlap", 0, 0, 'E'},
210 {"strip-trailing-cr", 0, 0, STRIP_TRAILING_CR_OPTION},
212 {"version", 0, 0, 'v'},
217 main (int argc, char **argv)
224 bool conflicts_found;
225 struct diff_block *thread0, *thread1, *last_block;
226 struct diff3_block *diff3;
228 char *tag_strings[3];
233 exit_failure = EXIT_TROUBLE;
234 initialize_main (&argc, &argv);
235 set_program_name (argv[0]);
236 setlocale (LC_ALL, "");
237 textdomain (PACKAGE);
240 while ((c = getopt_long (argc, argv, "aeimvx3AEL:TX", longopts, 0)) != -1)
278 case STRIP_TRAILING_CR_OPTION:
279 strip_trailing_cr = true;
282 version_etc (stdout, PROGRAM_NAME, PACKAGE_NAME, PACKAGE_VERSION,
283 AUTHORS, (char *) NULL);
286 case DIFF_PROGRAM_OPTION:
287 diff_program = optarg;
294 /* Handle up to three -L options. */
297 tag_strings[tag_count++] = optarg;
300 try_help ("too many file label options", 0);
306 edscript = incompat & ~merge; /* -AeExX3 without -m implies ed script. */
307 show_2nd |= ~incompat & merge; /* -m without -AeExX3 implies -A. */
308 flagging |= ~incompat & merge;
310 if (incompat > 1 /* Ensure at most one of -AeExX3. */
311 || finalwrite & merge /* -i -m would rewrite input file. */
312 || (tag_count && ! flagging)) /* -L requires one of -AEX. */
313 try_help ("incompatible options", 0);
315 if (argc - optind != 3)
317 if (argc - optind < 3)
318 try_help ("missing operand after `%s'", argv[argc - 1]);
320 try_help ("extra operand `%s'", argv[optind + 3]);
323 file = &argv[optind];
325 for (i = tag_count; i < 3; i++)
326 tag_strings[i] = file[i];
328 /* Always compare file1 to file2, even if file2 is "-".
329 This is needed for -mAeExX3. Using the file0 as
330 the common file would produce wrong results, because if the
331 file0-file1 diffs didn't line up with the file0-file2 diffs
332 (which is entirely possible since we don't use diff's -n option),
333 diff3 might report phantom changes from file1 to file2.
335 Also, try to compare file0 to file1, because this is where
336 changes are expected to come from. Diffing between these pairs
337 of files is more likely to avoid phantom changes from file0 to file1.
339 Historically, the default common file was file2, so some older
340 applications (e.g. Emacs ediff) used file2 as the ancestor. So,
341 for compatibility, if this is a 3-way diff (not a merge or
342 edscript), prefer file2 as the common file. */
344 common = 2 - (edscript | merge);
346 if (STREQ (file[common], "-"))
348 /* Sigh. We've got standard input as the common file. We can't
349 call diff twice on stdin. Use the other arg as the common
352 if (STREQ (file[0], "-") || STREQ (file[common], "-"))
353 fatal ("`-' specified for more than one input file");
357 mapping[1] = 3 - common;
360 for (i = 0; i < 3; i++)
361 rev_mapping[mapping[i]] = i;
363 for (i = 0; i < 3; i++)
364 if (strcmp (file[i], "-") != 0)
366 if (stat (file[i], &statb) < 0)
367 perror_with_exit (file[i]);
368 else if (S_ISDIR (statb.st_mode))
369 error (EXIT_TROUBLE, EISDIR, "%s", file[i]);
373 /* System V fork+wait does not work if SIGCHLD is ignored. */
374 signal (SIGCHLD, SIG_DFL);
377 /* Invoke diff twice on two pairs of input files, combine the two
378 diffs, and output them. */
380 commonname = file[rev_mapping[FILEC]];
381 thread1 = process_diff (file[rev_mapping[FILE1]], commonname, &last_block);
382 thread0 = process_diff (file[rev_mapping[FILE0]], commonname, &last_block);
383 diff3 = make_3way_diff (thread0, thread1);
386 = output_diff3_edscript (stdout, diff3, mapping, rev_mapping,
387 tag_strings[0], tag_strings[1], tag_strings[2]);
390 xfreopen (file[rev_mapping[FILE0]], "r", stdin);
392 = output_diff3_merge (stdin, stdout, diff3, mapping, rev_mapping,
393 tag_strings[0], tag_strings[1], tag_strings[2]);
395 fatal ("read failed");
399 output_diff3 (stdout, diff3, mapping, rev_mapping);
400 conflicts_found = false;
404 exit (conflicts_found);
405 return conflicts_found;
409 try_help (char const *reason_msgid, char const *operand)
412 error (0, 0, _(reason_msgid), operand);
413 error (EXIT_TROUBLE, 0,
414 _("Try `%s --help' for more information."), program_name);
422 fatal ("write failed");
423 else if (fclose (stdout) != 0)
424 perror_with_exit (_("standard output"));
427 static char const * const option_help_msgid[] = {
428 N_("-e --ed Output unmerged changes from OLDFILE to YOURFILE into MYFILE."),
429 N_("-E --show-overlap Output unmerged changes, bracketing conflicts."),
430 N_("-A --show-all Output all changes, bracketing conflicts."),
431 N_("-x --overlap-only Output overlapping changes."),
432 N_("-X Output overlapping changes, bracketing them."),
433 N_("-3 --easy-only Output unmerged nonoverlapping changes."),
435 N_("-m --merge Output merged file instead of ed script (default -A)."),
436 N_("-L LABEL --label=LABEL Use LABEL instead of file name."),
437 N_("-i Append `w' and `q' commands to ed scripts."),
438 N_("-a --text Treat all files as text."),
439 N_("--strip-trailing-cr Strip trailing carriage return on input."),
440 N_("-T --initial-tab Make tabs line up by prepending a tab."),
441 N_("--diff-program=PROGRAM Use PROGRAM to compare files."),
443 N_("-v --version Output version info."),
444 N_("--help Output this help."),
451 char const * const *p;
453 printf (_("Usage: %s [OPTION]... MYFILE OLDFILE YOURFILE\n"),
455 printf ("%s\n\n", _("Compare three files line by line."));
456 for (p = option_help_msgid; *p; p++)
458 printf (" %s\n", _(*p));
461 printf ("\n%s\n%s\n",
462 _("If a FILE is `-', read standard input."),
463 _("Exit status is 0 if successful, 1 if conflicts, 2 if trouble."));
464 emit_bug_reporting_address ();
467 /* Combine the two diffs together into one.
468 Here is the algorithm:
470 File2 is shared in common between the two diffs.
471 Diff02 is the diff between 0 and 2.
472 Diff12 is the diff between 1 and 2.
474 1) Find the range for the first block in File2.
475 a) Take the lowest of the two ranges (in File2) in the two
476 current blocks (one from each diff) as being the low
477 water mark. Assign the upper end of this block as
478 being the high water mark and move the current block up
479 one. Mark the block just moved over as to be used.
480 b) Check the next block in the diff that the high water
483 *If* the high water mark is above
484 the low end of the range in that block,
486 mark that block as to be used and move the current
487 block up. Set the high water mark to the max of
488 the high end of this block and the current. Repeat b.
490 2) Find the corresponding ranges in File0 (from the blocks
491 in diff02; line per line outside of diffs) and in File1.
492 Create a diff3_block, reserving space as indicated by the ranges.
494 3) Copy all of the pointers for file2 in. At least for now,
495 do memcmp's between corresponding strings in the two diffs.
497 4) Copy all of the pointers for file0 and 1 in. Get what is
498 needed from file2 (when there isn't a diff block, it's
499 identical to file2 within the range between diff blocks).
501 5) If the diff blocks used came from only one of the two
502 strings of diffs, then that file (i.e. the one other than
503 the common file in that diff) is the odd person out. If
504 diff blocks are used from both sets, check to see if files
507 Same number of lines? If so, do a set of memcmp's (if
508 a memcmp matches; copy the pointer over; it'll be easier
509 later during comparisons). If they match, 0 & 1 are the
510 same. If not, all three different.
512 Then do it again, until the blocks are exhausted. */
515 /* Make a three way diff (chain of diff3_block's) from two two way
516 diffs (chains of diff_block's). Assume that each of the two diffs
517 passed are onto the same file (i.e. that each of the diffs were
518 made "to" the same file). Return a three way diff pointer with
519 numbering FILE0 = the other file in diff02, FILE1 = the other file
520 in diff12, and FILEC = the common file. */
522 static struct diff3_block *
523 make_3way_diff (struct diff_block *thread0, struct diff_block *thread1)
525 /* Work on the two diffs passed to it as threads. Thread number 0
526 is diff02, thread number 1 is diff12. USING is the base of the
527 list of blocks to be used to construct each block of the three
528 way diff; if no blocks from a particular thread are to be used,
529 that element of USING is 0. LAST_USING contains the last
530 elements on each of the using lists.
532 HIGH_WATER_MARK is the highest line number in the common file
533 described in any of the diffs in either of the USING lists.
534 HIGH_WATER_THREAD names the thread. Similarly BASE_WATER_MARK
535 and BASE_WATER_THREAD describe the lowest line number in the
536 common file described in any of the diffs in either of the USING
537 lists. HIGH_WATER_DIFF is the diff from which the
538 HIGH_WATER_MARK was taken.
540 HIGH_WATER_DIFF should always be equal to
541 LAST_USING[HIGH_WATER_THREAD]. OTHER_DIFF is the next diff to
542 check for higher water, and should always be equal to
543 CURRENT[HIGH_WATER_THREAD ^ 1]. OTHER_THREAD is the thread in
544 which the OTHER_DIFF is, and hence should always be equal to
545 HIGH_WATER_THREAD ^ 1.
547 LAST_DIFF is the last diff block produced by this routine, for
548 line correspondence purposes between that diff and the one
549 currently being worked on. It is ZERO_DIFF before any blocks
550 have been created. */
552 struct diff_block *using[2];
553 struct diff_block *last_using[2];
554 struct diff_block *current[2];
558 int high_water_thread;
559 int base_water_thread;
562 struct diff_block *high_water_diff;
563 struct diff_block *other_diff;
565 struct diff3_block *result;
566 struct diff3_block *tmpblock;
567 struct diff3_block **result_end;
569 struct diff3_block const *last_diff3;
571 static struct diff3_block const zero_diff3;
575 result_end = &result;
576 current[0] = thread0; current[1] = thread1;
577 last_diff3 = &zero_diff3;
579 /* Sniff up the threads until we reach the end */
581 while (current[0] || current[1])
583 using[0] = using[1] = last_using[0] = last_using[1] = 0;
585 /* Setup low and high water threads, diffs, and marks. */
587 base_water_thread = 1;
588 else if (!current[1])
589 base_water_thread = 0;
592 (D_LOWLINE (current[0], FC) > D_LOWLINE (current[1], FC));
594 high_water_thread = base_water_thread;
596 high_water_diff = current[high_water_thread];
598 high_water_mark = D_HIGHLINE (high_water_diff, FC);
600 /* Make the diff you just got info from into the using class */
601 using[high_water_thread]
602 = last_using[high_water_thread]
604 current[high_water_thread] = high_water_diff->next;
605 last_using[high_water_thread]->next = 0;
607 /* And mark the other diff */
608 other_thread = high_water_thread ^ 0x1;
609 other_diff = current[other_thread];
611 /* Shuffle up the ladder, checking the other diff to see if it
612 needs to be incorporated. */
614 && D_LOWLINE (other_diff, FC) <= high_water_mark + 1)
617 /* Incorporate this diff into the using list. Note that
618 this doesn't take it off the current list */
619 if (using[other_thread])
620 last_using[other_thread]->next = other_diff;
622 using[other_thread] = other_diff;
623 last_using[other_thread] = other_diff;
625 /* Take it off the current list. Note that this following
626 code assumes that other_diff enters it equal to
627 current[high_water_thread ^ 0x1] */
628 current[other_thread] = current[other_thread]->next;
629 other_diff->next = 0;
631 /* Set the high_water stuff
632 If this comparison is equal, then this is the last pass
633 through this loop; since diff blocks within a given
634 thread cannot overlap, the high_water_mark will be
635 *below* the range_start of either of the next diffs. */
637 if (high_water_mark < D_HIGHLINE (other_diff, FC))
639 high_water_thread ^= 1;
640 high_water_mark = D_HIGHLINE (other_diff, FC);
643 /* Set the other diff */
644 other_thread = high_water_thread ^ 0x1;
645 other_diff = current[other_thread];
648 /* The using lists contain a list of all of the blocks to be
649 included in this diff3_block. Create it. */
651 tmpblock = using_to_diff3_block (using, last_using,
652 base_water_thread, high_water_thread,
656 fatal ("internal error: screwup in format of diff blocks");
658 /* Put it on the list. */
659 *result_end = tmpblock;
660 result_end = &tmpblock->next;
662 /* Set up corresponding lines correctly. */
663 last_diff3 = tmpblock;
668 /* Take two lists of blocks (from two separate diff threads) and put
669 them together into one diff3 block. Return a pointer to this diff3
670 block or 0 for failure.
672 All arguments besides using are for the convenience of the routine;
673 they could be derived from the using array. LAST_USING is a pair
674 of pointers to the last blocks in the using structure. LOW_THREAD
675 and HIGH_THREAD tell which threads contain the lowest and highest
676 line numbers for File0. LAST_DIFF3 contains the last diff produced
677 in the calling routine. This is used for lines mappings that
678 would still be identical to the state that diff ended in.
680 A distinction should be made in this routine between the two diffs
681 that are part of a normal two diff block, and the three diffs that
682 are part of a diff3_block. */
684 static struct diff3_block *
685 using_to_diff3_block (struct diff_block *using[2],
686 struct diff_block *last_using[2],
687 int low_thread, int high_thread,
688 struct diff3_block const *last_diff3)
691 struct diff3_block *result;
692 struct diff_block *ptr;
696 /* Find the range in the common file. */
697 lin lowc = D_LOWLINE (using[low_thread], FC);
698 lin highc = D_HIGHLINE (last_using[high_thread], FC);
700 /* Find the ranges in the other files.
701 If using[d] is null, that means that the file to which that diff
702 refers is equivalent to the common file over this range. */
704 for (d = 0; d < 2; d++)
707 low[d] = D_LOW_MAPLINE (using[d], FC, FO, lowc);
708 high[d] = D_HIGH_MAPLINE (last_using[d], FC, FO, highc);
712 low[d] = D_HIGH_MAPLINE (last_diff3, FILEC, FILE0 + d, lowc);
713 high[d] = D_HIGH_MAPLINE (last_diff3, FILEC, FILE0 + d, highc);
716 /* Create a block with the appropriate sizes */
717 result = create_diff3_block (low[0], high[0], low[1], high[1], lowc, highc);
719 /* Copy information for the common file.
720 Return with a zero if any of the compares failed. */
722 for (d = 0; d < 2; d++)
723 for (ptr = using[d]; ptr; ptr = D_NEXT (ptr))
725 lin result_offset = D_LOWLINE (ptr, FC) - lowc;
727 if (!copy_stringlist (D_LINEARRAY (ptr, FC),
728 D_LENARRAY (ptr, FC),
729 D_LINEARRAY (result, FILEC) + result_offset,
730 D_LENARRAY (result, FILEC) + result_offset,
731 D_NUMLINES (ptr, FC)))
735 /* Copy information for file d. First deal with anything that might be
736 before the first diff. */
738 for (d = 0; d < 2; d++)
740 struct diff_block *u = using[d];
741 lin lo = low[d], hi = high[d];
744 i + lo < (u ? D_LOWLINE (u, FO) : hi + 1);
747 D_RELNUM (result, FILE0 + d, i) = D_RELNUM (result, FILEC, i);
748 D_RELLEN (result, FILE0 + d, i) = D_RELLEN (result, FILEC, i);
751 for (ptr = u; ptr; ptr = D_NEXT (ptr))
753 lin result_offset = D_LOWLINE (ptr, FO) - lo;
756 if (!copy_stringlist (D_LINEARRAY (ptr, FO),
757 D_LENARRAY (ptr, FO),
758 D_LINEARRAY (result, FILE0 + d) + result_offset,
759 D_LENARRAY (result, FILE0 + d) + result_offset,
760 D_NUMLINES (ptr, FO)))
763 /* Catch the lines between here and the next diff */
764 linec = D_HIGHLINE (ptr, FC) + 1 - lowc;
765 for (i = D_HIGHLINE (ptr, FO) + 1 - lo;
766 i < (D_NEXT (ptr) ? D_LOWLINE (D_NEXT (ptr), FO) : hi + 1) - lo;
769 D_RELNUM (result, FILE0 + d, i) = D_RELNUM (result, FILEC, linec);
770 D_RELLEN (result, FILE0 + d, i) = D_RELLEN (result, FILEC, linec);
778 D3_TYPE (result) = DIFF_2ND;
780 D3_TYPE (result) = DIFF_1ST;
783 lin nl0 = D_NUMLINES (result, FILE0);
784 lin nl1 = D_NUMLINES (result, FILE1);
787 || !compare_line_list (D_LINEARRAY (result, FILE0),
788 D_LENARRAY (result, FILE0),
789 D_LINEARRAY (result, FILE1),
790 D_LENARRAY (result, FILE1),
792 D3_TYPE (result) = DIFF_ALL;
794 D3_TYPE (result) = DIFF_3RD;
800 /* Copy pointers from a list of strings to a different list of
801 strings. If a spot in the second list is already filled, make sure
802 that it is filled with the same string; if not, return false, the copy
803 incomplete. Upon successful completion of the copy, return true. */
806 copy_stringlist (char * const fromptrs[], size_t const fromlengths[],
807 char *toptrs[], size_t tolengths[],
810 register char * const *f = fromptrs;
811 register char **t = toptrs;
812 register size_t const *fl = fromlengths;
813 register size_t *tl = tolengths;
819 if (*fl != *tl || memcmp (*f, *t, *fl) != 0)
828 t++; f++; tl++; fl++;
834 /* Create a diff3_block, with ranges as specified in the arguments.
835 Allocate the arrays for the various pointers (and zero them) based
836 on the arguments passed. Return the block as a result. */
838 static struct diff3_block *
839 create_diff3_block (lin low0, lin high0,
843 struct diff3_block *result = xmalloc (sizeof *result);
846 D3_TYPE (result) = ERROR;
850 D_LOWLINE (result, FILE0) = low0;
851 D_HIGHLINE (result, FILE0) = high0;
852 D_LOWLINE (result, FILE1) = low1;
853 D_HIGHLINE (result, FILE1) = high1;
854 D_LOWLINE (result, FILE2) = low2;
855 D_HIGHLINE (result, FILE2) = high2;
857 /* Allocate and zero space */
858 numlines = D_NUMLINES (result, FILE0);
861 D_LINEARRAY (result, FILE0) = xcalloc (numlines, sizeof (char *));
862 D_LENARRAY (result, FILE0) = xcalloc (numlines, sizeof (size_t));
866 D_LINEARRAY (result, FILE0) = 0;
867 D_LENARRAY (result, FILE0) = 0;
870 numlines = D_NUMLINES (result, FILE1);
873 D_LINEARRAY (result, FILE1) = xcalloc (numlines, sizeof (char *));
874 D_LENARRAY (result, FILE1) = xcalloc (numlines, sizeof (size_t));
878 D_LINEARRAY (result, FILE1) = 0;
879 D_LENARRAY (result, FILE1) = 0;
882 numlines = D_NUMLINES (result, FILE2);
885 D_LINEARRAY (result, FILE2) = xcalloc (numlines, sizeof (char *));
886 D_LENARRAY (result, FILE2) = xcalloc (numlines, sizeof (size_t));
890 D_LINEARRAY (result, FILE2) = 0;
891 D_LENARRAY (result, FILE2) = 0;
898 /* Compare two lists of lines of text.
899 Return 1 if they are equivalent, 0 if not. */
902 compare_line_list (char * const list1[], size_t const lengths1[],
903 char * const list2[], size_t const lengths2[],
906 char * const *l1 = list1;
907 char * const *l2 = list2;
908 size_t const *lgths1 = lengths1;
909 size_t const *lgths2 = lengths2;
912 if (!*l1 || !*l2 || *lgths1 != *lgths2++
913 || memcmp (*l1++, *l2++, *lgths1++) != 0)
918 /* Input and parse two way diffs. */
920 static struct diff_block *
921 process_diff (char const *filea,
923 struct diff_block **last_block)
930 struct diff_block *block_list;
931 struct diff_block **block_list_end = &block_list;
932 struct diff_block *bptr IF_LINT (= NULL);
933 size_t too_many_lines = (PTRDIFF_MAX
934 / MIN (sizeof *bptr->lines[1],
935 sizeof *bptr->lengths[1]));
937 diff_limit = read_diff (filea, fileb, &diff_contents);
938 scan_diff = diff_contents;
940 while (scan_diff < diff_limit)
942 bptr = xmalloc (sizeof *bptr);
943 bptr->lines[0] = bptr->lines[1] = 0;
944 bptr->lengths[0] = bptr->lengths[1] = 0;
946 dt = process_diff_control (&scan_diff, bptr);
947 if (dt == ERROR || *scan_diff != '\n')
949 fprintf (stderr, _("%s: diff failed: "), program_name);
952 putc (*scan_diff, stderr);
954 while (*scan_diff++ != '\n');
959 /* Force appropriate ranges to be null, if necessary */
963 bptr->ranges[0][0]++;
966 bptr->ranges[1][0]++;
971 fatal ("internal error: invalid diff type in process_diff");
975 /* Allocate space for the pointers for the lines from filea, and
976 parcel them out among these pointers */
979 lin numlines = D_NUMLINES (bptr, 0);
980 if (too_many_lines <= numlines)
982 bptr->lines[0] = xmalloc (numlines * sizeof *bptr->lines[0]);
983 bptr->lengths[0] = xmalloc (numlines * sizeof *bptr->lengths[0]);
984 for (i = 0; i < numlines; i++)
985 scan_diff = scan_diff_line (scan_diff,
986 &(bptr->lines[0][i]),
987 &(bptr->lengths[0][i]),
992 /* Get past the separator for changes */
995 if (strncmp (scan_diff, "---\n", 4))
996 fatal ("invalid diff format; invalid change separator");
1000 /* Allocate space for the pointers for the lines from fileb, and
1001 parcel them out among these pointers */
1004 lin numlines = D_NUMLINES (bptr, 1);
1005 if (too_many_lines <= numlines)
1007 bptr->lines[1] = xmalloc (numlines * sizeof *bptr->lines[1]);
1008 bptr->lengths[1] = xmalloc (numlines * sizeof *bptr->lengths[1]);
1009 for (i = 0; i < numlines; i++)
1010 scan_diff = scan_diff_line (scan_diff,
1011 &(bptr->lines[1][i]),
1012 &(bptr->lengths[1][i]),
1017 /* Place this block on the blocklist. */
1018 *block_list_end = bptr;
1019 block_list_end = &bptr->next;
1022 *block_list_end = NULL;
1027 /* Skip tabs and spaces, and return the first character after them. */
1032 while (*s == ' ' || *s == '\t')
1037 /* Read a nonnegative line number from S, returning the address of the
1038 first character after the line number, and storing the number into
1039 *PNUM. Return 0 if S does not point to a valid line number. */
1042 readnum (char *s, lin *pnum)
1044 unsigned char c = *s;
1052 num = c - '0' + num * 10;
1055 while (ISDIGIT (c));
1061 /* Parse a normal format diff control string. Return the type of the
1062 diff (ERROR if the format is bad). All of the other important
1063 information is filled into to the structure pointed to by db, and
1064 the string pointer (whose location is passed to this routine) is
1065 updated to point beyond the end of the string parsed. Note that
1066 only the ranges in the diff_block will be set by this routine.
1068 If some specific pair of numbers has been reduced to a single
1069 number, then both corresponding numbers in the diff block are set
1070 to that number. In general these numbers are interpreted as ranges
1071 inclusive, unless being used by the ADD or DELETE commands. It is
1072 assumed that these will be special cased in a superior routine. */
1074 static enum diff_type
1075 process_diff_control (char **string, struct diff_block *db)
1078 enum diff_type type;
1080 /* Read first set of digits */
1081 s = readnum (skipwhite (s), &db->ranges[0][RANGE_START]);
1085 /* Was that the only digit? */
1089 s = readnum (s + 1, &db->ranges[0][RANGE_END]);
1094 db->ranges[0][RANGE_END] = db->ranges[0][RANGE_START];
1096 /* Get the letter */
1110 return ERROR; /* Bad format */
1112 s++; /* Past letter */
1114 /* Read second set of digits */
1115 s = readnum (skipwhite (s), &db->ranges[1][RANGE_START]);
1119 /* Was that the only digit? */
1123 s = readnum (s + 1, &db->ranges[1][RANGE_END]);
1126 s = skipwhite (s); /* To move to end */
1129 db->ranges[1][RANGE_END] = db->ranges[1][RANGE_START];
1136 read_diff (char const *filea,
1138 char **output_placement)
1141 size_t current_chunk_size, total;
1142 int fd, wstatus, status;
1144 struct stat pipestat;
1146 #if HAVE_WORKING_FORK || HAVE_WORKING_VFORK
1148 char const *argv[9];
1154 *ap++ = diff_program;
1157 if (strip_trailing_cr)
1158 *ap++ = "--strip-trailing-cr";
1159 *ap++ = "--horizon-lines=100";
1165 if (pipe (fds) != 0)
1166 perror_with_exit ("pipe");
1173 if (fds[1] != STDOUT_FILENO)
1175 dup2 (fds[1], STDOUT_FILENO);
1179 /* The cast to (char **) is needed for portability to older
1180 hosts with a nonstandard prototype for execvp. */
1181 execvp (diff_program, (char **) argv);
1183 _exit (errno == ENOENT ? 127 : 126);
1187 perror_with_exit ("fork");
1189 close (fds[1]); /* Prevent erroneous lack of EOF */
1195 char const args[] = " --horizon-lines=100 -- ";
1196 char *command = xmalloc (shell_quote_length (diff_program)
1198 + sizeof "--strip-trailing-cr"
1200 + shell_quote_length (filea) + 1
1201 + shell_quote_length (fileb) + 1);
1203 p = shell_quote_copy (p, diff_program);
1209 if (strip_trailing_cr)
1211 strcpy (p, " --strip-trailing-cr");
1215 p += sizeof args - 1;
1216 p = shell_quote_copy (p, filea);
1218 p = shell_quote_copy (p, fileb);
1221 fpipe = popen (command, "r");
1223 perror_with_exit (command);
1225 fd = fileno (fpipe);
1229 if (fstat (fd, &pipestat) != 0)
1230 perror_with_exit ("fstat");
1231 current_chunk_size = MAX (1, STAT_BLOCKSIZE (pipestat));
1232 diff_result = xmalloc (current_chunk_size);
1237 size_t bytes_to_read = current_chunk_size - total;
1238 size_t bytes = block_read (fd, diff_result + total, bytes_to_read);
1240 if (bytes != bytes_to_read)
1242 if (bytes == SIZE_MAX)
1243 perror_with_exit (_("read failed"));
1246 if (PTRDIFF_MAX / 2 <= current_chunk_size)
1248 current_chunk_size *= 2;
1249 diff_result = xrealloc (diff_result, current_chunk_size);
1252 if (total != 0 && diff_result[total-1] != '\n')
1253 fatal ("invalid diff format; incomplete last line");
1255 *output_placement = diff_result;
1257 #if ! (HAVE_WORKING_FORK || HAVE_WORKING_VFORK)
1259 wstatus = pclose (fpipe);
1265 if (close (fd) != 0)
1266 perror_with_exit ("close");
1267 if (waitpid (pid, &wstatus, 0) < 0)
1268 perror_with_exit ("waitpid");
1272 status = ! werrno && WIFEXITED (wstatus) ? WEXITSTATUS (wstatus) : INT_MAX;
1274 if (EXIT_TROUBLE <= status)
1275 error (EXIT_TROUBLE, werrno,
1277 ? "subsidiary program `%s' could not be invoked"
1279 ? "subsidiary program `%s' not found"
1281 ? "subsidiary program `%s' failed"
1282 : "subsidiary program `%s' failed (exit status %d)"),
1283 diff_program, status);
1285 return diff_result + total;
1289 /* Scan a regular diff line (consisting of > or <, followed by a
1290 space, followed by text (including nulls) up to a newline.
1292 This next routine began life as a macro and many parameters in it
1293 are used as call-by-reference values. */
1295 scan_diff_line (char *scan_ptr, char **set_start, size_t *set_length,
1296 char *limit, char leadingchar)
1300 if (!(scan_ptr[0] == leadingchar
1301 && scan_ptr[1] == ' '))
1302 fatal ("invalid diff format; incorrect leading line chars");
1304 *set_start = line_ptr = scan_ptr + 2;
1305 while (*line_ptr++ != '\n')
1308 /* Include newline if the original line ended in a newline,
1309 or if an edit script is being generated.
1310 Copy any missing newline message to stderr if an edit script is being
1311 generated, because edit scripts cannot handle missing newlines.
1312 Return the beginning of the next line. */
1313 *set_length = line_ptr - *set_start;
1314 if (line_ptr < limit && *line_ptr == '\\')
1317 fprintf (stderr, "%s:", program_name);
1324 putc (*line_ptr, stderr);
1326 while (*line_ptr++ != '\n');
1332 /* Output a three way diff passed as a list of diff3_block's. The
1333 argument MAPPING is indexed by external file number (in the
1334 argument list) and contains the internal file number (from the diff
1335 passed). This is important because the user expects outputs in
1336 terms of the argument list number, and the diff passed may have
1337 been done slightly differently (if the last argument was "-", for
1338 example). REV_MAPPING is the inverse of MAPPING. */
1341 output_diff3 (FILE *outputfile, struct diff3_block *diff,
1342 int const mapping[3], int const rev_mapping[3])
1347 struct diff3_block *ptr;
1351 static int skew_increment[3] = { 2, 3, 1 }; /* 0==>2==>1==>3 */
1352 char const *line_prefix = initial_tab ? "\t" : " ";
1354 for (ptr = diff; ptr; ptr = D_NEXT (ptr))
1358 switch (ptr->correspond)
1362 dontprint = 3; /* Print them all */
1363 oddoneout = 3; /* Nobody's odder than anyone else */
1368 oddoneout = rev_mapping[ptr->correspond - DIFF_1ST];
1370 x[0] = oddoneout + '1';
1372 dontprint = oddoneout == 0;
1375 fatal ("internal error: invalid diff type passed to output");
1377 fprintf (outputfile, "====%s\n", x);
1379 /* Go 0, 2, 1 if the first and third outputs are equivalent. */
1381 i = (oddoneout == 1 ? skew_increment[i] : i + 1))
1383 int realfile = mapping[i];
1384 lin lowt = D_LOWLINE (ptr, realfile);
1385 lin hight = D_HIGHLINE (ptr, realfile);
1386 long int llowt = lowt;
1387 long int lhight = hight;
1389 fprintf (outputfile, "%d:", i + 1);
1390 switch (lowt - hight)
1393 fprintf (outputfile, "%lda\n", llowt - 1);
1396 fprintf (outputfile, "%ldc\n", llowt);
1399 fprintf (outputfile, "%ld,%ldc\n", llowt, lhight);
1403 if (i == dontprint) continue;
1410 fputs (line_prefix, outputfile);
1411 cp = D_RELNUM (ptr, realfile, line);
1412 length = D_RELLEN (ptr, realfile, line);
1413 fwrite (cp, sizeof (char), length, outputfile);
1415 while (++line < hight - lowt + 1);
1416 if (cp[length - 1] != '\n')
1417 fprintf (outputfile, "\n\\ %s\n",
1418 _("No newline at end of file"));
1425 /* Output to OUTPUTFILE the lines of B taken from FILENUM. Double any
1426 initial '.'s; yield nonzero if any initial '.'s were doubled. */
1429 dotlines (FILE *outputfile, struct diff3_block *b, int filenum)
1432 bool leading_dot = false;
1435 i < D_NUMLINES (b, filenum);
1438 char *line = D_RELNUM (b, filenum, i);
1442 fputc ('.', outputfile);
1444 fwrite (line, sizeof (char),
1445 D_RELLEN (b, filenum, i), outputfile);
1451 /* Output to OUTPUTFILE a '.' line. If LEADING_DOT is true, also
1452 output a command that removes initial '.'s starting with line START
1453 and continuing for NUM lines. (START is long int, not lin, for
1454 convenience with printf %ld formats.) */
1457 undotlines (FILE *outputfile, bool leading_dot, long int start, lin num)
1459 fputs (".\n", outputfile);
1463 fprintf (outputfile, "%lds/^\\.//\n", start);
1465 fprintf (outputfile, "%ld,%lds/^\\.//\n", start, start + num - 1);
1469 /* Output a diff3 set of blocks as an ed script. This script applies
1470 the changes between file's 2 & 3 to file 1. Take the precise
1471 format of the ed script to be output from global variables set
1472 during options processing. Reverse the order of
1473 the set of diff3 blocks in DIFF; this gets
1474 around the problems involved with changing line numbers in an ed
1477 As in `output_diff3', the variable MAPPING maps from file number
1478 according to the argument list to file number according to the diff
1479 passed. All files listed below are in terms of the argument list.
1480 REV_MAPPING is the inverse of MAPPING.
1482 FILE0, FILE1 and FILE2 are the strings to print as the names of the
1483 three files. These may be the actual names, or may be the
1484 arguments specified with -L.
1486 Return 1 if conflicts were found. */
1489 output_diff3_edscript (FILE *outputfile, struct diff3_block *diff,
1490 int const mapping[3], int const rev_mapping[3],
1491 char const *file0, char const *file1, char const *file2)
1494 bool conflicts_found = false;
1496 struct diff3_block *b;
1498 for (b = reverse_diff3_blocklist (diff); b; b = b->next)
1500 /* Must do mapping correctly. */
1502 = (b->correspond == DIFF_ALL
1504 : DIFF_1ST + rev_mapping[b->correspond - DIFF_1ST]);
1506 long int low0, high0;
1508 /* If we aren't supposed to do this output block, skip it. */
1512 case DIFF_2ND: if (!show_2nd) continue; conflict = true; break;
1513 case DIFF_3RD: if (overlap_only) continue; conflict = false; break;
1514 case DIFF_ALL: if (simple_only) continue; conflict = flagging; break;
1517 low0 = D_LOWLINE (b, mapping[FILE0]);
1518 high0 = D_HIGHLINE (b, mapping[FILE0]);
1522 conflicts_found = true;
1525 /* Mark end of conflict. */
1527 fprintf (outputfile, "%lda\n", high0);
1528 leading_dot = false;
1529 if (type == DIFF_ALL)
1533 /* Append lines from FILE1. */
1534 fprintf (outputfile, "||||||| %s\n", file1);
1535 leading_dot = dotlines (outputfile, b, mapping[FILE1]);
1537 /* Append lines from FILE2. */
1538 fputs ("=======\n", outputfile);
1539 leading_dot |= dotlines (outputfile, b, mapping[FILE2]);
1541 fprintf (outputfile, ">>>>>>> %s\n", file2);
1542 undotlines (outputfile, leading_dot, high0 + 2,
1543 (D_NUMLINES (b, mapping[FILE1])
1544 + D_NUMLINES (b, mapping[FILE2]) + 1));
1547 /* Mark start of conflict. */
1549 fprintf (outputfile, "%lda\n<<<<<<< %s\n", low0 - 1,
1550 type == DIFF_ALL ? file0 : file1);
1551 leading_dot = false;
1552 if (type == DIFF_2ND)
1554 /* Prepend lines from FILE1. */
1555 leading_dot = dotlines (outputfile, b, mapping[FILE1]);
1556 fputs ("=======\n", outputfile);
1558 undotlines (outputfile, leading_dot, low0 + 1,
1559 D_NUMLINES (b, mapping[FILE1]));
1561 else if (D_NUMLINES (b, mapping[FILE2]) == 0)
1562 /* Write out a delete */
1565 fprintf (outputfile, "%ldd\n", low0);
1567 fprintf (outputfile, "%ld,%ldd\n", low0, high0);
1570 /* Write out an add or change */
1572 switch (high0 - low0)
1575 fprintf (outputfile, "%lda\n", high0);
1578 fprintf (outputfile, "%ldc\n", high0);
1581 fprintf (outputfile, "%ld,%ldc\n", low0, high0);
1585 undotlines (outputfile, dotlines (outputfile, b, mapping[FILE2]),
1586 low0, D_NUMLINES (b, mapping[FILE2]));
1590 fputs ("w\nq\n", outputfile);
1591 return conflicts_found;
1594 /* Read from INFILE and output to OUTPUTFILE a set of diff3_blocks
1595 DIFF as a merged file. This acts like 'ed file0
1596 <[output_diff3_edscript]', except that it works even for binary
1597 data or incomplete lines.
1599 As before, MAPPING maps from arg list file number to diff file
1600 number, REV_MAPPING is its inverse, and FILE0, FILE1, and FILE2 are
1601 the names of the files.
1603 Return 1 if conflicts were found. */
1606 output_diff3_merge (FILE *infile, FILE *outputfile, struct diff3_block *diff,
1607 int const mapping[3], int const rev_mapping[3],
1608 char const *file0, char const *file1, char const *file2)
1612 bool conflicts_found = false;
1614 struct diff3_block *b;
1617 for (b = diff; b; b = b->next)
1619 /* Must do mapping correctly. */
1621 = ((b->correspond == DIFF_ALL)
1623 : DIFF_1ST + rev_mapping[b->correspond - DIFF_1ST]);
1624 char const *format_2nd = "<<<<<<< %s\n";
1626 /* If we aren't supposed to do this output block, skip it. */
1630 case DIFF_2ND: if (!show_2nd) continue; conflict = true; break;
1631 case DIFF_3RD: if (overlap_only) continue; conflict = false; break;
1632 case DIFF_ALL: if (simple_only) continue; conflict = flagging;
1633 format_2nd = "||||||| %s\n";
1637 /* Copy I lines from file 0. */
1638 i = D_LOWLINE (b, FILE0) - linesread - 1;
1646 if (ferror (infile))
1647 perror_with_exit (_("read failed"));
1648 else if (feof (infile))
1649 fatal ("input file shrank");
1651 putc (c, outputfile);
1657 conflicts_found = true;
1659 if (type == DIFF_ALL)
1661 /* Put in lines from FILE0 with bracket. */
1662 fprintf (outputfile, "<<<<<<< %s\n", file0);
1664 i < D_NUMLINES (b, mapping[FILE0]);
1666 fwrite (D_RELNUM (b, mapping[FILE0], i), sizeof (char),
1667 D_RELLEN (b, mapping[FILE0], i), outputfile);
1672 /* Put in lines from FILE1 with bracket. */
1673 fprintf (outputfile, format_2nd, file1);
1675 i < D_NUMLINES (b, mapping[FILE1]);
1677 fwrite (D_RELNUM (b, mapping[FILE1], i), sizeof (char),
1678 D_RELLEN (b, mapping[FILE1], i), outputfile);
1681 fputs ("=======\n", outputfile);
1684 /* Put in lines from FILE2. */
1686 i < D_NUMLINES (b, mapping[FILE2]);
1688 fwrite (D_RELNUM (b, mapping[FILE2], i), sizeof (char),
1689 D_RELLEN (b, mapping[FILE2], i), outputfile);
1692 fprintf (outputfile, ">>>>>>> %s\n", file2);
1694 /* Skip I lines in file 0. */
1695 i = D_NUMLINES (b, FILE0);
1698 while ((c = getc (infile)) != '\n')
1701 if (ferror (infile))
1702 perror_with_exit (_("read failed"));
1703 else if (feof (infile))
1706 fatal ("input file shrank");
1707 return conflicts_found;
1711 /* Copy rest of common file. */
1712 while ((c = getc (infile)) != EOF || !(ferror (infile) | feof (infile)))
1713 putc (c, outputfile);
1714 return conflicts_found;
1717 /* Reverse the order of the list of diff3 blocks. */
1719 static struct diff3_block *
1720 reverse_diff3_blocklist (struct diff3_block *diff)
1722 register struct diff3_block *tmp, *next, *prev;
1724 for (tmp = diff, prev = 0; tmp; tmp = next)
1735 fatal (char const *msgid)
1737 error (EXIT_TROUBLE, 0, "%s", _(msgid));
1742 perror_with_exit (char const *string)
1744 error (EXIT_TROUBLE, errno, "%s", string);