xref: /dragonfly/contrib/diffutils/src/diff3.c (revision 25a2db75)
1 /* diff3 - compare three files line by line
2 
3    Copyright (C) 1988-1989, 1992-1996, 1998, 2001-2002, 2004, 2006, 2009-2013
4    Free Software Foundation, Inc.
5 
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.
10 
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.
15 
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/>.  */
18 
19 #include "system.h"
20 #include "paths.h"
21 
22 #include <stdio.h>
23 #include <unlocked-io.h>
24 
25 #include <c-stack.h>
26 #include <cmpbuf.h>
27 #include <error.h>
28 #include <exitfail.h>
29 #include <file-type.h>
30 #include <getopt.h>
31 #include <progname.h>
32 #include <system-quote.h>
33 #include <version-etc.h>
34 #include <xalloc.h>
35 #include <xfreopen.h>
36 
37 /* The official name of this program (e.g., no 'g' prefix).  */
38 #define PROGRAM_NAME "diff3"
39 
40 #define AUTHORS \
41   proper_name ("Randy Smith")
42 
43 /* Internal data structures and macros for the diff3 program; includes
44    data structures for both diff3 diffs and normal diffs.  */
45 
46 /* Different files within a three way diff.  */
47 #define	FILE0	0
48 #define	FILE1	1
49 #define	FILE2	2
50 
51 /* A three way diff is built from two two-way diffs; the file which
52    the two two-way diffs share is:  */
53 #define	FILEC	FILE2
54 
55 /* Different files within a two way diff.
56    FC is the common file, FO the other file.  */
57 #define FO 0
58 #define FC 1
59 
60 /* The ranges are indexed by */
61 #define	RANGE_START	0
62 #define	RANGE_END	1
63 
64 enum diff_type {
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 */
73 };
74 
75 /* Two way diff */
76 struct diff_block {
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;
81 };
82 
83 /* Three way diff */
84 
85 struct diff3_block {
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;
91 };
92 
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)
100 
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])
108 
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])
114 
115 /* Next block.  */
116 #define	D_NEXT(diff)	((diff)->next)
117 
118 /* Access the type of a diff3 block.  */
119 #define	D3_TYPE(diff)	((diff)->correspond)
120 
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)	\
124   ((linenum)						\
125    - D_HIGHLINE ((diff), (fromfile))			\
126    + D_HIGHLINE ((diff), (tofile)))
127 
128 #define	D_LOW_MAPLINE(diff, fromfile, tofile, linenum)	\
129   ((linenum)						\
130    - D_LOWLINE ((diff), (fromfile))			\
131    + D_LOWLINE ((diff), (tofile)))
132 
133 /* Options variables for flags set on command line.  */
134 
135 /* If nonzero, treat all files as text files, never as binary.  */
136 static bool text;
137 
138 /* Remove trailing carriage returns from input.  */
139 static bool strip_trailing_cr;
140 
141 /* If nonzero, write out an ed script instead of the standard diff3 format.  */
142 static bool edscript;
143 
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;
148 
149 /* Use a tab to align output lines (-T).  */
150 static bool initial_tab;
151 
152 /* If nonzero, do not output information for overlapping diffs.  */
153 static bool simple_only;
154 
155 /* If nonzero, do not output information for non-overlapping diffs.  */
156 static bool overlap_only;
157 
158 /* If nonzero, show information for DIFF_2ND diffs.  */
159 static bool show_2nd;
160 
161 /* If nonzero, include ':wq' at the end of the script
162    to write out the file being edited.   */
163 static bool finalwrite;
164 
165 /* If nonzero, output a merged file.  */
166 static bool merge;
167 
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);
186 
187 static char const *diff_program = DEFAULT_DIFF_PROGRAM;
188 
189 /* Values for long options that do not have single-letter equivalents.  */
190 enum
191 {
192   DIFF_PROGRAM_OPTION = CHAR_MAX + 1,
193   HELP_OPTION,
194   STRIP_TRAILING_CR_OPTION
195 };
196 
197 static struct option const longopts[] =
198 {
199   {"diff-program", 1, 0, DIFF_PROGRAM_OPTION},
200   {"easy-only", 0, 0, '3'},
201   {"ed", 0, 0, 'e'},
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},
210   {"text", 0, 0, 'a'},
211   {"version", 0, 0, 'v'},
212   {0, 0, 0, 0}
213 };
214 
215 int
216 main (int argc, char **argv)
217 {
218   int c, i;
219   int common;
220   int mapping[3];
221   int rev_mapping[3];
222   int incompat = 0;
223   bool conflicts_found;
224   struct diff_block *thread0, *thread1, *last_block;
225   struct diff3_block *diff3;
226   int tag_count = 0;
227   char *tag_strings[3];
228   char *commonname;
229   char **file;
230   struct stat statb;
231 
232   exit_failure = EXIT_TROUBLE;
233   initialize_main (&argc, &argv);
234   set_program_name (argv[0]);
235   setlocale (LC_ALL, "");
236   textdomain (PACKAGE);
237   c_stack_action (0);
238 
239   while ((c = getopt_long (argc, argv, "aeimvx3AEL:TX", longopts, 0)) != -1)
240     {
241       switch (c)
242 	{
243 	case 'a':
244 	  text = true;
245 	  break;
246 	case 'A':
247 	  show_2nd = true;
248 	  flagging = true;
249 	  incompat++;
250 	  break;
251 	case 'x':
252 	  overlap_only = true;
253 	  incompat++;
254 	  break;
255 	case '3':
256 	  simple_only = true;
257 	  incompat++;
258 	  break;
259 	case 'i':
260 	  finalwrite = true;
261 	  break;
262 	case 'm':
263 	  merge = true;
264 	  break;
265 	case 'X':
266 	  overlap_only = true;
267 	  /* Fall through.  */
268 	case 'E':
269 	  flagging = true;
270 	  /* Fall through.  */
271 	case 'e':
272 	  incompat++;
273 	  break;
274 	case 'T':
275 	  initial_tab = true;
276 	  break;
277 	case STRIP_TRAILING_CR_OPTION:
278 	  strip_trailing_cr = true;
279 	  break;
280 	case 'v':
281 	  version_etc (stdout, PROGRAM_NAME, PACKAGE_NAME, Version,
282 		       AUTHORS, (char *) NULL);
283 	  check_stdout ();
284 	  return EXIT_SUCCESS;
285 	case DIFF_PROGRAM_OPTION:
286 	  diff_program = optarg;
287 	  break;
288 	case HELP_OPTION:
289 	  usage ();
290 	  check_stdout ();
291 	  return EXIT_SUCCESS;
292 	case 'L':
293 	  /* Handle up to three -L options.  */
294 	  if (tag_count < 3)
295 	    {
296 	      tag_strings[tag_count++] = optarg;
297 	      break;
298 	    }
299 	  try_help ("too many file label options", 0);
300 	default:
301 	  try_help (0, 0);
302 	}
303     }
304 
305   edscript = incompat & ~merge;  /* -AeExX3 without -m implies ed script.  */
306   show_2nd |= ~incompat & merge;  /* -m without -AeExX3 implies -A.  */
307   flagging |= ~incompat & merge;
308 
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);
313 
314   if (argc - optind != 3)
315     {
316       if (argc - optind < 3)
317 	try_help ("missing operand after '%s'", argv[argc - 1]);
318       else
319 	try_help ("extra operand '%s'", argv[optind + 3]);
320     }
321 
322   file = &argv[optind];
323 
324   for (i = tag_count; i < 3; i++)
325     tag_strings[i] = file[i];
326 
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.
333 
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.
337 
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.  */
342 
343   common = 2 - (edscript | merge);
344 
345   if (STREQ (file[common], "-"))
346     {
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
349 	 file instead.  */
350       common = 3 - common;
351       if (STREQ (file[0], "-") || STREQ (file[common], "-"))
352 	fatal ("'-' specified for more than one input file");
353     }
354 
355   mapping[0] = 0;
356   mapping[1] = 3 - common;
357   mapping[2] = common;
358 
359   for (i = 0; i < 3; i++)
360     rev_mapping[mapping[i]] = i;
361 
362   for (i = 0; i < 3; i++)
363     if (! STREQ (file[i], "-"))
364       {
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]);
369       }
370 
371 #ifdef SIGCHLD
372   /* System V fork+wait does not work if SIGCHLD is ignored.  */
373   signal (SIGCHLD, SIG_DFL);
374 #endif
375 
376   /* Invoke diff twice on two pairs of input files, combine the two
377      diffs, and output them.  */
378 
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);
383   if (edscript)
384     conflicts_found
385       = output_diff3_edscript (stdout, diff3, mapping, rev_mapping,
386 			       tag_strings[0], tag_strings[1], tag_strings[2]);
387   else if (merge)
388     {
389       xfreopen (file[rev_mapping[FILE0]], "r", stdin);
390       conflicts_found
391 	= output_diff3_merge (stdin, stdout, diff3, mapping, rev_mapping,
392 			      tag_strings[0], tag_strings[1], tag_strings[2]);
393       if (ferror (stdin))
394 	fatal ("read failed");
395     }
396   else
397     {
398       output_diff3 (stdout, diff3, mapping, rev_mapping);
399       conflicts_found = false;
400     }
401 
402   check_stdout ();
403   exit (conflicts_found);
404   return conflicts_found;
405 }
406 
407 static void
408 try_help (char const *reason_msgid, char const *operand)
409 {
410   if (reason_msgid)
411     error (0, 0, _(reason_msgid), operand);
412   error (EXIT_TROUBLE, 0,
413 	 _("Try '%s --help' for more information."), program_name);
414   abort ();
415 }
416 
417 static void
418 check_stdout (void)
419 {
420   if (ferror (stdout))
421     fatal ("write failed");
422   else if (fclose (stdout) != 0)
423     perror_with_exit (_("standard output"));
424 }
425 
426 static char const * const option_help_msgid[] = {
427   N_("-A, --show-all              output all changes, bracketing conflicts"),
428   "",
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"),
436   "",
437   N_("-m, --merge                 output actual merged file, according to\n"
438      "                                -A if no other options are given"),
439   "",
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)"),
446   "",
447   N_("    --help                  display this help and exit"),
448   N_("-v, --version               output version information and exit"),
449   0
450 };
451 
452 static void
453 usage (void)
454 {
455   char const * const *p;
456 
457   printf (_("Usage: %s [OPTION]... MYFILE OLDFILE YOURFILE\n"),
458 	  program_name);
459   printf ("%s\n\n", _("Compare three files line by line."));
460 
461   fputs (_("\
462 Mandatory arguments to long options are mandatory for short options too.\n\
463 "), stdout);
464   for (p = option_help_msgid;  *p;  p++)
465     if (**p)
466       printf ("  %s\n", _(*p));
467     else
468       putchar ('\n');
469   fputs (_("\n\
470 The default output format is a somewhat human-readable representation of\n\
471 the changes.\n\
472 \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\
475 \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 ();
483 }
484 
485 /* Combine the two diffs together into one.
486    Here is the algorithm:
487 
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.
491 
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
499 	       mark is *not* from.
500 
501 	       *If* the high water mark is above
502 	       the low end of the range in that block,
503 
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.
507 
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.
511 
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.
514 
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).
518 
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
523 	    0 and 1 match:
524 
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.
529 
530      Then do it again, until the blocks are exhausted.  */
531 
532 
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.  */
539 
540 static struct diff3_block *
541 make_3way_diff (struct diff_block *thread0, struct diff_block *thread1)
542 {
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.
549 
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.
557 
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.
564 
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.  */
569 
570   struct diff_block *using[2];
571   struct diff_block *last_using[2];
572   struct diff_block *current[2];
573 
574   lin high_water_mark;
575 
576   int high_water_thread;
577   int base_water_thread;
578   int other_thread;
579 
580   struct diff_block *high_water_diff;
581   struct diff_block *other_diff;
582 
583   struct diff3_block *result;
584   struct diff3_block *tmpblock;
585   struct diff3_block **result_end;
586 
587   struct diff3_block const *last_diff3;
588 
589   static struct diff3_block const zero_diff3;
590 
591   /* Initialization */
592   result = 0;
593   result_end = &result;
594   current[0] = thread0; current[1] = thread1;
595   last_diff3 = &zero_diff3;
596 
597   /* Sniff up the threads until we reach the end */
598 
599   while (current[0] || current[1])
600     {
601       using[0] = using[1] = last_using[0] = last_using[1] = 0;
602 
603       /* Setup low and high water threads, diffs, and marks.  */
604       if (!current[0])
605 	base_water_thread = 1;
606       else if (!current[1])
607 	base_water_thread = 0;
608       else
609 	base_water_thread =
610 	  (D_LOWLINE (current[0], FC) > D_LOWLINE (current[1], FC));
611 
612       high_water_thread = base_water_thread;
613 
614       high_water_diff = current[high_water_thread];
615 
616       high_water_mark = D_HIGHLINE (high_water_diff, FC);
617 
618       /* Make the diff you just got info from into the using class */
619       using[high_water_thread]
620 	= last_using[high_water_thread]
621 	= high_water_diff;
622       current[high_water_thread] = high_water_diff->next;
623       last_using[high_water_thread]->next = 0;
624 
625       /* And mark the other diff */
626       other_thread = high_water_thread ^ 0x1;
627       other_diff = current[other_thread];
628 
629       /* Shuffle up the ladder, checking the other diff to see if it
630 	 needs to be incorporated.  */
631       while (other_diff
632 	     && D_LOWLINE (other_diff, FC) <= high_water_mark + 1)
633 	{
634 
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;
639 	  else
640 	    using[other_thread] = other_diff;
641 	  last_using[other_thread] = other_diff;
642 
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;
648 
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.  */
654 
655 	  if (high_water_mark < D_HIGHLINE (other_diff, FC))
656 	    {
657 	      high_water_thread ^= 1;
658 	      high_water_mark = D_HIGHLINE (other_diff, FC);
659 	    }
660 
661 	  /* Set the other diff */
662 	  other_thread = high_water_thread ^ 0x1;
663 	  other_diff = current[other_thread];
664 	}
665 
666       /* The using lists contain a list of all of the blocks to be
667 	 included in this diff3_block.  Create it.  */
668 
669       tmpblock = using_to_diff3_block (using, last_using,
670 				       base_water_thread, high_water_thread,
671 				       last_diff3);
672 
673       if (!tmpblock)
674 	fatal ("internal error: screwup in format of diff blocks");
675 
676       /* Put it on the list.  */
677       *result_end = tmpblock;
678       result_end = &tmpblock->next;
679 
680       /* Set up corresponding lines correctly.  */
681       last_diff3 = tmpblock;
682     }
683   return result;
684 }
685 
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.
689 
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.
697 
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.  */
701 
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)
707 {
708   lin low[2], high[2];
709   struct diff3_block *result;
710   struct diff_block *ptr;
711   int d;
712   lin i;
713 
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);
717 
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.  */
721 
722   for (d = 0; d < 2; d++)
723     if (using[d])
724       {
725 	low[d] = D_LOW_MAPLINE (using[d], FC, FO, lowc);
726 	high[d] = D_HIGH_MAPLINE (last_using[d], FC, FO, highc);
727       }
728     else
729       {
730 	low[d] = D_HIGH_MAPLINE (last_diff3, FILEC, FILE0 + d, lowc);
731 	high[d] = D_HIGH_MAPLINE (last_diff3, FILEC, FILE0 + d, highc);
732       }
733 
734   /* Create a block with the appropriate sizes */
735   result = create_diff3_block (low[0], high[0], low[1], high[1], lowc, highc);
736 
737   /* Copy information for the common file.
738      Return with a zero if any of the compares failed.  */
739 
740   for (d = 0; d < 2; d++)
741     for (ptr = using[d]; ptr; ptr = D_NEXT (ptr))
742       {
743 	lin result_offset = D_LOWLINE (ptr, FC) - lowc;
744 
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)))
750 	  return 0;
751       }
752 
753   /* Copy information for file d.  First deal with anything that might be
754      before the first diff.  */
755 
756   for (d = 0; d < 2; d++)
757     {
758       struct diff_block *u = using[d];
759       lin lo = low[d], hi = high[d];
760 
761       for (i = 0;
762 	   i + lo < (u ? D_LOWLINE (u, FO) : hi + 1);
763 	   i++)
764 	{
765 	  D_RELNUM (result, FILE0 + d, i) = D_RELNUM (result, FILEC, i);
766 	  D_RELLEN (result, FILE0 + d, i) = D_RELLEN (result, FILEC, i);
767 	}
768 
769       for (ptr = u; ptr; ptr = D_NEXT (ptr))
770 	{
771 	  lin result_offset = D_LOWLINE (ptr, FO) - lo;
772 	  lin linec;
773 
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)))
779 	    return 0;
780 
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;
785 	       i++)
786 	    {
787 	      D_RELNUM (result, FILE0 + d, i) = D_RELNUM (result, FILEC, linec);
788 	      D_RELLEN (result, FILE0 + d, i) = D_RELLEN (result, FILEC, linec);
789 	      linec++;
790 	    }
791 	}
792     }
793 
794   /* Set correspond */
795   if (!using[0])
796     D3_TYPE (result) = DIFF_2ND;
797   else if (!using[1])
798     D3_TYPE (result) = DIFF_1ST;
799   else
800     {
801       lin nl0 = D_NUMLINES (result, FILE0);
802       lin nl1 = D_NUMLINES (result, FILE1);
803 
804       if (nl0 != nl1
805 	  || !compare_line_list (D_LINEARRAY (result, FILE0),
806 				 D_LENARRAY (result, FILE0),
807 				 D_LINEARRAY (result, FILE1),
808 				 D_LENARRAY (result, FILE1),
809 				 nl0))
810 	D3_TYPE (result) = DIFF_ALL;
811       else
812 	D3_TYPE (result) = DIFF_3RD;
813     }
814 
815   return result;
816 }
817 
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.  */
822 
823 static bool
824 copy_stringlist (char * const fromptrs[], size_t const fromlengths[],
825 		 char *toptrs[], size_t tolengths[],
826 		 lin copynum)
827 {
828   register char * const *f = fromptrs;
829   register char **t = toptrs;
830   register size_t const *fl = fromlengths;
831   register size_t *tl = tolengths;
832 
833   while (copynum--)
834     {
835       if (*t)
836 	{
837 	  if (*fl != *tl || memcmp (*f, *t, *fl) != 0)
838 	    return false;
839 	}
840       else
841 	{
842 	  *t = *f;
843 	  *tl = *fl;
844 	}
845 
846       t++; f++; tl++; fl++;
847     }
848 
849   return true;
850 }
851 
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.  */
855 
856 static struct diff3_block *
857 create_diff3_block (lin low0, lin high0,
858 		    lin low1, lin high1,
859 		    lin low2, lin high2)
860 {
861   struct diff3_block *result = xmalloc (sizeof *result);
862   lin numlines;
863 
864   D3_TYPE (result) = ERROR;
865   D_NEXT (result) = 0;
866 
867   /* Assign ranges */
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;
874 
875   /* Allocate and zero space */
876   numlines = D_NUMLINES (result, FILE0);
877   if (numlines)
878     {
879       D_LINEARRAY (result, FILE0) = xcalloc (numlines, sizeof (char *));
880       D_LENARRAY (result, FILE0) = xcalloc (numlines, sizeof (size_t));
881     }
882   else
883     {
884       D_LINEARRAY (result, FILE0) = 0;
885       D_LENARRAY (result, FILE0) = 0;
886     }
887 
888   numlines = D_NUMLINES (result, FILE1);
889   if (numlines)
890     {
891       D_LINEARRAY (result, FILE1) = xcalloc (numlines, sizeof (char *));
892       D_LENARRAY (result, FILE1) = xcalloc (numlines, sizeof (size_t));
893     }
894   else
895     {
896       D_LINEARRAY (result, FILE1) = 0;
897       D_LENARRAY (result, FILE1) = 0;
898     }
899 
900   numlines = D_NUMLINES (result, FILE2);
901   if (numlines)
902     {
903       D_LINEARRAY (result, FILE2) = xcalloc (numlines, sizeof (char *));
904       D_LENARRAY (result, FILE2) = xcalloc (numlines, sizeof (size_t));
905     }
906   else
907     {
908       D_LINEARRAY (result, FILE2) = 0;
909       D_LENARRAY (result, FILE2) = 0;
910     }
911 
912   /* Return */
913   return result;
914 }
915 
916 /* Compare two lists of lines of text.
917    Return 1 if they are equivalent, 0 if not.  */
918 
919 static bool
920 compare_line_list (char * const list1[], size_t const lengths1[],
921 		   char * const list2[], size_t const lengths2[],
922 		   lin nl)
923 {
924   char * const *l1 = list1;
925   char * const *l2 = list2;
926   size_t const *lgths1 = lengths1;
927   size_t const *lgths2 = lengths2;
928 
929   while (nl--)
930     if (!*l1 || !*l2 || *lgths1 != *lgths2++
931 	|| memcmp (*l1++, *l2++, *lgths1++) != 0)
932       return false;
933   return true;
934 }
935 
936 /* Input and parse two way diffs.  */
937 
938 static struct diff_block *
939 process_diff (char const *filea,
940 	      char const *fileb,
941 	      struct diff_block **last_block)
942 {
943   char *diff_contents;
944   char *diff_limit;
945   char *scan_diff;
946   enum diff_type dt;
947   lin i;
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]));
954 
955   diff_limit = read_diff (filea, fileb, &diff_contents);
956   scan_diff = diff_contents;
957 
958   while (scan_diff < diff_limit)
959     {
960       bptr = xmalloc (sizeof *bptr);
961       bptr->lines[0] = bptr->lines[1] = 0;
962       bptr->lengths[0] = bptr->lengths[1] = 0;
963 
964       dt = process_diff_control (&scan_diff, bptr);
965       if (dt == ERROR || *scan_diff != '\n')
966 	{
967 	  fprintf (stderr, _("%s: diff failed: "), program_name);
968 	  do
969 	    {
970 	      putc (*scan_diff, stderr);
971 	    }
972 	  while (*scan_diff++ != '\n');
973 	  exit (EXIT_TROUBLE);
974 	}
975       scan_diff++;
976 
977       /* Force appropriate ranges to be null, if necessary */
978       switch (dt)
979 	{
980 	case ADD:
981 	  bptr->ranges[0][0]++;
982 	  break;
983 	case DELETE:
984 	  bptr->ranges[1][0]++;
985 	  break;
986 	case CHANGE:
987 	  break;
988 	default:
989 	  fatal ("internal error: invalid diff type in process_diff");
990 	  break;
991 	}
992 
993       /* Allocate space for the pointers for the lines from filea, and
994 	 parcel them out among these pointers */
995       if (dt != ADD)
996 	{
997 	  lin numlines = D_NUMLINES (bptr, 0);
998 	  if (too_many_lines <= numlines)
999 	    xalloc_die ();
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]),
1006 					diff_limit,
1007 					'<');
1008 	}
1009 
1010       /* Get past the separator for changes */
1011       if (dt == CHANGE)
1012 	{
1013 	  if (strncmp (scan_diff, "---\n", 4))
1014 	    fatal ("invalid diff format; invalid change separator");
1015 	  scan_diff += 4;
1016 	}
1017 
1018       /* Allocate space for the pointers for the lines from fileb, and
1019 	 parcel them out among these pointers */
1020       if (dt != DELETE)
1021 	{
1022 	  lin numlines = D_NUMLINES (bptr, 1);
1023 	  if (too_many_lines <= numlines)
1024 	    xalloc_die ();
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]),
1031 					diff_limit,
1032 					'>');
1033 	}
1034 
1035       /* Place this block on the blocklist.  */
1036       *block_list_end = bptr;
1037       block_list_end = &bptr->next;
1038     }
1039 
1040   *block_list_end = NULL;
1041   *last_block = bptr;
1042   return block_list;
1043 }
1044 
1045 /* Skip tabs and spaces, and return the first character after them.  */
1046 
1047 static char * _GL_ATTRIBUTE_PURE
1048 skipwhite (char *s)
1049 {
1050   while (*s == ' ' || *s == '\t')
1051     s++;
1052   return s;
1053 }
1054 
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.  */
1058 
1059 static char *
1060 readnum (char *s, lin *pnum)
1061 {
1062   unsigned char c = *s;
1063   lin num = 0;
1064 
1065   if (! ISDIGIT (c))
1066     return 0;
1067 
1068   do
1069     {
1070       num = c - '0' + num * 10;
1071       c = *++s;
1072     }
1073   while (ISDIGIT (c));
1074 
1075   *pnum = num;
1076   return s;
1077 }
1078 
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.
1085 
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.   */
1091 
1092 static enum diff_type
1093 process_diff_control (char **string, struct diff_block *db)
1094 {
1095   char *s = *string;
1096   enum diff_type type;
1097 
1098   /* Read first set of digits */
1099   s = readnum (skipwhite (s), &db->ranges[0][RANGE_START]);
1100   if (! s)
1101     return ERROR;
1102 
1103   /* Was that the only digit? */
1104   s = skipwhite (s);
1105   if (*s == ',')
1106     {
1107       s = readnum (s + 1, &db->ranges[0][RANGE_END]);
1108       if (! s)
1109 	return ERROR;
1110     }
1111   else
1112     db->ranges[0][RANGE_END] = db->ranges[0][RANGE_START];
1113 
1114   /* Get the letter */
1115   s = skipwhite (s);
1116   switch (*s)
1117     {
1118     case 'a':
1119       type = ADD;
1120       break;
1121     case 'c':
1122       type = CHANGE;
1123       break;
1124     case 'd':
1125       type = DELETE;
1126       break;
1127     default:
1128       return ERROR;			/* Bad format */
1129     }
1130   s++;				/* Past letter */
1131 
1132   /* Read second set of digits */
1133   s = readnum (skipwhite (s), &db->ranges[1][RANGE_START]);
1134   if (! s)
1135     return ERROR;
1136 
1137   /* Was that the only digit? */
1138   s = skipwhite (s);
1139   if (*s == ',')
1140     {
1141       s = readnum (s + 1, &db->ranges[1][RANGE_END]);
1142       if (! s)
1143 	return ERROR;
1144       s = skipwhite (s);		/* To move to end */
1145     }
1146   else
1147     db->ranges[1][RANGE_END] = db->ranges[1][RANGE_START];
1148 
1149   *string = s;
1150   return type;
1151 }
1152 
1153 static char *
1154 read_diff (char const *filea,
1155 	   char const *fileb,
1156 	   char **output_placement)
1157 {
1158   char *diff_result;
1159   size_t current_chunk_size, total;
1160   int fd, wstatus, status;
1161   int werrno = 0;
1162   struct stat pipestat;
1163   char const *argv[9];
1164   char const **ap;
1165 #if HAVE_WORKING_FORK
1166   int fds[2];
1167   pid_t pid;
1168 #else
1169   FILE *fpipe;
1170   char *command;
1171 #endif
1172 
1173   ap = argv;
1174   *ap++ = diff_program;
1175   if (text)
1176     *ap++ = "-a";
1177   if (strip_trailing_cr)
1178     *ap++ = "--strip-trailing-cr";
1179   *ap++ = "--horizon-lines=100";
1180   *ap++ = "--";
1181   *ap++ = filea;
1182   *ap++ = fileb;
1183   *ap = 0;
1184 
1185 #if HAVE_WORKING_FORK
1186 
1187   if (pipe (fds) != 0)
1188     perror_with_exit ("pipe");
1189 
1190   pid = fork ();
1191   if (pid == 0)
1192     {
1193       /* Child */
1194       close (fds[0]);
1195       if (fds[1] != STDOUT_FILENO)
1196 	{
1197 	  dup2 (fds[1], STDOUT_FILENO);
1198 	  close (fds[1]);
1199 	}
1200 
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);
1204 
1205       _exit (errno == ENOENT ? 127 : 126);
1206     }
1207 
1208   if (pid == -1)
1209     perror_with_exit ("fork");
1210 
1211   close (fds[1]);		/* Prevent erroneous lack of EOF */
1212   fd = fds[0];
1213 
1214 #else
1215 
1216   command = system_quote_argv (SCI_SYSTEM, (char **) argv);
1217   errno = 0;
1218   fpipe = popen (command, "r");
1219   if (!fpipe)
1220     perror_with_exit (command);
1221   free (command);
1222   fd = fileno (fpipe);
1223 
1224 #endif
1225 
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);
1230   total = 0;
1231 
1232   for (;;)
1233     {
1234       size_t bytes_to_read = current_chunk_size - total;
1235       size_t bytes = block_read (fd, diff_result + total, bytes_to_read);
1236       total += bytes;
1237       if (bytes != bytes_to_read)
1238 	{
1239 	  if (bytes == SIZE_MAX)
1240 	    perror_with_exit (_("read failed"));
1241 	  break;
1242 	}
1243       if (PTRDIFF_MAX / 2 <= current_chunk_size)
1244 	xalloc_die ();
1245       current_chunk_size *= 2;
1246       diff_result = xrealloc (diff_result, current_chunk_size);
1247     }
1248 
1249   if (total != 0 && diff_result[total-1] != '\n')
1250     fatal ("invalid diff format; incomplete last line");
1251 
1252   *output_placement = diff_result;
1253 
1254 #if ! HAVE_WORKING_FORK
1255 
1256   wstatus = pclose (fpipe);
1257   if (wstatus == -1)
1258     werrno = errno;
1259 
1260 #else
1261 
1262   if (close (fd) != 0)
1263     perror_with_exit ("close");
1264   if (waitpid (pid, &wstatus, 0) < 0)
1265     perror_with_exit ("waitpid");
1266 
1267 #endif
1268 
1269   status = ! werrno && WIFEXITED (wstatus) ? WEXITSTATUS (wstatus) : INT_MAX;
1270 
1271   if (EXIT_TROUBLE <= status)
1272     error (EXIT_TROUBLE, werrno,
1273 	   _(status == 126
1274 	     ? "subsidiary program '%s' could not be invoked"
1275 	     : status == 127
1276 	     ? "subsidiary program '%s' not found"
1277 	     : status == INT_MAX
1278 	     ? "subsidiary program '%s' failed"
1279 	     : "subsidiary program '%s' failed (exit status %d)"),
1280 	   diff_program, status);
1281 
1282   return diff_result + total;
1283 }
1284 
1285 
1286 /* Scan a regular diff line (consisting of > or <, followed by a
1287    space, followed by text (including nulls) up to a newline.
1288 
1289    This next routine began life as a macro and many parameters in it
1290    are used as call-by-reference values.  */
1291 static char *
1292 scan_diff_line (char *scan_ptr, char **set_start, size_t *set_length,
1293 		char *limit, char leadingchar)
1294 {
1295   char *line_ptr;
1296 
1297   if (!(scan_ptr[0] == leadingchar
1298 	&& scan_ptr[1] == ' '))
1299     fatal ("invalid diff format; incorrect leading line chars");
1300 
1301   *set_start = line_ptr = scan_ptr + 2;
1302   while (*line_ptr++ != '\n')
1303     continue;
1304 
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 == '\\')
1312     {
1313       if (edscript)
1314 	fprintf (stderr, "%s:", program_name);
1315       else
1316 	--*set_length;
1317       line_ptr++;
1318       do
1319 	{
1320 	  if (edscript)
1321 	    putc (*line_ptr, stderr);
1322 	}
1323       while (*line_ptr++ != '\n');
1324     }
1325 
1326   return line_ptr;
1327 }
1328 
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.  */
1336 
1337 static void
1338 output_diff3 (FILE *outputfile, struct diff3_block *diff,
1339 	      int const mapping[3], int const rev_mapping[3])
1340 {
1341   int i;
1342   int oddoneout;
1343   char *cp;
1344   struct diff3_block *ptr;
1345   lin line;
1346   size_t length;
1347   int dontprint;
1348   static int skew_increment[3] = { 2, 3, 1 }; /* 0==>2==>1==>3 */
1349   char const *line_prefix = initial_tab ? "\t" : "  ";
1350 
1351   for (ptr = diff; ptr; ptr = D_NEXT (ptr))
1352     {
1353       char x[2];
1354 
1355       switch (ptr->correspond)
1356 	{
1357 	case DIFF_ALL:
1358 	  x[0] = 0;
1359 	  dontprint = 3;	/* Print them all */
1360 	  oddoneout = 3;	/* Nobody's odder than anyone else */
1361 	  break;
1362 	case DIFF_1ST:
1363 	case DIFF_2ND:
1364 	case DIFF_3RD:
1365 	  oddoneout = rev_mapping[ptr->correspond - DIFF_1ST];
1366 
1367 	  x[0] = oddoneout + '1';
1368 	  x[1] = 0;
1369 	  dontprint = oddoneout == 0;
1370 	  break;
1371 	default:
1372 	  fatal ("internal error: invalid diff type passed to output");
1373 	}
1374       fprintf (outputfile, "====%s\n", x);
1375 
1376       /* Go 0, 2, 1 if the first and third outputs are equivalent.  */
1377       for (i = 0; i < 3;
1378 	   i = (oddoneout == 1 ? skew_increment[i] : i + 1))
1379 	{
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;
1385 
1386 	  fprintf (outputfile, "%d:", i + 1);
1387 	  switch (lowt - hight)
1388 	    {
1389 	    case 1:
1390 	      fprintf (outputfile, "%lda\n", llowt - 1);
1391 	      break;
1392 	    case 0:
1393 	      fprintf (outputfile, "%ldc\n", llowt);
1394 	      break;
1395 	    default:
1396 	      fprintf (outputfile, "%ld,%ldc\n", llowt, lhight);
1397 	      break;
1398 	    }
1399 
1400 	  if (i == dontprint) continue;
1401 
1402 	  if (lowt <= hight)
1403 	    {
1404 	      line = 0;
1405 	      do
1406 		{
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);
1411 		}
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"));
1416 	    }
1417 	}
1418     }
1419 }
1420 
1421 
1422 /* Output to OUTPUTFILE the lines of B taken from FILENUM.  Double any
1423    initial '.'s; yield nonzero if any initial '.'s were doubled.  */
1424 
1425 static bool
1426 dotlines (FILE *outputfile, struct diff3_block *b, int filenum)
1427 {
1428   lin i;
1429   bool leading_dot = false;
1430 
1431   for (i = 0;
1432        i < D_NUMLINES (b, filenum);
1433        i++)
1434     {
1435       char *line = D_RELNUM (b, filenum, i);
1436       if (line[0] == '.')
1437 	{
1438 	  leading_dot = true;
1439 	  fputc ('.', outputfile);
1440 	}
1441       fwrite (line, sizeof (char),
1442 	      D_RELLEN (b, filenum, i), outputfile);
1443     }
1444 
1445   return leading_dot;
1446 }
1447 
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.)  */
1452 
1453 static void
1454 undotlines (FILE *outputfile, bool leading_dot, long int start, lin num)
1455 {
1456   fputs (".\n", outputfile);
1457   if (leading_dot)
1458     {
1459       if (num == 1)
1460 	fprintf (outputfile, "%lds/^\\.//\n", start);
1461       else
1462 	fprintf (outputfile, "%ld,%lds/^\\.//\n", start, start + num - 1);
1463     }
1464 }
1465 
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
1472    script.
1473 
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.
1478 
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.
1482 
1483    Return 1 if conflicts were found.  */
1484 
1485 static bool
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)
1489 {
1490   bool leading_dot;
1491   bool conflicts_found = false;
1492   bool conflict;
1493   struct diff3_block *b;
1494 
1495   for (b = reverse_diff3_blocklist (diff); b; b = b->next)
1496     {
1497       /* Must do mapping correctly.  */
1498       enum diff_type type
1499 	= (b->correspond == DIFF_ALL
1500 	   ? DIFF_ALL
1501 	   : DIFF_1ST + rev_mapping[b->correspond - DIFF_1ST]);
1502 
1503       long int low0, high0;
1504 
1505       /* If we aren't supposed to do this output block, skip it.  */
1506       switch (type)
1507 	{
1508 	default: continue;
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;
1512 	}
1513 
1514       low0 = D_LOWLINE (b, mapping[FILE0]);
1515       high0 = D_HIGHLINE (b, mapping[FILE0]);
1516 
1517       if (conflict)
1518 	{
1519 	  conflicts_found = true;
1520 
1521 
1522 	  /* Mark end of conflict.  */
1523 
1524 	  fprintf (outputfile, "%lda\n", high0);
1525 	  leading_dot = false;
1526 	  if (type == DIFF_ALL)
1527 	    {
1528 	      if (show_2nd)
1529 		{
1530 		  /* Append lines from FILE1.  */
1531 		  fprintf (outputfile, "||||||| %s\n", file1);
1532 		  leading_dot = dotlines (outputfile, b, mapping[FILE1]);
1533 		}
1534 	      /* Append lines from FILE2.  */
1535 	      fputs ("=======\n", outputfile);
1536 	      leading_dot |= dotlines (outputfile, b, mapping[FILE2]);
1537 	    }
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));
1542 
1543 
1544 	  /* Mark start of conflict.  */
1545 
1546 	  fprintf (outputfile, "%lda\n<<<<<<< %s\n", low0 - 1,
1547 		   type == DIFF_ALL ? file0 : file1);
1548 	  leading_dot = false;
1549 	  if (type == DIFF_2ND)
1550 	    {
1551 	      /* Prepend lines from FILE1.  */
1552 	      leading_dot = dotlines (outputfile, b, mapping[FILE1]);
1553 	      fputs ("=======\n", outputfile);
1554 	    }
1555 	  undotlines (outputfile, leading_dot, low0 + 1,
1556 		      D_NUMLINES (b, mapping[FILE1]));
1557 	}
1558       else if (D_NUMLINES (b, mapping[FILE2]) == 0)
1559 	/* Write out a delete */
1560 	{
1561 	  if (low0 == high0)
1562 	    fprintf (outputfile, "%ldd\n", low0);
1563 	  else
1564 	    fprintf (outputfile, "%ld,%ldd\n", low0, high0);
1565 	}
1566       else
1567 	/* Write out an add or change */
1568 	{
1569 	  switch (high0 - low0)
1570 	    {
1571 	    case -1:
1572 	      fprintf (outputfile, "%lda\n", high0);
1573 	      break;
1574 	    case 0:
1575 	      fprintf (outputfile, "%ldc\n", high0);
1576 	      break;
1577 	    default:
1578 	      fprintf (outputfile, "%ld,%ldc\n", low0, high0);
1579 	      break;
1580 	    }
1581 
1582 	  undotlines (outputfile, dotlines (outputfile, b, mapping[FILE2]),
1583 		      low0, D_NUMLINES (b, mapping[FILE2]));
1584 	}
1585     }
1586   if (finalwrite)
1587     fputs ("w\nq\n", outputfile);
1588   return conflicts_found;
1589 }
1590 
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.
1595 
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.
1599 
1600    Return 1 if conflicts were found.  */
1601 
1602 static bool
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)
1606 {
1607   int c;
1608   lin i;
1609   bool conflicts_found = false;
1610   bool conflict;
1611   struct diff3_block *b;
1612   lin linesread = 0;
1613 
1614   for (b = diff; b; b = b->next)
1615     {
1616       /* Must do mapping correctly.  */
1617       enum diff_type type
1618 	= ((b->correspond == DIFF_ALL)
1619 	   ? DIFF_ALL
1620 	   : DIFF_1ST + rev_mapping[b->correspond - DIFF_1ST]);
1621       char const *format_2nd = "<<<<<<< %s\n";
1622 
1623       /* If we aren't supposed to do this output block, skip it.  */
1624       switch (type)
1625 	{
1626 	default: continue;
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";
1631 	  break;
1632 	}
1633 
1634       /* Copy I lines from file 0.  */
1635       i = D_LOWLINE (b, FILE0) - linesread - 1;
1636       linesread += i;
1637       while (0 <= --i)
1638 	do
1639 	  {
1640 	    c = getc (infile);
1641 	    if (c == EOF)
1642 	      {
1643 		if (ferror (infile))
1644 		  perror_with_exit (_("read failed"));
1645 		else if (feof (infile))
1646 		  fatal ("input file shrank");
1647 	      }
1648 	    putc (c, outputfile);
1649 	  }
1650 	while (c != '\n');
1651 
1652       if (conflict)
1653 	{
1654 	  conflicts_found = true;
1655 
1656 	  if (type == DIFF_ALL)
1657 	    {
1658 	      /* Put in lines from FILE0 with bracket.  */
1659 	      fprintf (outputfile, "<<<<<<< %s\n", file0);
1660 	      for (i = 0;
1661 		   i < D_NUMLINES (b, mapping[FILE0]);
1662 		   i++)
1663 		fwrite (D_RELNUM (b, mapping[FILE0], i), sizeof (char),
1664 			D_RELLEN (b, mapping[FILE0], i), outputfile);
1665 	    }
1666 
1667 	  if (show_2nd)
1668 	    {
1669 	      /* Put in lines from FILE1 with bracket.  */
1670 	      fprintf (outputfile, format_2nd, file1);
1671 	      for (i = 0;
1672 		   i < D_NUMLINES (b, mapping[FILE1]);
1673 		   i++)
1674 		fwrite (D_RELNUM (b, mapping[FILE1], i), sizeof (char),
1675 			D_RELLEN (b, mapping[FILE1], i), outputfile);
1676 	    }
1677 
1678 	  fputs ("=======\n", outputfile);
1679 	}
1680 
1681       /* Put in lines from FILE2.  */
1682       for (i = 0;
1683 	   i < D_NUMLINES (b, mapping[FILE2]);
1684 	   i++)
1685 	fwrite (D_RELNUM (b, mapping[FILE2], i), sizeof (char),
1686 		D_RELLEN (b, mapping[FILE2], i), outputfile);
1687 
1688       if (conflict)
1689 	fprintf (outputfile, ">>>>>>> %s\n", file2);
1690 
1691       /* Skip I lines in file 0.  */
1692       i = D_NUMLINES (b, FILE0);
1693       linesread += i;
1694       while (0 <= --i)
1695 	while ((c = getc (infile)) != '\n')
1696 	  if (c == EOF)
1697 	    {
1698 	      if (ferror (infile))
1699 		perror_with_exit (_("read failed"));
1700 	      else if (feof (infile))
1701 		{
1702 		  if (i || b->next)
1703 		    fatal ("input file shrank");
1704 		  return conflicts_found;
1705 		}
1706 	    }
1707     }
1708   /* Copy rest of common file.  */
1709   while ((c = getc (infile)) != EOF || !(ferror (infile) | feof (infile)))
1710     putc (c, outputfile);
1711   return conflicts_found;
1712 }
1713 
1714 /* Reverse the order of the list of diff3 blocks.  */
1715 
1716 static struct diff3_block *
1717 reverse_diff3_blocklist (struct diff3_block *diff)
1718 {
1719   register struct diff3_block *tmp, *next, *prev;
1720 
1721   for (tmp = diff, prev = 0;  tmp;  tmp = next)
1722     {
1723       next = tmp->next;
1724       tmp->next = prev;
1725       prev = tmp;
1726     }
1727 
1728   return prev;
1729 }
1730 
1731 static void
1732 fatal (char const *msgid)
1733 {
1734   error (EXIT_TROUBLE, 0, "%s", _(msgid));
1735   abort ();
1736 }
1737 
1738 static void
1739 perror_with_exit (char const *string)
1740 {
1741   error (EXIT_TROUBLE, errno, "%s", string);
1742   abort ();
1743 }
1744