1 /* diff3 - compare three files line by line
3 Copyright (C) 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1998, 2001,
4 2002 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 2, or (at your option)
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.
14 See the 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; see the file COPYING.
18 If not, write to the Free Software Foundation,
19 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
23 static char const copyright_string[] =
24 "Copyright (C) 2002 Free Software Foundation, Inc.";
26 static char const authorship_msgid[] = N_("Written by Randy Smith.");
39 extern char const version_string[];
42 * Internal data structures and macros for the diff3 program; includes
43 * data structures for both diff3 diffs and normal diffs.
46 /* 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:
58 * Different files within a two way diff.
59 * FC is the common file, FO the other file.
64 /* The ranges are indexed by */
69 ERROR, /* Should not be used */
70 ADD, /* Two way diff add */
71 CHANGE, /* Two way diff change */
72 DELETE, /* Two way diff delete */
73 DIFF_ALL, /* All three are different */
74 DIFF_1ST, /* Only the first is different */
75 DIFF_2ND, /* Only the second */
76 DIFF_3RD /* Only the third */
81 lin ranges[2][2]; /* Ranges are inclusive */
82 char **lines[2]; /* The actual lines (may contain nulls) */
83 size_t *lengths[2]; /* Line lengths (including newlines, if any) */
84 struct diff_block *next;
90 enum diff_type correspond; /* Type of diff */
91 lin ranges[3][2]; /* Ranges are inclusive */
92 char **lines[3]; /* The actual lines (may contain nulls) */
93 size_t *lengths[3]; /* Line lengths (including newlines, if any) */
94 struct diff3_block *next;
98 * Access the ranges on a diff block.
100 #define D_LOWLINE(diff, filenum) \
101 ((diff)->ranges[filenum][RANGE_START])
102 #define D_HIGHLINE(diff, filenum) \
103 ((diff)->ranges[filenum][RANGE_END])
104 #define D_NUMLINES(diff, filenum) \
105 (D_HIGHLINE (diff, filenum) - D_LOWLINE (diff, filenum) + 1)
108 * Access the line numbers in a file in a diff by relative line
109 * numbers (i.e. line number within the diff itself). Note that these
110 * are lvalues and can be used for assignment.
112 #define D_RELNUM(diff, filenum, linenum) \
113 ((diff)->lines[filenum][linenum])
114 #define D_RELLEN(diff, filenum, linenum) \
115 ((diff)->lengths[filenum][linenum])
118 * And get at them directly, when that should be necessary.
120 #define D_LINEARRAY(diff, filenum) \
121 ((diff)->lines[filenum])
122 #define D_LENARRAY(diff, filenum) \
123 ((diff)->lengths[filenum])
128 #define D_NEXT(diff) ((diff)->next)
131 * Access the type of a diff3 block.
133 #define D3_TYPE(diff) ((diff)->correspond)
136 * Line mappings based on diffs. The first maps off the top of the
137 * diff, the second off of the bottom.
139 #define D_HIGH_MAPLINE(diff, fromfile, tofile, linenum) \
141 - D_HIGHLINE ((diff), (fromfile)) \
142 + D_HIGHLINE ((diff), (tofile)))
144 #define D_LOW_MAPLINE(diff, fromfile, tofile, linenum) \
146 - D_LOWLINE ((diff), (fromfile)) \
147 + D_LOWLINE ((diff), (tofile)))
149 /* Options variables for flags set on command line. */
151 /* If nonzero, treat all files as text files, never as binary. */
154 /* If nonzero, write out an ed script instead of the standard diff3 format. */
155 static bool edscript;
157 /* If nonzero, in the case of overlapping diffs (type DIFF_ALL),
158 preserve the lines which would normally be deleted from
159 file 1 with a special flagging mechanism. */
160 static bool flagging;
162 /* Use a tab to align output lines (-T). */
163 static bool initial_tab;
165 /* If nonzero, do not output information for overlapping diffs. */
166 static bool simple_only;
168 /* If nonzero, do not output information for non-overlapping diffs. */
169 static bool overlap_only;
171 /* If nonzero, show information for DIFF_2ND diffs. */
172 static bool show_2nd;
174 /* If nonzero, include `:wq' at the end of the script
175 to write out the file being edited. */
176 static bool finalwrite;
178 /* If nonzero, output a merged file. */
183 static char *read_diff (char const *, char const *, char **);
184 static char *scan_diff_line (char *, char **, size_t *, char *, char);
185 static enum diff_type process_diff_control (char **, struct diff_block *);
186 static bool compare_line_list (char * const[], size_t const[], char * const[], size_t const[], lin);
187 static bool copy_stringlist (char * const[], size_t const[], char *[], size_t[], lin);
188 static bool output_diff3_edscript (FILE *, struct diff3_block *, int const[3], int const[3], char const *, char const *, char const *);
189 static bool output_diff3_merge (FILE *, FILE *, struct diff3_block *, int const[3], int const[3], char const *, char const *, char const *);
190 static struct diff3_block *create_diff3_block (lin, lin, lin, lin, lin, lin);
191 static struct diff3_block *make_3way_diff (struct diff_block *, struct diff_block *);
192 static struct diff3_block *reverse_diff3_blocklist (struct diff3_block *);
193 static struct diff3_block *using_to_diff3_block (struct diff_block *[2], struct diff_block *[2], int, int, struct diff3_block const *);
194 static struct diff_block *process_diff (char const *, char const *, struct diff_block **);
195 static void check_stdout (void);
196 static void fatal (char const *) __attribute__((noreturn));
197 static void output_diff3 (FILE *, struct diff3_block *, int const[3], int const[3]);
198 static void perror_with_exit (char const *) __attribute__((noreturn));
199 static void try_help (char const *, char const *) __attribute__((noreturn));
200 static void usage (void);
202 static char const *diff_program = DEFAULT_DIFF_PROGRAM;
204 /* Values for long options that do not have single-letter equivalents. */
207 DIFF_PROGRAM_OPTION = CHAR_MAX + 1,
211 static struct option const longopts[] =
214 {"show-all", 0, 0, 'A'},
216 {"diff-program", 1, 0, DIFF_PROGRAM_OPTION},
217 {"show-overlap", 0, 0, 'E'},
218 {"label", 1, 0, 'L'},
219 {"merge", 0, 0, 'm'},
220 {"initial-tab", 0, 0, 'T'},
221 {"overlap-only", 0, 0, 'x'},
222 {"easy-only", 0, 0, '3'},
223 {"version", 0, 0, 'v'},
224 {"help", 0, 0, HELP_OPTION},
229 * Main program. Calls diff twice on two pairs of input files,
230 * combines the two diffs, and outputs them.
233 main (int argc, char **argv)
240 bool conflicts_found;
241 struct diff_block *thread0, *thread1, *last_block;
242 struct diff3_block *diff3;
244 char *tag_strings[3];
250 initialize_main (&argc, &argv);
251 program_name = argv[0];
252 setlocale (LC_ALL, "");
253 bindtextdomain (PACKAGE, LOCALEDIR);
254 textdomain (PACKAGE);
255 c_stack_action (c_stack_die);
257 while ((c = getopt_long (argc, argv, "aeimvx3AEL:TX", longopts, 0)) != -1)
296 printf ("diff3 %s\n%s\n\n%s\n\n%s\n",
297 version_string, copyright_string,
298 _(free_software_msgid), _(authorship_msgid));
301 case DIFF_PROGRAM_OPTION:
302 diff_program = optarg;
309 /* Handle up to three -L options. */
312 tag_strings[tag_count++] = optarg;
315 try_help ("too many file label options", 0);
321 edscript = incompat & ~merge; /* -AeExX3 without -m implies ed script. */
322 show_2nd |= ~incompat & merge; /* -m without -AeExX3 implies -A. */
323 flagging |= ~incompat & merge;
325 if (incompat > 1 /* Ensure at most one of -AeExX3. */
326 || finalwrite & merge /* -i -m would rewrite input file. */
327 || (tag_count && ! flagging)) /* -L requires one of -AEX. */
328 try_help ("incompatible options", 0);
330 if (argc - optind != 3)
332 if (argc - optind < 3)
333 try_help ("missing operand after `%s'", argv[argc - 1]);
335 try_help ("extra operand `%s'", argv[optind + 3]);
338 file = &argv[optind];
340 for (i = tag_count; i < 3; i++)
341 tag_strings[i] = file[i];
343 /* Always compare file1 to file2, even if file2 is "-".
344 This is needed for -mAeExX3. Using the file0 as
345 the common file would produce wrong results, because if the
346 file0-file1 diffs didn't line up with the file0-file2 diffs
347 (which is entirely possible since we don't use diff's -n option),
348 diff3 might report phantom changes from file1 to file2.
350 Also, try to compare file0 to file1, because this is where
351 changes are expected to come from. Diffing between these pairs
352 of files is more likely to avoid phantom changes from file0 to file1.
354 Historically, the default common file was file2, so some older
355 applications (e.g. Emacs ediff) used file2 as the ancestor. So,
356 for compatibility, if this is a 3-way diff (not a merge or
357 edscript), prefer file2 as the common file. */
359 common = 2 - (edscript | merge);
361 if (strcmp (file[common], "-") == 0)
363 /* Sigh. We've got standard input as the common file. We can't
364 call diff twice on stdin. Use the other arg as the common
367 if (strcmp (file[0], "-") == 0 || strcmp (file[common], "-") == 0)
368 fatal ("`-' specified for more than one input file");
372 mapping[1] = 3 - common;
375 for (i = 0; i < 3; i++)
376 rev_mapping[mapping[i]] = i;
378 for (i = 0; i < 3; i++)
379 if (strcmp (file[i], "-") != 0)
381 if (stat (file[i], &statb) < 0)
382 perror_with_exit (file[i]);
383 else if (S_ISDIR (statb.st_mode))
384 error (EXIT_TROUBLE, EISDIR, "%s", file[i]);
388 /* System V fork+wait does not work if SIGCHLD is ignored. */
389 signal (SIGCHLD, SIG_DFL);
392 commonname = file[rev_mapping[FILEC]];
393 thread1 = process_diff (file[rev_mapping[FILE1]], commonname, &last_block);
394 thread0 = process_diff (file[rev_mapping[FILE0]], commonname, &last_block);
395 diff3 = make_3way_diff (thread0, thread1);
398 = output_diff3_edscript (stdout, diff3, mapping, rev_mapping,
399 tag_strings[0], tag_strings[1], tag_strings[2]);
402 if (! freopen (file[rev_mapping[FILE0]], "r", stdin))
403 perror_with_exit (file[rev_mapping[FILE0]]);
405 = output_diff3_merge (stdin, stdout, diff3, mapping, rev_mapping,
406 tag_strings[0], tag_strings[1], tag_strings[2]);
408 fatal ("read failed");
412 output_diff3 (stdout, diff3, mapping, rev_mapping);
417 exit (conflicts_found);
418 return conflicts_found;
422 try_help (char const *reason_msgid, char const *operand)
425 error (0, 0, _(reason_msgid), operand);
426 error (EXIT_TROUBLE, 0,
427 _("Try `%s --help' for more information."), program_name);
435 fatal ("write failed");
436 else if (fclose (stdout) != 0)
437 perror_with_exit (_("standard output"));
440 static char const * const option_help_msgid[] = {
441 N_("-e --ed Output unmerged changes from OLDFILE to YOURFILE into MYFILE."),
442 N_("-E --show-overlap Output unmerged changes, bracketing conflicts."),
443 N_("-A --show-all Output all changes, bracketing conflicts."),
444 N_("-x --overlap-only Output overlapping changes."),
445 N_("-X Output overlapping changes, bracketing them."),
446 N_("-3 --easy-only Output unmerged nonoverlapping changes."),
448 N_("-m --merge Output merged file instead of ed script (default -A)."),
449 N_("-L LABEL --label=LABEL Use LABEL instead of file name."),
450 N_("-i Append `w' and `q' commands to ed scripts."),
451 N_("-a --text Treat all files as text."),
452 N_("-T --initial-tab Make tabs line up by prepending a tab."),
453 N_("--diff-program=PROGRAM Use PROGRAM to compare files."),
455 N_("-v --version Output version info."),
456 N_("--help Output this help."),
463 char const * const *p;
465 printf (_("Usage: %s [OPTION]... MYFILE OLDFILE YOURFILE\n"),
467 printf ("%s\n\n", _("Compare three files line by line."));
468 for (p = option_help_msgid; *p; p++)
470 printf (" %s\n", _(*p));
473 printf ("\n%s\n\n%s\n",
474 _("If a FILE is `-', read standard input."),
475 _("Report bugs to <bug-gnu-utils@gnu.org>."));
479 * Routines that combine the two diffs together into one. The
480 * algorithm used follows:
482 * File2 is shared in common between the two diffs.
483 * Diff02 is the diff between 0 and 2.
484 * Diff12 is the diff between 1 and 2.
486 * 1) Find the range for the first block in File2.
487 * a) Take the lowest of the two ranges (in File2) in the two
488 * current blocks (one from each diff) as being the low
489 * water mark. Assign the upper end of this block as
490 * being the high water mark and move the current block up
491 * one. Mark the block just moved over as to be used.
492 * b) Check the next block in the diff that the high water
493 * mark is *not* from.
495 * *If* the high water mark is above
496 * the low end of the range in that block,
498 * mark that block as to be used and move the current
499 * block up. Set the high water mark to the max of
500 * the high end of this block and the current. Repeat b.
502 * 2) Find the corresponding ranges in File0 (from the blocks
503 * in diff02; line per line outside of diffs) and in File1.
504 * Create a diff3_block, reserving space as indicated by the ranges.
506 * 3) Copy all of the pointers for file2 in. At least for now,
507 * do memcmp's between corresponding strings in the two diffs.
509 * 4) Copy all of the pointers for file0 and 1 in. Get what you
510 * need from file2 (when there isn't a diff block, it's
511 * identical to file2 within the range between diff blocks).
513 * 5) If the diff blocks you used came from only one of the two
514 * strings of diffs, then that file (i.e. the one other than
515 * the common file in that diff) is the odd person out. If you used
516 * diff blocks from both sets, check to see if files 0 and 1 match:
518 * Same number of lines? If so, do a set of memcmp's (if a
519 * memcmp matches; copy the pointer over; it'll be easier later
520 * if you have to do any compares). If they match, 0 & 1 are
521 * the same. If not, all three different.
523 * Then you do it again, until you run out of blocks.
528 * This routine makes a three way diff (chain of diff3_block's) from two
529 * two way diffs (chains of diff_block's). It is assumed that each of
530 * the two diffs passed are onto the same file (i.e. that each of the
531 * diffs were made "to" the same file). The three way diff pointer
532 * returned will have numbering FILE0--the other file in diff02,
533 * FILE1--the other file in diff12, and FILEC--the common file.
535 static struct diff3_block *
536 make_3way_diff (struct diff_block *thread0, struct diff_block *thread1)
539 * This routine works on the two diffs passed to it as threads.
540 * Thread number 0 is diff02, thread number 1 is diff12. The USING
541 * array is set to the base of the list of blocks to be used to
542 * construct each block of the three way diff; if no blocks from a
543 * particular thread are to be used, that element of the using array
544 * is set to 0. The elements LAST_USING array are set to the last
545 * elements on each of the using lists.
547 * The HIGH_WATER_MARK is set to the highest line number in the common file
548 * described in any of the diffs in either of the USING lists. The
549 * HIGH_WATER_THREAD names the thread. Similarly the BASE_WATER_MARK
550 * and BASE_WATER_THREAD describe the lowest line number in the common file
551 * described in any of the diffs in either of the USING lists. The
552 * HIGH_WATER_DIFF is the diff from which the HIGH_WATER_MARK was
555 * The HIGH_WATER_DIFF should always be equal to LAST_USING
556 * [HIGH_WATER_THREAD]. The OTHER_DIFF is the next diff to check for
557 * higher water, and should always be equal to
558 * CURRENT[HIGH_WATER_THREAD ^ 0x1]. The OTHER_THREAD is the thread
559 * in which the OTHER_DIFF is, and hence should always be equal to
560 * HIGH_WATER_THREAD ^ 0x1.
562 * The variable LAST_DIFF is kept set to the last diff block produced
563 * by this routine, for line correspondence purposes between that diff
564 * and the one currently being worked on. It is initialized to
565 * ZERO_DIFF before any blocks have been created.
568 struct diff_block *using[2];
569 struct diff_block *last_using[2];
570 struct diff_block *current[2];
574 int high_water_thread;
575 int base_water_thread;
578 struct diff_block *high_water_diff;
579 struct diff_block *other_diff;
581 struct diff3_block *result;
582 struct diff3_block *tmpblock;
583 struct diff3_block **result_end;
585 struct diff3_block const *last_diff3;
587 static struct diff3_block const zero_diff3;
591 result_end = &result;
592 current[0] = thread0; current[1] = thread1;
593 last_diff3 = &zero_diff3;
595 /* Sniff up the threads until we reach the end */
597 while (current[0] || current[1])
599 using[0] = using[1] = last_using[0] = last_using[1] = 0;
601 /* Setup low and high water threads, diffs, and marks. */
603 base_water_thread = 1;
604 else if (!current[1])
605 base_water_thread = 0;
608 (D_LOWLINE (current[0], FC) > D_LOWLINE (current[1], FC));
610 high_water_thread = base_water_thread;
612 high_water_diff = current[high_water_thread];
614 high_water_mark = D_HIGHLINE (high_water_diff, FC);
616 /* Make the diff you just got info from into the using class */
617 using[high_water_thread]
618 = last_using[high_water_thread]
620 current[high_water_thread] = high_water_diff->next;
621 last_using[high_water_thread]->next = 0;
623 /* And mark the other diff */
624 other_thread = high_water_thread ^ 0x1;
625 other_diff = current[other_thread];
627 /* Shuffle up the ladder, checking the other diff to see if it
628 needs to be incorporated. */
630 && D_LOWLINE (other_diff, FC) <= high_water_mark + 1)
633 /* Incorporate this diff into the using list. Note that
634 this doesn't take it off the current list */
635 if (using[other_thread])
636 last_using[other_thread]->next = other_diff;
638 using[other_thread] = other_diff;
639 last_using[other_thread] = other_diff;
641 /* Take it off the current list. Note that this following
642 code assumes that other_diff enters it equal to
643 current[high_water_thread ^ 0x1] */
644 current[other_thread] = current[other_thread]->next;
645 other_diff->next = 0;
647 /* Set the high_water stuff
648 If this comparison is equal, then this is the last pass
649 through this loop; since diff blocks within a given
650 thread cannot overlap, the high_water_mark will be
651 *below* the range_start of either of the next diffs. */
653 if (high_water_mark < D_HIGHLINE (other_diff, FC))
655 high_water_thread ^= 1;
656 high_water_diff = other_diff;
657 high_water_mark = D_HIGHLINE (other_diff, FC);
660 /* Set the other diff */
661 other_thread = high_water_thread ^ 0x1;
662 other_diff = current[other_thread];
665 /* The using lists contain a list of all of the blocks to be
666 included in this diff3_block. Create it. */
668 tmpblock = using_to_diff3_block (using, last_using,
669 base_water_thread, high_water_thread,
673 fatal ("internal error: screwup in format of diff blocks");
675 /* Put it on the list. */
676 *result_end = tmpblock;
677 result_end = &tmpblock->next;
679 /* Set up corresponding lines correctly. */
680 last_diff3 = tmpblock;
686 * using_to_diff3_block:
687 * This routine takes two lists of blocks (from two separate diff
688 * threads) and puts them together into one diff3 block.
689 * It then returns a pointer to this diff3 block or 0 for failure.
691 * All arguments besides using are for the convenience of the routine;
692 * they could be derived from the using array.
693 * LAST_USING is a pair of pointers to the last blocks in the using
695 * LOW_THREAD and HIGH_THREAD tell which threads contain the lowest
696 * and highest line numbers for File0.
697 * last_diff3 contains the last diff produced in the calling routine.
698 * This is used for lines mappings which would still be identical to
699 * the state that diff ended in.
701 * A distinction should be made in this routine between the two diffs
702 * that are part of a normal two diff block, and the three diffs that
703 * are part of a diff3_block.
705 static struct diff3_block *
706 using_to_diff3_block (struct diff_block *using[2],
707 struct diff_block *last_using[2],
708 int low_thread, int high_thread,
709 struct diff3_block const *last_diff3)
712 struct diff3_block *result;
713 struct diff_block *ptr;
717 /* Find the range in the common file. */
718 lin lowc = D_LOWLINE (using[low_thread], FC);
719 lin highc = D_HIGHLINE (last_using[high_thread], FC);
721 /* Find the ranges in the other files.
722 If using[d] is null, that means that the file to which that diff
723 refers is equivalent to the common file over this range. */
725 for (d = 0; d < 2; d++)
728 low[d] = D_LOW_MAPLINE (using[d], FC, FO, lowc);
729 high[d] = D_HIGH_MAPLINE (last_using[d], FC, FO, highc);
733 low[d] = D_HIGH_MAPLINE (last_diff3, FILEC, FILE0 + d, lowc);
734 high[d] = D_HIGH_MAPLINE (last_diff3, FILEC, FILE0 + d, highc);
737 /* Create a block with the appropriate sizes */
738 result = create_diff3_block (low[0], high[0], low[1], high[1], lowc, highc);
740 /* Copy information for the common file.
741 Return with a zero if any of the compares failed. */
743 for (d = 0; d < 2; d++)
744 for (ptr = using[d]; ptr; ptr = D_NEXT (ptr))
746 lin result_offset = D_LOWLINE (ptr, FC) - lowc;
748 if (!copy_stringlist (D_LINEARRAY (ptr, FC),
749 D_LENARRAY (ptr, FC),
750 D_LINEARRAY (result, FILEC) + result_offset,
751 D_LENARRAY (result, FILEC) + result_offset,
752 D_NUMLINES (ptr, FC)))
756 /* Copy information for file d. First deal with anything that might be
757 before the first diff. */
759 for (d = 0; d < 2; d++)
761 struct diff_block *u = using[d];
762 lin lo = low[d], hi = high[d];
765 i + lo < (u ? D_LOWLINE (u, FO) : hi + 1);
768 D_RELNUM (result, FILE0 + d, i) = D_RELNUM (result, FILEC, i);
769 D_RELLEN (result, FILE0 + d, i) = D_RELLEN (result, FILEC, i);
772 for (ptr = u; ptr; ptr = D_NEXT (ptr))
774 lin result_offset = D_LOWLINE (ptr, FO) - lo;
777 if (!copy_stringlist (D_LINEARRAY (ptr, FO),
778 D_LENARRAY (ptr, FO),
779 D_LINEARRAY (result, FILE0 + d) + result_offset,
780 D_LENARRAY (result, FILE0 + d) + result_offset,
781 D_NUMLINES (ptr, FO)))
784 /* Catch the lines between here and the next diff */
785 linec = D_HIGHLINE (ptr, FC) + 1 - lowc;
786 for (i = D_HIGHLINE (ptr, FO) + 1 - lo;
787 i < (D_NEXT (ptr) ? D_LOWLINE (D_NEXT (ptr), FO) : hi + 1) - lo;
790 D_RELNUM (result, FILE0 + d, i) = D_RELNUM (result, FILEC, linec);
791 D_RELLEN (result, FILE0 + d, i) = D_RELLEN (result, FILEC, linec);
799 D3_TYPE (result) = DIFF_2ND;
801 D3_TYPE (result) = DIFF_1ST;
804 lin nl0 = D_NUMLINES (result, FILE0);
805 lin nl1 = D_NUMLINES (result, FILE1);
808 || !compare_line_list (D_LINEARRAY (result, FILE0),
809 D_LENARRAY (result, FILE0),
810 D_LINEARRAY (result, FILE1),
811 D_LENARRAY (result, FILE1),
813 D3_TYPE (result) = DIFF_ALL;
815 D3_TYPE (result) = DIFF_3RD;
822 * This routine copies pointers from a list of strings to a different list
823 * of strings. If a spot in the second list is already filled, it
824 * makes sure that it is filled with the same string; if not it
825 * returns 0, the copy incomplete.
826 * Upon successful completion of the copy, it returns 1.
829 copy_stringlist (char * const fromptrs[], size_t const fromlengths[],
830 char *toptrs[], size_t tolengths[],
833 register char * const *f = fromptrs;
834 register char **t = toptrs;
835 register size_t const *fl = fromlengths;
836 register size_t *tl = tolengths;
841 { if (*fl != *tl || memcmp (*f, *t, *fl)) return 0; }
843 { *t = *f ; *tl = *fl; }
845 t++; f++; tl++; fl++;
851 * Create a diff3_block, with ranges as specified in the arguments.
852 * Allocate the arrays for the various pointers (and zero them) based
853 * on the arguments passed. Return the block as a result.
855 static struct diff3_block *
856 create_diff3_block (lin low0, lin high0,
860 struct diff3_block *result = xmalloc (sizeof *result);
863 D3_TYPE (result) = ERROR;
867 D_LOWLINE (result, FILE0) = low0;
868 D_HIGHLINE (result, FILE0) = high0;
869 D_LOWLINE (result, FILE1) = low1;
870 D_HIGHLINE (result, FILE1) = high1;
871 D_LOWLINE (result, FILE2) = low2;
872 D_HIGHLINE (result, FILE2) = high2;
874 /* Allocate and zero space */
875 numlines = D_NUMLINES (result, FILE0);
878 D_LINEARRAY (result, FILE0) = xcalloc (numlines, sizeof (char *));
879 D_LENARRAY (result, FILE0) = xcalloc (numlines, sizeof (size_t));
883 D_LINEARRAY (result, FILE0) = 0;
884 D_LENARRAY (result, FILE0) = 0;
887 numlines = D_NUMLINES (result, FILE1);
890 D_LINEARRAY (result, FILE1) = xcalloc (numlines, sizeof (char *));
891 D_LENARRAY (result, FILE1) = xcalloc (numlines, sizeof (size_t));
895 D_LINEARRAY (result, FILE1) = 0;
896 D_LENARRAY (result, FILE1) = 0;
899 numlines = D_NUMLINES (result, FILE2);
902 D_LINEARRAY (result, FILE2) = xcalloc (numlines, sizeof (char *));
903 D_LENARRAY (result, FILE2) = xcalloc (numlines, sizeof (size_t));
907 D_LINEARRAY (result, FILE2) = 0;
908 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[],
932 if (!*l1 || !*l2 || *lgths1 != *lgths2++
933 || memcmp (*l1++, *l2++, *lgths1++))
939 * Routines to input and parse two way diffs.
942 static struct diff_block *
943 process_diff (char const *filea,
945 struct diff_block **last_block)
952 struct diff_block *block_list, **block_list_end, *bptr;
953 size_t too_many_lines = (PTRDIFF_MAX
954 / MIN (sizeof *bptr->lines[1],
955 sizeof *bptr->lengths[1]));
957 diff_limit = read_diff (filea, fileb, &diff_contents);
958 scan_diff = diff_contents;
959 block_list_end = &block_list;
960 bptr = 0; /* Pacify `gcc -W'. */
962 while (scan_diff < diff_limit)
964 bptr = xmalloc (sizeof *bptr);
965 bptr->lines[0] = bptr->lines[1] = 0;
966 bptr->lengths[0] = bptr->lengths[1] = 0;
968 dt = process_diff_control (&scan_diff, bptr);
969 if (dt == ERROR || *scan_diff != '\n')
971 fprintf (stderr, _("%s: diff failed: "), program_name);
974 putc (*scan_diff, stderr);
976 while (*scan_diff++ != '\n');
981 /* Force appropriate ranges to be null, if necessary */
985 bptr->ranges[0][0]++;
988 bptr->ranges[1][0]++;
993 fatal ("internal error: invalid diff type in process_diff");
997 /* Allocate space for the pointers for the lines from filea, and
998 parcel them out among these pointers */
1001 lin numlines = D_NUMLINES (bptr, 0);
1002 if (too_many_lines <= numlines)
1004 bptr->lines[0] = xmalloc (numlines * sizeof *bptr->lines[0]);
1005 bptr->lengths[0] = xmalloc (numlines * sizeof *bptr->lengths[0]);
1006 for (i = 0; i < numlines; i++)
1007 scan_diff = scan_diff_line (scan_diff,
1008 &(bptr->lines[0][i]),
1009 &(bptr->lengths[0][i]),
1014 /* Get past the separator for changes */
1017 if (strncmp (scan_diff, "---\n", 4))
1018 fatal ("invalid diff format; invalid change separator");
1022 /* Allocate space for the pointers for the lines from fileb, and
1023 parcel them out among these pointers */
1026 lin numlines = D_NUMLINES (bptr, 1);
1027 if (too_many_lines <= numlines)
1029 bptr->lines[1] = xmalloc (numlines * sizeof *bptr->lines[1]);
1030 bptr->lengths[1] = xmalloc (numlines * sizeof *bptr->lengths[1]);
1031 for (i = 0; i < numlines; i++)
1032 scan_diff = scan_diff_line (scan_diff,
1033 &(bptr->lines[1][i]),
1034 &(bptr->lengths[1][i]),
1039 /* Place this block on the blocklist. */
1040 *block_list_end = bptr;
1041 block_list_end = &bptr->next;
1044 *block_list_end = 0;
1050 * This routine will parse a normal format diff control string. It
1051 * returns the type of the diff (ERROR if the format is bad). All of
1052 * the other important information is filled into to the structure
1053 * pointed to by db, and the string pointer (whose location is passed
1054 * to this routine) is updated to point beyond the end of the string
1055 * parsed. Note that only the ranges in the diff_block will be set by
1058 * If some specific pair of numbers has been reduced to a single
1059 * number, then both corresponding numbers in the diff block are set
1060 * to that number. In general these numbers are interpreted as ranges
1061 * inclusive, unless being used by the ADD or DELETE commands. It is
1062 * assumed that these will be special cased in a superior routine.
1065 static enum diff_type
1066 process_diff_control (char **string, struct diff_block *db)
1070 enum diff_type type;
1072 /* These macros are defined here because they can use variables
1073 defined in this function. Don't try this at home kids, we're
1074 trained professionals!
1076 Also note that SKIPWHITE only recognizes tabs and spaces, and
1077 that READNUM can only read positive, integral numbers */
1079 #define SKIPWHITE(s) { while (*s == ' ' || *s == '\t') s++; }
1080 #define READNUM(s, num) \
1081 { unsigned char c = *s; if (!ISDIGIT (c)) return ERROR; holdnum = 0; \
1082 do { holdnum = (c - '0' + holdnum * 10); } \
1083 while (ISDIGIT (c = *++s)); (num) = holdnum; }
1085 /* Read first set of digits */
1087 READNUM (s, db->ranges[0][RANGE_START]);
1089 /* Was that the only digit? */
1093 /* Get the next digit */
1095 READNUM (s, db->ranges[0][RANGE_END]);
1098 db->ranges[0][RANGE_END] = db->ranges[0][RANGE_START];
1100 /* Get the letter */
1114 return ERROR; /* Bad format */
1116 s++; /* Past letter */
1118 /* Read second set of digits */
1120 READNUM (s, db->ranges[1][RANGE_START]);
1122 /* Was that the only digit? */
1126 /* Get the next digit */
1128 READNUM (s, db->ranges[1][RANGE_END]);
1129 SKIPWHITE (s); /* To move to end */
1132 db->ranges[1][RANGE_END] = db->ranges[1][RANGE_START];
1139 read_diff (char const *filea,
1141 char **output_placement)
1144 size_t current_chunk_size, total;
1147 struct stat pipestat;
1149 #if HAVE_WORKING_FORK || HAVE_WORKING_VFORK
1151 char const *argv[8];
1157 *ap++ = diff_program;
1160 *ap++ = "--horizon-lines=100";
1166 if (pipe (fds) != 0)
1167 perror_with_exit ("pipe");
1174 if (fds[1] != STDOUT_FILENO)
1176 dup2 (fds[1], STDOUT_FILENO);
1180 /* The cast to (char **) is needed for portability to older
1181 hosts with a nonstandard prototype for execvp. */
1182 execvp (diff_program, (char **) argv);
1184 _exit (errno == ENOEXEC ? 126 : 127);
1188 perror_with_exit ("fork");
1190 close (fds[1]); /* Prevent erroneous lack of EOF */
1196 char const args[] = " -a --horizon-lines=100 -- ";
1197 char *command = xmalloc (quote_system_arg (0, diff_program)
1199 + quote_system_arg (0, filea) + 1
1200 + quote_system_arg (0, fileb) + 1);
1202 p += quote_system_arg (p, diff_program);
1203 strcpy (p, args + (text ? 0 : 3));
1205 p += quote_system_arg (p, filea);
1207 p += quote_system_arg (p, fileb);
1210 fpipe = popen (command, "r");
1212 perror_with_exit (command);
1214 fd = fileno (fpipe);
1218 if (fstat (fd, &pipestat) != 0)
1219 perror_with_exit ("fstat");
1220 current_chunk_size = MAX (1, STAT_BLOCKSIZE (pipestat));
1221 diff_result = xmalloc (current_chunk_size);
1226 size_t bytes_to_read = current_chunk_size - total;
1227 size_t bytes = block_read (fd, diff_result + total, bytes_to_read);
1229 if (bytes != bytes_to_read)
1231 if (bytes == SIZE_MAX)
1232 perror_with_exit (_("read failed"));
1235 if (PTRDIFF_MAX / 2 <= current_chunk_size)
1237 current_chunk_size *= 2;
1238 diff_result = xrealloc (diff_result, current_chunk_size);
1241 if (total != 0 && diff_result[total-1] != '\n')
1242 fatal ("invalid diff format; incomplete last line");
1244 *output_placement = diff_result;
1246 #if ! (HAVE_WORKING_FORK || HAVE_WORKING_VFORK)
1248 wstatus = pclose (fpipe);
1254 if (close (fd) != 0)
1255 perror_with_exit ("close");
1256 if (waitpid (pid, &wstatus, 0) < 0)
1257 perror_with_exit ("waitpid");
1261 if (! werrno && WIFEXITED (wstatus))
1262 switch (WEXITSTATUS (wstatus))
1265 error (EXIT_TROUBLE, 0, _("subsidiary program `%s' not executable"),
1268 error (EXIT_TROUBLE, 0, _("subsidiary program `%s' not found"),
1271 if (werrno || ! (WIFEXITED (wstatus) && WEXITSTATUS (wstatus) < 2))
1272 error (EXIT_TROUBLE, werrno, _("subsidiary program `%s' failed"),
1275 return diff_result + total;
1280 * Scan a regular diff line (consisting of > or <, followed by a
1281 * space, followed by text (including nulls) up to a newline.
1283 * This next routine began life as a macro and many parameters in it
1284 * are used as call-by-reference values.
1287 scan_diff_line (char *scan_ptr, char **set_start, size_t *set_length,
1288 char *limit, char leadingchar)
1292 if (!(scan_ptr[0] == leadingchar
1293 && scan_ptr[1] == ' '))
1294 fatal ("invalid diff format; incorrect leading line chars");
1296 *set_start = line_ptr = scan_ptr + 2;
1297 while (*line_ptr++ != '\n')
1300 /* Include newline if the original line ended in a newline,
1301 or if an edit script is being generated.
1302 Copy any missing newline message to stderr if an edit script is being
1303 generated, because edit scripts cannot handle missing newlines.
1304 Return the beginning of the next line. */
1305 *set_length = line_ptr - *set_start;
1306 if (line_ptr < limit && *line_ptr == '\\')
1309 fprintf (stderr, "%s:", program_name);
1316 putc (*line_ptr, stderr);
1318 while (*line_ptr++ != '\n');
1325 * This routine outputs a three way diff passed as a list of
1327 * The argument MAPPING is indexed by external file number (in the
1328 * argument list) and contains the internal file number (from the
1329 * diff passed). This is important because the user expects his
1330 * outputs in terms of the argument list number, and the diff passed
1331 * may have been done slightly differently (if the last argument
1332 * was "-", for example).
1333 * REV_MAPPING is the inverse of MAPPING.
1336 output_diff3 (FILE *outputfile, struct diff3_block *diff,
1337 int const mapping[3], int const rev_mapping[3])
1342 struct diff3_block *ptr;
1346 static int skew_increment[3] = { 2, 3, 1 }; /* 0==>2==>1==>3 */
1347 char const *line_prefix = initial_tab ? "\t" : " ";
1349 for (ptr = diff; ptr; ptr = D_NEXT (ptr))
1353 switch (ptr->correspond)
1357 dontprint = 3; /* Print them all */
1358 oddoneout = 3; /* Nobody's odder than anyone else */
1363 oddoneout = rev_mapping[ptr->correspond - DIFF_1ST];
1365 x[0] = oddoneout + '1';
1367 dontprint = oddoneout == 0;
1370 fatal ("internal error: invalid diff type passed to output");
1372 fprintf (outputfile, "====%s\n", x);
1374 /* Go 0, 2, 1 if the first and third outputs are equivalent. */
1376 i = (oddoneout == 1 ? skew_increment[i] : i + 1))
1378 int realfile = mapping[i];
1379 lin lowt = D_LOWLINE (ptr, realfile);
1380 lin hight = D_HIGHLINE (ptr, realfile);
1382 long lhight = hight;
1384 fprintf (outputfile, "%d:", i + 1);
1385 switch (lowt - hight)
1388 fprintf (outputfile, "%lda\n", llowt - 1);
1391 fprintf (outputfile, "%ldc\n", llowt);
1394 fprintf (outputfile, "%ld,%ldc\n", llowt, lhight);
1398 if (i == dontprint) continue;
1405 fprintf (outputfile, line_prefix);
1406 cp = D_RELNUM (ptr, realfile, line);
1407 length = D_RELLEN (ptr, realfile, line);
1408 fwrite (cp, sizeof (char), length, outputfile);
1410 while (++line < hight - lowt + 1);
1411 if (cp[length - 1] != '\n')
1412 fprintf (outputfile, "\n\\ %s\n",
1413 _("No newline at end of file"));
1421 * Output to OUTPUTFILE the lines of B taken from FILENUM.
1422 * Double any initial '.'s; yield nonzero if any initial '.'s were doubled.
1425 dotlines (FILE *outputfile, struct diff3_block *b, int filenum)
1428 bool leading_dot = 0;
1431 i < D_NUMLINES (b, filenum);
1434 char *line = D_RELNUM (b, filenum, i);
1438 fprintf (outputfile, ".");
1440 fwrite (line, sizeof (char),
1441 D_RELLEN (b, filenum, i), outputfile);
1448 * Output to OUTPUTFILE a '.' line. If LEADING_DOT is nonzero,
1449 * also output a command that removes initial '.'s
1450 * starting with line START and continuing for NUM lines.
1451 * (START is long, not lin, for convenience with printf %ld formats.)
1454 undotlines (FILE *outputfile, bool leading_dot, long start, lin num)
1456 fprintf (outputfile, ".\n");
1460 fprintf (outputfile, "%lds/^\\.//\n", start);
1462 fprintf (outputfile, "%ld,%lds/^\\.//\n", start, start + num - 1);
1467 * This routine outputs a diff3 set of blocks as an ed script. This
1468 * script applies the changes between file's 2 & 3 to file 1. It
1469 * takes the precise format of the ed script to be output from global
1470 * variables set during options processing. Note that it does
1471 * destructive things to the set of diff3 blocks it is passed; it
1472 * reverses their order (this gets around the problems involved with
1473 * changing line numbers in an ed script).
1475 * Note that this routine has the same problem of mapping as the last
1476 * one did; the variable MAPPING maps from file number according to
1477 * the argument list to file number according to the diff passed. All
1478 * files listed below are in terms of the argument list.
1479 * REV_MAPPING is the inverse of MAPPING.
1481 * The arguments FILE0, FILE1 and FILE2 are the strings to print
1482 * as the names of the three files. These may be the actual names,
1483 * or may be the arguments specified with -L.
1485 * Returns 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 = 0, conflict;
1495 struct diff3_block *b;
1497 for (b = reverse_diff3_blocklist (diff); b; b = b->next)
1499 /* Must do mapping correctly. */
1501 = (b->correspond == DIFF_ALL
1503 : DIFF_1ST + rev_mapping[b->correspond - DIFF_1ST]);
1507 /* If we aren't supposed to do this output block, skip it. */
1511 case DIFF_2ND: if (!show_2nd) continue; conflict = 1; break;
1512 case DIFF_3RD: if (overlap_only) continue; conflict = 0; break;
1513 case DIFF_ALL: if (simple_only) continue; conflict = flagging; break;
1516 low0 = D_LOWLINE (b, mapping[FILE0]);
1517 high0 = D_HIGHLINE (b, mapping[FILE0]);
1521 conflicts_found = 1;
1524 /* Mark end of conflict. */
1526 fprintf (outputfile, "%lda\n", high0);
1528 if (type == DIFF_ALL)
1532 /* Append lines from FILE1. */
1533 fprintf (outputfile, "||||||| %s\n", file1);
1534 leading_dot = dotlines (outputfile, b, mapping[FILE1]);
1536 /* Append lines from FILE2. */
1537 fprintf (outputfile, "=======\n");
1538 leading_dot |= dotlines (outputfile, b, mapping[FILE2]);
1540 fprintf (outputfile, ">>>>>>> %s\n", file2);
1541 undotlines (outputfile, leading_dot, high0 + 2,
1542 (D_NUMLINES (b, mapping[FILE1])
1543 + D_NUMLINES (b, mapping[FILE2]) + 1));
1546 /* Mark start of conflict. */
1548 fprintf (outputfile, "%lda\n<<<<<<< %s\n", low0 - 1,
1549 type == DIFF_ALL ? file0 : file1);
1551 if (type == DIFF_2ND)
1553 /* Prepend lines from FILE1. */
1554 leading_dot = dotlines (outputfile, b, mapping[FILE1]);
1555 fprintf (outputfile, "=======\n");
1557 undotlines (outputfile, leading_dot, low0 + 1,
1558 D_NUMLINES (b, mapping[FILE1]));
1560 else if (D_NUMLINES (b, mapping[FILE2]) == 0)
1561 /* Write out a delete */
1564 fprintf (outputfile, "%ldd\n", low0);
1566 fprintf (outputfile, "%ld,%ldd\n", low0, high0);
1569 /* Write out an add or change */
1571 switch (high0 - low0)
1574 fprintf (outputfile, "%lda\n", high0);
1577 fprintf (outputfile, "%ldc\n", high0);
1580 fprintf (outputfile, "%ld,%ldc\n", low0, high0);
1584 undotlines (outputfile, dotlines (outputfile, b, mapping[FILE2]),
1585 low0, D_NUMLINES (b, mapping[FILE2]));
1588 if (finalwrite) fprintf (outputfile, "w\nq\n");
1589 return conflicts_found;
1593 * Read from INFILE and output to OUTPUTFILE a set of diff3_ blocks DIFF
1594 * as a merged file. This acts like 'ed file0 <[output_diff3_edscript]',
1595 * except that it works even for binary data or incomplete lines.
1597 * As before, MAPPING maps from arg list file number to diff file number,
1598 * REV_MAPPING is its inverse,
1599 * and FILE0, FILE1, and FILE2 are the names of the files.
1601 * Returns 1 if conflicts were found.
1605 output_diff3_merge (FILE *infile, FILE *outputfile, struct diff3_block *diff,
1606 int const mapping[3], int const rev_mapping[3],
1607 char const *file0, char const *file1, char const *file2)
1611 bool conflicts_found = 0, conflict;
1612 struct diff3_block *b;
1615 for (b = diff; b; b = b->next)
1617 /* Must do mapping correctly. */
1619 = ((b->correspond == DIFF_ALL)
1621 : DIFF_1ST + rev_mapping[b->correspond - DIFF_1ST]);
1622 char const *format_2nd = "<<<<<<< %s\n";
1624 /* If we aren't supposed to do this output block, skip it. */
1628 case DIFF_2ND: if (!show_2nd) continue; conflict = 1; break;
1629 case DIFF_3RD: if (overlap_only) continue; conflict = 0; break;
1630 case DIFF_ALL: if (simple_only) continue; conflict = flagging;
1631 format_2nd = "||||||| %s\n";
1635 /* Copy I lines from file 0. */
1636 i = D_LOWLINE (b, FILE0) - linesread - 1;
1644 if (ferror (infile))
1645 perror_with_exit (_("read failed"));
1646 else if (feof (infile))
1647 fatal ("input file shrank");
1649 putc (c, outputfile);
1655 conflicts_found = 1;
1657 if (type == DIFF_ALL)
1659 /* Put in lines from FILE0 with bracket. */
1660 fprintf (outputfile, "<<<<<<< %s\n", file0);
1662 i < D_NUMLINES (b, mapping[FILE0]);
1664 fwrite (D_RELNUM (b, mapping[FILE0], i), sizeof (char),
1665 D_RELLEN (b, mapping[FILE0], i), outputfile);
1670 /* Put in lines from FILE1 with bracket. */
1671 fprintf (outputfile, format_2nd, file1);
1673 i < D_NUMLINES (b, mapping[FILE1]);
1675 fwrite (D_RELNUM (b, mapping[FILE1], i), sizeof (char),
1676 D_RELLEN (b, mapping[FILE1], i), outputfile);
1679 fprintf (outputfile, "=======\n");
1682 /* Put in lines from FILE2. */
1684 i < D_NUMLINES (b, mapping[FILE2]);
1686 fwrite (D_RELNUM (b, mapping[FILE2], i), sizeof (char),
1687 D_RELLEN (b, mapping[FILE2], i), outputfile);
1690 fprintf (outputfile, ">>>>>>> %s\n", file2);
1692 /* Skip I lines in file 0. */
1693 i = D_NUMLINES (b, FILE0);
1696 while ((c = getc (infile)) != '\n')
1699 if (ferror (infile))
1700 perror_with_exit (_("read failed"));
1701 else if (feof (infile))
1704 fatal ("input file shrank");
1705 return conflicts_found;
1709 /* Copy rest of common file. */
1710 while ((c = getc (infile)) != EOF || !(ferror (infile) | feof (infile)))
1711 putc (c, outputfile);
1712 return conflicts_found;
1716 * Reverse the order of the list of diff3 blocks.
1718 static struct diff3_block *
1719 reverse_diff3_blocklist (struct diff3_block *diff)
1721 register struct diff3_block *tmp, *next, *prev;
1723 for (tmp = diff, prev = 0; tmp; tmp = next)
1734 fatal (char const *msgid)
1736 error (EXIT_TROUBLE, 0, "%s", _(msgid));
1741 perror_with_exit (char const *string)
1743 error (EXIT_TROUBLE, errno, "%s", string);