contrib/diffutils/src/diff3.c

   1 /* diff3 - compare three files line by line
   2
   3    Copyright (C) 1988-1989, 1992-1996, 1998, 2001-2002, 2004, 2006, 2009-2010
   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 \f
  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 <inttostr.h>
  32 #include <progname.h>
  33 #include <sh-quote.h>
  34 #include <version-etc.h>
  35 #include <xalloc.h>
  36 #include <xfreopen.h>
  37
  38 /* The official name of this program (e.g., no `g' prefix).  */
  39 #define PROGRAM_NAME "diff3"
  40
  41 #define AUTHORS \
  42   proper_name ("Randy Smith")
  43
  44 /* Internal data structures and macros for the diff3 program; includes
  45    data structures for both diff3 diffs and normal diffs.  */
  46
  47 /* Different files within a three way diff.  */
  48 #define FILE0   0
  49 #define FILE1   1
  50 #define FILE2   2
  51
  52 /* A three way diff is built from two two-way diffs; the file which
  53    the two two-way diffs share is:  */
  54 #define FILEC   FILE2
  55
  56 /* Different files within a two way diff.
  57    FC is the common file, FO the other file.  */
  58 #define FO 0
  59 #define FC 1
  60
  61 /* The ranges are indexed by */
  62 #define RANGE_START     0
  63 #define RANGE_END       1
  64
  65 enum diff_type {
  66   ERROR,                        /* Should not be used */
  67   ADD,                          /* Two way diff add */
  68   CHANGE,                       /* Two way diff change */
  69   DELETE,                       /* Two way diff delete */
  70   DIFF_ALL,                     /* All three are different */
  71   DIFF_1ST,                     /* Only the first is different */
  72   DIFF_2ND,                     /* Only the second */
  73   DIFF_3RD                      /* Only the third */
  74 };
  75
  76 /* Two way diff */
  77 struct diff_block {
  78   lin ranges[2][2];             /* Ranges are inclusive */
  79   char **lines[2];              /* The actual lines (may contain nulls) */
  80   size_t *lengths[2];           /* Line lengths (including newlines, if any) */
  81   struct diff_block *next;
  82 };
  83
  84 /* Three way diff */
  85
  86 struct diff3_block {
  87   enum diff_type correspond;    /* Type of diff */
  88   lin ranges[3][2];             /* Ranges are inclusive */
  89   char **lines[3];              /* The actual lines (may contain nulls) */
  90   size_t *lengths[3];           /* Line lengths (including newlines, if any) */
  91   struct diff3_block *next;
  92 };
  93
  94 /* Access the ranges on a diff block.  */
  95 #define D_LOWLINE(diff, filenum)        \
  96   ((diff)->ranges[filenum][RANGE_START])
  97 #define D_HIGHLINE(diff, filenum)       \
  98   ((diff)->ranges[filenum][RANGE_END])
  99 #define D_NUMLINES(diff, filenum)       \
 100   (D_HIGHLINE (diff, filenum) - D_LOWLINE (diff, filenum) + 1)
 101
 102 /* Access the line numbers in a file in a diff by relative line
 103    numbers (i.e. line number within the diff itself).  Note that these
 104    are lvalues and can be used for assignment.  */
 105 #define D_RELNUM(diff, filenum, linenum)        \
 106   ((diff)->lines[filenum][linenum])
 107 #define D_RELLEN(diff, filenum, linenum)        \
 108   ((diff)->lengths[filenum][linenum])
 109
 110 /* And get at them directly, when that should be necessary.  */
 111 #define D_LINEARRAY(diff, filenum)      \
 112   ((diff)->lines[filenum])
 113 #define D_LENARRAY(diff, filenum)       \
 114   ((diff)->lengths[filenum])
 115
 116 /* Next block.  */
 117 #define D_NEXT(diff)    ((diff)->next)
 118
 119 /* Access the type of a diff3 block.  */
 120 #define D3_TYPE(diff)   ((diff)->correspond)
 121
 122 /* Line mappings based on diffs.  The first maps off the top of the
 123    diff, the second off of the bottom.  */
 124 #define D_HIGH_MAPLINE(diff, fromfile, tofile, linenum) \
 125   ((linenum)                                            \
 126    - D_HIGHLINE ((diff), (fromfile))                    \
 127    + D_HIGHLINE ((diff), (tofile)))
 128
 129 #define D_LOW_MAPLINE(diff, fromfile, tofile, linenum)  \
 130   ((linenum)                                            \
 131    - D_LOWLINE ((diff), (fromfile))                     \
 132    + D_LOWLINE ((diff), (tofile)))
 133 \f
 134 /* Options variables for flags set on command line.  */
 135
 136 /* If nonzero, treat all files as text files, never as binary.  */
 137 static bool text;
 138
 139 /* Remove trailing carriage returns from input.  */
 140 static bool strip_trailing_cr;
 141
 142 /* If nonzero, write out an ed script instead of the standard diff3 format.  */
 143 static bool edscript;
 144
 145 /* If nonzero, in the case of overlapping diffs (type DIFF_ALL),
 146    preserve the lines which would normally be deleted from
 147    file 1 with a special flagging mechanism.  */
 148 static bool flagging;
 149
 150 /* Use a tab to align output lines (-T).  */
 151 static bool initial_tab;
 152
 153 /* If nonzero, do not output information for overlapping diffs.  */
 154 static bool simple_only;
 155
 156 /* If nonzero, do not output information for non-overlapping diffs.  */
 157 static bool overlap_only;
 158
 159 /* If nonzero, show information for DIFF_2ND diffs.  */
 160 static bool show_2nd;
 161
 162 /* If nonzero, include `:wq' at the end of the script
 163    to write out the file being edited.   */
 164 static bool finalwrite;
 165
 166 /* If nonzero, output a merged file.  */
 167 static bool merge;
 168
 169 static char *read_diff (char const *, char const *, char **);
 170 static char *scan_diff_line (char *, char **, size_t *, char *, char);
 171 static enum diff_type process_diff_control (char **, struct diff_block *);
 172 static bool compare_line_list (char * const[], size_t const[], char * const[], size_t const[], lin);
 173 static bool copy_stringlist (char * const[], size_t const[], char *[], size_t[], lin);
 174 static bool output_diff3_edscript (FILE *, struct diff3_block *, int const[3], int const[3], char const *, char const *, char const *);
 175 static bool output_diff3_merge (FILE *, FILE *, struct diff3_block *, int const[3], int const[3], char const *, char const *, char const *);
 176 static struct diff3_block *create_diff3_block (lin, lin, lin, lin, lin, lin);
 177 static struct diff3_block *make_3way_diff (struct diff_block *, struct diff_block *);
 178 static struct diff3_block *reverse_diff3_blocklist (struct diff3_block *);
 179 static struct diff3_block *using_to_diff3_block (struct diff_block *[2], struct diff_block *[2], int, int, struct diff3_block const *);
 180 static struct diff_block *process_diff (char const *, char const *, struct diff_block **);
 181 static void check_stdout (void);
 182 static void fatal (char const *) __attribute__((noreturn));
 183 static void output_diff3 (FILE *, struct diff3_block *, int const[3], int const[3]);
 184 static void perror_with_exit (char const *) __attribute__((noreturn));
 185 static void try_help (char const *, char const *) __attribute__((noreturn));
 186 static void usage (void);
 187
 188 static char const *diff_program = DEFAULT_DIFF_PROGRAM;
 189
 190 /* Values for long options that do not have single-letter equivalents.  */
 191 enum
 192 {
 193   DIFF_PROGRAM_OPTION = CHAR_MAX + 1,
 194   HELP_OPTION,
 195   STRIP_TRAILING_CR_OPTION
 196 };
 197
 198 static struct option const longopts[] =
 199 {
 200   {"diff-program", 1, 0, DIFF_PROGRAM_OPTION},
 201   {"easy-only", 0, 0, '3'},
 202   {"ed", 0, 0, 'e'},
 203   {"help", 0, 0, HELP_OPTION},
 204   {"initial-tab", 0, 0, 'T'},
 205   {"label", 1, 0, 'L'},
 206   {"merge", 0, 0, 'm'},
 207   {"overlap-only", 0, 0, 'x'},
 208   {"show-all", 0, 0, 'A'},
 209   {"show-overlap", 0, 0, 'E'},
 210   {"strip-trailing-cr", 0, 0, STRIP_TRAILING_CR_OPTION},
 211   {"text", 0, 0, 'a'},
 212   {"version", 0, 0, 'v'},
 213   {0, 0, 0, 0}
 214 };
 215
 216 int
 217 main (int argc, char **argv)
 218 {
 219   int c, i;
 220   int common;
 221   int mapping[3];
 222   int rev_mapping[3];
 223   int incompat = 0;
 224   bool conflicts_found;
 225   struct diff_block *thread0, *thread1, *last_block;
 226   struct diff3_block *diff3;
 227   int tag_count = 0;
 228   char *tag_strings[3];
 229   char *commonname;
 230   char **file;
 231   struct stat statb;
 232
 233   exit_failure = EXIT_TROUBLE;
 234   initialize_main (&argc, &argv);
 235   set_program_name (argv[0]);
 236   setlocale (LC_ALL, "");
 237   bindtextdomain (PACKAGE, LOCALEDIR);
 238   textdomain (PACKAGE);
 239   c_stack_action (0);
 240
 241   while ((c = getopt_long (argc, argv, "aeimvx3AEL:TX", longopts, 0)) != -1)
 242     {
 243       switch (c)
 244         {
 245         case 'a':
 246           text = true;
 247           break;
 248         case 'A':
 249           show_2nd = true;
 250           flagging = true;
 251           incompat++;
 252           break;
 253         case 'x':
 254           overlap_only = true;
 255           incompat++;
 256           break;
 257         case '3':
 258           simple_only = true;
 259           incompat++;
 260           break;
 261         case 'i':
 262           finalwrite = true;
 263           break;
 264         case 'm':
 265           merge = true;
 266           break;
 267         case 'X':
 268           overlap_only = true;
 269           /* Fall through.  */
 270         case 'E':
 271           flagging = true;
 272           /* Fall through.  */
 273         case 'e':
 274           incompat++;
 275           break;
 276         case 'T':
 277           initial_tab = true;
 278           break;
 279         case STRIP_TRAILING_CR_OPTION:
 280           strip_trailing_cr = true;
 281           break;
 282         case 'v':
 283           version_etc (stdout, PROGRAM_NAME, PACKAGE_NAME, PACKAGE_VERSION,
 284                        AUTHORS, (char *) NULL);
 285           check_stdout ();
 286           return EXIT_SUCCESS;
 287         case DIFF_PROGRAM_OPTION:
 288           diff_program = optarg;
 289           break;
 290         case HELP_OPTION:
 291           usage ();
 292           check_stdout ();
 293           return EXIT_SUCCESS;
 294         case 'L':
 295           /* Handle up to three -L options.  */
 296           if (tag_count < 3)
 297             {
 298               tag_strings[tag_count++] = optarg;
 299               break;
 300             }
 301           try_help ("too many file label options", 0);
 302         default:
 303           try_help (0, 0);
 304         }
 305     }
 306
 307   edscript = incompat & ~merge;  /* -AeExX3 without -m implies ed script.  */
 308   show_2nd |= ~incompat & merge;  /* -m without -AeExX3 implies -A.  */
 309   flagging |= ~incompat & merge;
 310
 311   if (incompat > 1  /* Ensure at most one of -AeExX3.  */
 312       || finalwrite & merge /* -i -m would rewrite input file.  */
 313       || (tag_count && ! flagging)) /* -L requires one of -AEX.  */
 314     try_help ("incompatible options", 0);
 315
 316   if (argc - optind != 3)
 317     {
 318       if (argc - optind < 3)
 319         try_help ("missing operand after `%s'", argv[argc - 1]);
 320       else
 321         try_help ("extra operand `%s'", argv[optind + 3]);
 322     }
 323
 324   file = &argv[optind];
 325
 326   for (i = tag_count; i < 3; i++)
 327     tag_strings[i] = file[i];
 328
 329   /* Always compare file1 to file2, even if file2 is "-".
 330      This is needed for -mAeExX3.  Using the file0 as
 331      the common file would produce wrong results, because if the
 332      file0-file1 diffs didn't line up with the file0-file2 diffs
 333      (which is entirely possible since we don't use diff's -n option),
 334      diff3 might report phantom changes from file1 to file2.
 335
 336      Also, try to compare file0 to file1, because this is where
 337      changes are expected to come from.  Diffing between these pairs
 338      of files is more likely to avoid phantom changes from file0 to file1.
 339
 340      Historically, the default common file was file2, so some older
 341      applications (e.g. Emacs ediff) used file2 as the ancestor.  So,
 342      for compatibility, if this is a 3-way diff (not a merge or
 343      edscript), prefer file2 as the common file.  */
 344
 345   common = 2 - (edscript | merge);
 346
 347   if (STREQ (file[common], "-"))
 348     {
 349       /* Sigh.  We've got standard input as the common file.  We can't
 350          call diff twice on stdin.  Use the other arg as the common
 351          file instead.  */
 352       common = 3 - common;
 353       if (STREQ (file[0], "-") || STREQ (file[common], "-"))
 354         fatal ("`-' specified for more than one input file");
 355     }
 356
 357   mapping[0] = 0;
 358   mapping[1] = 3 - common;
 359   mapping[2] = common;
 360
 361   for (i = 0; i < 3; i++)
 362     rev_mapping[mapping[i]] = i;
 363
 364   for (i = 0; i < 3; i++)
 365     if (strcmp (file[i], "-") != 0)
 366       {
 367         if (stat (file[i], &statb) < 0)
 368           perror_with_exit (file[i]);
 369         else if (S_ISDIR (statb.st_mode))
 370           error (EXIT_TROUBLE, EISDIR, "%s", file[i]);
 371       }
 372
 373 #ifdef SIGCHLD
 374   /* System V fork+wait does not work if SIGCHLD is ignored.  */
 375   signal (SIGCHLD, SIG_DFL);
 376 #endif
 377
 378   /* Invoke diff twice on two pairs of input files, combine the two
 379      diffs, and output them.  */
 380
 381   commonname = file[rev_mapping[FILEC]];
 382   thread1 = process_diff (file[rev_mapping[FILE1]], commonname, &last_block);
 383   thread0 = process_diff (file[rev_mapping[FILE0]], commonname, &last_block);
 384   diff3 = make_3way_diff (thread0, thread1);
 385   if (edscript)
 386     conflicts_found
 387       = output_diff3_edscript (stdout, diff3, mapping, rev_mapping,
 388                                tag_strings[0], tag_strings[1], tag_strings[2]);
 389   else if (merge)
 390     {
 391       xfreopen (file[rev_mapping[FILE0]], "r", stdin);
 392       conflicts_found
 393         = output_diff3_merge (stdin, stdout, diff3, mapping, rev_mapping,
 394                               tag_strings[0], tag_strings[1], tag_strings[2]);
 395       if (ferror (stdin))
 396         fatal ("read failed");
 397     }
 398   else
 399     {
 400       output_diff3 (stdout, diff3, mapping, rev_mapping);
 401       conflicts_found = false;
 402     }
 403
 404   check_stdout ();
 405   exit (conflicts_found);
 406   return conflicts_found;
 407 }
 408
 409 static void
 410 try_help (char const *reason_msgid, char const *operand)
 411 {
 412   if (reason_msgid)
 413     error (0, 0, _(reason_msgid), operand);
 414   error (EXIT_TROUBLE, 0,
 415          _("Try `%s --help' for more information."), program_name);
 416   abort ();
 417 }
 418
 419 static void
 420 check_stdout (void)
 421 {
 422   if (ferror (stdout))
 423     fatal ("write failed");
 424   else if (fclose (stdout) != 0)
 425     perror_with_exit (_("standard output"));
 426 }
 427
 428 static char const * const option_help_msgid[] = {
 429   N_("-e  --ed  Output unmerged changes from OLDFILE to YOURFILE into MYFILE."),
 430   N_("-E  --show-overlap  Output unmerged changes, bracketing conflicts."),
 431   N_("-A  --show-all  Output all changes, bracketing conflicts."),
 432   N_("-x  --overlap-only  Output overlapping changes."),
 433   N_("-X  Output overlapping changes, bracketing them."),
 434   N_("-3  --easy-only  Output unmerged nonoverlapping changes."),
 435   "",
 436   N_("-m  --merge  Output merged file instead of ed script (default -A)."),
 437   N_("-L LABEL  --label=LABEL  Use LABEL instead of file name."),
 438   N_("-i  Append `w' and `q' commands to ed scripts."),
 439   N_("-a  --text  Treat all files as text."),
 440   N_("--strip-trailing-cr  Strip trailing carriage return on input."),
 441   N_("-T  --initial-tab  Make tabs line up by prepending a tab."),
 442   N_("--diff-program=PROGRAM  Use PROGRAM to compare files."),
 443   "",
 444   N_("-v  --version  Output version info."),
 445   N_("--help  Output this help."),
 446   0
 447 };
 448
 449 static void
 450 usage (void)
 451 {
 452   char const * const *p;
 453
 454   printf (_("Usage: %s [OPTION]... MYFILE OLDFILE YOURFILE\n"),
 455           program_name);
 456   printf ("%s\n\n", _("Compare three files line by line."));
 457   for (p = option_help_msgid;  *p;  p++)
 458     if (**p)
 459       printf ("  %s\n", _(*p));
 460     else
 461       putchar ('\n');
 462   printf ("\n%s\n%s\n",
 463           _("If a FILE is `-', read standard input."),
 464           _("Exit status is 0 if successful, 1 if conflicts, 2 if trouble."));
 465   emit_bug_reporting_address ();
 466 }
 467 \f
 468 /* Combine the two diffs together into one.
 469    Here is the algorithm:
 470
 471      File2 is shared in common between the two diffs.
 472      Diff02 is the diff between 0 and 2.
 473      Diff12 is the diff between 1 and 2.
 474
 475         1) Find the range for the first block in File2.
 476             a) Take the lowest of the two ranges (in File2) in the two
 477                current blocks (one from each diff) as being the low
 478                water mark.  Assign the upper end of this block as
 479                being the high water mark and move the current block up
 480                one.  Mark the block just moved over as to be used.
 481             b) Check the next block in the diff that the high water
 482                mark is *not* from.
 483
 484                *If* the high water mark is above
 485                the low end of the range in that block,
 486
 487                    mark that block as to be used and move the current
 488                    block up.  Set the high water mark to the max of
 489                    the high end of this block and the current.  Repeat b.
 490
 491          2) Find the corresponding ranges in File0 (from the blocks
 492             in diff02; line per line outside of diffs) and in File1.
 493             Create a diff3_block, reserving space as indicated by the ranges.
 494
 495          3) Copy all of the pointers for file2 in.  At least for now,
 496             do memcmp's between corresponding strings in the two diffs.
 497
 498          4) Copy all of the pointers for file0 and 1 in.  Get what is
 499             needed from file2 (when there isn't a diff block, it's
 500             identical to file2 within the range between diff blocks).
 501
 502          5) If the diff blocks used came from only one of the two
 503             strings of diffs, then that file (i.e. the one other than
 504             the common file in that diff) is the odd person out.  If
 505             diff blocks are used from both sets, check to see if files
 506             0 and 1 match:
 507
 508                 Same number of lines?  If so, do a set of memcmp's (if
 509             a memcmp matches; copy the pointer over; it'll be easier
 510             later during comparisons).  If they match, 0 & 1 are the
 511             same.  If not, all three different.
 512
 513      Then do it again, until the blocks are exhausted.  */
 514
 515
 516 /* Make a three way diff (chain of diff3_block's) from two two way
 517    diffs (chains of diff_block's).  Assume that each of the two diffs
 518    passed are onto the same file (i.e. that each of the diffs were
 519    made "to" the same file).  Return a three way diff pointer with
 520    numbering FILE0 = the other file in diff02, FILE1 = the other file
 521    in diff12, and FILEC = the common file.  */
 522
 523 static struct diff3_block *
 524 make_3way_diff (struct diff_block *thread0, struct diff_block *thread1)
 525 {
 526   /* Work on the two diffs passed to it as threads.  Thread number 0
 527      is diff02, thread number 1 is diff12.  USING is the base of the
 528      list of blocks to be used to construct each block of the three
 529      way diff; if no blocks from a particular thread are to be used,
 530      that element of USING is 0.  LAST_USING contains the last
 531      elements on each of the using lists.
 532
 533      HIGH_WATER_MARK is the highest line number in the common file
 534      described in any of the diffs in either of the USING lists.
 535      HIGH_WATER_THREAD names the thread.  Similarly BASE_WATER_MARK
 536      and BASE_WATER_THREAD describe the lowest line number in the
 537      common file described in any of the diffs in either of the USING
 538      lists.  HIGH_WATER_DIFF is the diff from which the
 539      HIGH_WATER_MARK was taken.
 540
 541      HIGH_WATER_DIFF should always be equal to
 542      LAST_USING[HIGH_WATER_THREAD].  OTHER_DIFF is the next diff to
 543      check for higher water, and should always be equal to
 544      CURRENT[HIGH_WATER_THREAD ^ 1].  OTHER_THREAD is the thread in
 545      which the OTHER_DIFF is, and hence should always be equal to
 546      HIGH_WATER_THREAD ^ 1.
 547
 548      LAST_DIFF is the last diff block produced by this routine, for
 549      line correspondence purposes between that diff and the one
 550      currently being worked on.  It is ZERO_DIFF before any blocks
 551      have been created.  */
 552
 553   struct diff_block *using[2];
 554   struct diff_block *last_using[2];
 555   struct diff_block *current[2];
 556
 557   lin high_water_mark;
 558
 559   int high_water_thread;
 560   int base_water_thread;
 561   int other_thread;
 562
 563   struct diff_block *high_water_diff;
 564   struct diff_block *other_diff;
 565
 566   struct diff3_block *result;
 567   struct diff3_block *tmpblock;
 568   struct diff3_block **result_end;
 569
 570   struct diff3_block const *last_diff3;
 571
 572   static struct diff3_block const zero_diff3;
 573
 574   /* Initialization */
 575   result = 0;
 576   result_end = &result;
 577   current[0] = thread0; current[1] = thread1;
 578   last_diff3 = &zero_diff3;
 579
 580   /* Sniff up the threads until we reach the end */
 581
 582   while (current[0] || current[1])
 583     {
 584       using[0] = using[1] = last_using[0] = last_using[1] = 0;
 585
 586       /* Setup low and high water threads, diffs, and marks.  */
 587       if (!current[0])
 588         base_water_thread = 1;
 589       else if (!current[1])
 590         base_water_thread = 0;
 591       else
 592         base_water_thread =
 593           (D_LOWLINE (current[0], FC) > D_LOWLINE (current[1], FC));
 594
 595       high_water_thread = base_water_thread;
 596
 597       high_water_diff = current[high_water_thread];
 598
 599       high_water_mark = D_HIGHLINE (high_water_diff, FC);
 600
 601       /* Make the diff you just got info from into the using class */
 602       using[high_water_thread]
 603         = last_using[high_water_thread]
 604         = high_water_diff;
 605       current[high_water_thread] = high_water_diff->next;
 606       last_using[high_water_thread]->next = 0;
 607
 608       /* And mark the other diff */
 609       other_thread = high_water_thread ^ 0x1;
 610       other_diff = current[other_thread];
 611
 612       /* Shuffle up the ladder, checking the other diff to see if it
 613          needs to be incorporated.  */
 614       while (other_diff
 615              && D_LOWLINE (other_diff, FC) <= high_water_mark + 1)
 616         {
 617
 618           /* Incorporate this diff into the using list.  Note that
 619              this doesn't take it off the current list */
 620           if (using[other_thread])
 621             last_using[other_thread]->next = other_diff;
 622           else
 623             using[other_thread] = other_diff;
 624           last_using[other_thread] = other_diff;
 625
 626           /* Take it off the current list.  Note that this following
 627              code assumes that other_diff enters it equal to
 628              current[high_water_thread ^ 0x1] */
 629           current[other_thread] = current[other_thread]->next;
 630           other_diff->next = 0;
 631
 632           /* Set the high_water stuff
 633              If this comparison is equal, then this is the last pass
 634              through this loop; since diff blocks within a given
 635              thread cannot overlap, the high_water_mark will be
 636              *below* the range_start of either of the next diffs.  */
 637
 638           if (high_water_mark < D_HIGHLINE (other_diff, FC))
 639             {
 640               high_water_thread ^= 1;
 641               high_water_mark = D_HIGHLINE (other_diff, FC);
 642             }
 643
 644           /* Set the other diff */
 645           other_thread = high_water_thread ^ 0x1;
 646           other_diff = current[other_thread];
 647         }
 648
 649       /* The using lists contain a list of all of the blocks to be
 650          included in this diff3_block.  Create it.  */
 651
 652       tmpblock = using_to_diff3_block (using, last_using,
 653                                        base_water_thread, high_water_thread,
 654                                        last_diff3);
 655
 656       if (!tmpblock)
 657         fatal ("internal error: screwup in format of diff blocks");
 658
 659       /* Put it on the list.  */
 660       *result_end = tmpblock;
 661       result_end = &tmpblock->next;
 662
 663       /* Set up corresponding lines correctly.  */
 664       last_diff3 = tmpblock;
 665     }
 666   return result;
 667 }
 668
 669 /* Take two lists of blocks (from two separate diff threads) and put
 670    them together into one diff3 block.  Return a pointer to this diff3
 671    block or 0 for failure.
 672
 673    All arguments besides using are for the convenience of the routine;
 674    they could be derived from the using array.  LAST_USING is a pair
 675    of pointers to the last blocks in the using structure.  LOW_THREAD
 676    and HIGH_THREAD tell which threads contain the lowest and highest
 677    line numbers for File0.  LAST_DIFF3 contains the last diff produced
 678    in the calling routine.  This is used for lines mappings that
 679    would still be identical to the state that diff ended in.
 680
 681    A distinction should be made in this routine between the two diffs
 682    that are part of a normal two diff block, and the three diffs that
 683    are part of a diff3_block.  */
 684
 685 static struct diff3_block *
 686 using_to_diff3_block (struct diff_block *using[2],
 687                       struct diff_block *last_using[2],
 688                       int low_thread, int high_thread,
 689                       struct diff3_block const *last_diff3)
 690 {
 691   lin low[2], high[2];
 692   struct diff3_block *result;
 693   struct diff_block *ptr;
 694   int d;
 695   lin i;
 696
 697   /* Find the range in the common file.  */
 698   lin lowc = D_LOWLINE (using[low_thread], FC);
 699   lin highc = D_HIGHLINE (last_using[high_thread], FC);
 700
 701   /* Find the ranges in the other files.
 702      If using[d] is null, that means that the file to which that diff
 703      refers is equivalent to the common file over this range.  */
 704
 705   for (d = 0; d < 2; d++)
 706     if (using[d])
 707       {
 708         low[d] = D_LOW_MAPLINE (using[d], FC, FO, lowc);
 709         high[d] = D_HIGH_MAPLINE (last_using[d], FC, FO, highc);
 710       }
 711     else
 712       {
 713         low[d] = D_HIGH_MAPLINE (last_diff3, FILEC, FILE0 + d, lowc);
 714         high[d] = D_HIGH_MAPLINE (last_diff3, FILEC, FILE0 + d, highc);
 715       }
 716
 717   /* Create a block with the appropriate sizes */
 718   result = create_diff3_block (low[0], high[0], low[1], high[1], lowc, highc);
 719
 720   /* Copy information for the common file.
 721      Return with a zero if any of the compares failed.  */
 722
 723   for (d = 0; d < 2; d++)
 724     for (ptr = using[d]; ptr; ptr = D_NEXT (ptr))
 725       {
 726         lin result_offset = D_LOWLINE (ptr, FC) - lowc;
 727
 728         if (!copy_stringlist (D_LINEARRAY (ptr, FC),
 729                               D_LENARRAY (ptr, FC),
 730                               D_LINEARRAY (result, FILEC) + result_offset,
 731                               D_LENARRAY (result, FILEC) + result_offset,
 732                               D_NUMLINES (ptr, FC)))
 733           return 0;
 734       }
 735
 736   /* Copy information for file d.  First deal with anything that might be
 737      before the first diff.  */
 738
 739   for (d = 0; d < 2; d++)
 740     {
 741       struct diff_block *u = using[d];
 742       lin lo = low[d], hi = high[d];
 743
 744       for (i = 0;
 745            i + lo < (u ? D_LOWLINE (u, FO) : hi + 1);
 746            i++)
 747         {
 748           D_RELNUM (result, FILE0 + d, i) = D_RELNUM (result, FILEC, i);
 749           D_RELLEN (result, FILE0 + d, i) = D_RELLEN (result, FILEC, i);
 750         }
 751
 752       for (ptr = u; ptr; ptr = D_NEXT (ptr))
 753         {
 754           lin result_offset = D_LOWLINE (ptr, FO) - lo;
 755           lin linec;
 756
 757           if (!copy_stringlist (D_LINEARRAY (ptr, FO),
 758                                 D_LENARRAY (ptr, FO),
 759                                 D_LINEARRAY (result, FILE0 + d) + result_offset,
 760                                 D_LENARRAY (result, FILE0 + d) + result_offset,
 761                                 D_NUMLINES (ptr, FO)))
 762             return 0;
 763
 764           /* Catch the lines between here and the next diff */
 765           linec = D_HIGHLINE (ptr, FC) + 1 - lowc;
 766           for (i = D_HIGHLINE (ptr, FO) + 1 - lo;
 767                i < (D_NEXT (ptr) ? D_LOWLINE (D_NEXT (ptr), FO) : hi + 1) - lo;
 768                i++)
 769             {
 770               D_RELNUM (result, FILE0 + d, i) = D_RELNUM (result, FILEC, linec);
 771               D_RELLEN (result, FILE0 + d, i) = D_RELLEN (result, FILEC, linec);
 772               linec++;
 773             }
 774         }
 775     }
 776
 777   /* Set correspond */
 778   if (!using[0])
 779     D3_TYPE (result) = DIFF_2ND;
 780   else if (!using[1])
 781     D3_TYPE (result) = DIFF_1ST;
 782   else
 783     {
 784       lin nl0 = D_NUMLINES (result, FILE0);
 785       lin nl1 = D_NUMLINES (result, FILE1);
 786
 787       if (nl0 != nl1
 788           || !compare_line_list (D_LINEARRAY (result, FILE0),
 789                                  D_LENARRAY (result, FILE0),
 790                                  D_LINEARRAY (result, FILE1),
 791                                  D_LENARRAY (result, FILE1),
 792                                  nl0))
 793         D3_TYPE (result) = DIFF_ALL;
 794       else
 795         D3_TYPE (result) = DIFF_3RD;
 796     }
 797
 798   return result;
 799 }
 800
 801 /* Copy pointers from a list of strings to a different list of
 802    strings.  If a spot in the second list is already filled, make sure
 803    that it is filled with the same string; if not, return false, the copy
 804    incomplete.  Upon successful completion of the copy, return true.  */
 805
 806 static bool
 807 copy_stringlist (char * const fromptrs[], size_t const fromlengths[],
 808                  char *toptrs[], size_t tolengths[],
 809                  lin copynum)
 810 {
 811   register char * const *f = fromptrs;
 812   register char **t = toptrs;
 813   register size_t const *fl = fromlengths;
 814   register size_t *tl = tolengths;
 815
 816   while (copynum--)
 817     {
 818       if (*t)
 819         {
 820           if (*fl != *tl || memcmp (*f, *t, *fl) != 0)
 821             return false;
 822         }
 823       else
 824         {
 825           *t = *f;
 826           *tl = *fl;
 827         }
 828
 829       t++; f++; tl++; fl++;
 830     }
 831
 832   return true;
 833 }
 834
 835 /* Create a diff3_block, with ranges as specified in the arguments.
 836    Allocate the arrays for the various pointers (and zero them) based
 837    on the arguments passed.  Return the block as a result.  */
 838
 839 static struct diff3_block *
 840 create_diff3_block (lin low0, lin high0,
 841                     lin low1, lin high1,
 842                     lin low2, lin high2)
 843 {
 844   struct diff3_block *result = xmalloc (sizeof *result);
 845   lin numlines;
 846
 847   D3_TYPE (result) = ERROR;
 848   D_NEXT (result) = 0;
 849
 850   /* Assign ranges */
 851   D_LOWLINE (result, FILE0) = low0;
 852   D_HIGHLINE (result, FILE0) = high0;
 853   D_LOWLINE (result, FILE1) = low1;
 854   D_HIGHLINE (result, FILE1) = high1;
 855   D_LOWLINE (result, FILE2) = low2;
 856   D_HIGHLINE (result, FILE2) = high2;
 857
 858   /* Allocate and zero space */
 859   numlines = D_NUMLINES (result, FILE0);
 860   if (numlines)
 861     {
 862       D_LINEARRAY (result, FILE0) = xcalloc (numlines, sizeof (char *));
 863       D_LENARRAY (result, FILE0) = xcalloc (numlines, sizeof (size_t));
 864     }
 865   else
 866     {
 867       D_LINEARRAY (result, FILE0) = 0;
 868       D_LENARRAY (result, FILE0) = 0;
 869     }
 870
 871   numlines = D_NUMLINES (result, FILE1);
 872   if (numlines)
 873     {
 874       D_LINEARRAY (result, FILE1) = xcalloc (numlines, sizeof (char *));
 875       D_LENARRAY (result, FILE1) = xcalloc (numlines, sizeof (size_t));
 876     }
 877   else
 878     {
 879       D_LINEARRAY (result, FILE1) = 0;
 880       D_LENARRAY (result, FILE1) = 0;
 881     }
 882
 883   numlines = D_NUMLINES (result, FILE2);
 884   if (numlines)
 885     {
 886       D_LINEARRAY (result, FILE2) = xcalloc (numlines, sizeof (char *));
 887       D_LENARRAY (result, FILE2) = xcalloc (numlines, sizeof (size_t));
 888     }
 889   else
 890     {
 891       D_LINEARRAY (result, FILE2) = 0;
 892       D_LENARRAY (result, FILE2) = 0;
 893     }
 894
 895   /* Return */
 896   return result;
 897 }
 898
 899 /* Compare two lists of lines of text.
 900    Return 1 if they are equivalent, 0 if not.  */
 901
 902 static bool
 903 compare_line_list (char * const list1[], size_t const lengths1[],
 904                    char * const list2[], size_t const lengths2[],
 905                    lin nl)
 906 {
 907   char * const *l1 = list1;
 908   char * const *l2 = list2;
 909   size_t const *lgths1 = lengths1;
 910   size_t const *lgths2 = lengths2;
 911
 912   while (nl--)
 913     if (!*l1 || !*l2 || *lgths1 != *lgths2++
 914         || memcmp (*l1++, *l2++, *lgths1++) != 0)
 915       return false;
 916   return true;
 917 }
 918 \f
 919 /* Input and parse two way diffs.  */
 920
 921 static struct diff_block *
 922 process_diff (char const *filea,
 923               char const *fileb,
 924               struct diff_block **last_block)
 925 {
 926   char *diff_contents;
 927   char *diff_limit;
 928   char *scan_diff;
 929   enum diff_type dt;
 930   lin i;
 931   struct diff_block *block_list;
 932   struct diff_block **block_list_end = &block_list;
 933   struct diff_block *bptr IF_LINT (= NULL);
 934   size_t too_many_lines = (PTRDIFF_MAX
 935                            / MIN (sizeof *bptr->lines[1],
 936                                   sizeof *bptr->lengths[1]));
 937
 938   diff_limit = read_diff (filea, fileb, &diff_contents);
 939   scan_diff = diff_contents;
 940
 941   while (scan_diff < diff_limit)
 942     {
 943       bptr = xmalloc (sizeof *bptr);
 944       bptr->lines[0] = bptr->lines[1] = 0;
 945       bptr->lengths[0] = bptr->lengths[1] = 0;
 946
 947       dt = process_diff_control (&scan_diff, bptr);
 948       if (dt == ERROR || *scan_diff != '\n')
 949         {
 950           fprintf (stderr, _("%s: diff failed: "), program_name);
 951           do
 952             {
 953               putc (*scan_diff, stderr);
 954             }
 955           while (*scan_diff++ != '\n');
 956           exit (EXIT_TROUBLE);
 957         }
 958       scan_diff++;
 959
 960       /* Force appropriate ranges to be null, if necessary */
 961       switch (dt)
 962         {
 963         case ADD:
 964           bptr->ranges[0][0]++;
 965           break;
 966         case DELETE:
 967           bptr->ranges[1][0]++;
 968           break;
 969         case CHANGE:
 970           break;
 971         default:
 972           fatal ("internal error: invalid diff type in process_diff");
 973           break;
 974         }
 975
 976       /* Allocate space for the pointers for the lines from filea, and
 977          parcel them out among these pointers */
 978       if (dt != ADD)
 979         {
 980           lin numlines = D_NUMLINES (bptr, 0);
 981           if (too_many_lines <= numlines)
 982             xalloc_die ();
 983           bptr->lines[0] = xmalloc (numlines * sizeof *bptr->lines[0]);
 984           bptr->lengths[0] = xmalloc (numlines * sizeof *bptr->lengths[0]);
 985           for (i = 0; i < numlines; i++)
 986             scan_diff = scan_diff_line (scan_diff,
 987                                         &(bptr->lines[0][i]),
 988                                         &(bptr->lengths[0][i]),
 989                                         diff_limit,
 990                                         '<');
 991         }
 992
 993       /* Get past the separator for changes */
 994       if (dt == CHANGE)
 995         {
 996           if (strncmp (scan_diff, "---\n", 4))
 997             fatal ("invalid diff format; invalid change separator");
 998           scan_diff += 4;
 999         }
1000
1001       /* Allocate space for the pointers for the lines from fileb, and
1002          parcel them out among these pointers */
1003       if (dt != DELETE)
1004         {
1005           lin numlines = D_NUMLINES (bptr, 1);
1006           if (too_many_lines <= numlines)
1007             xalloc_die ();
1008           bptr->lines[1] = xmalloc (numlines * sizeof *bptr->lines[1]);
1009           bptr->lengths[1] = xmalloc (numlines * sizeof *bptr->lengths[1]);
1010           for (i = 0; i < numlines; i++)
1011             scan_diff = scan_diff_line (scan_diff,
1012                                         &(bptr->lines[1][i]),
1013                                         &(bptr->lengths[1][i]),
1014                                         diff_limit,
1015                                         '>');
1016         }
1017
1018       /* Place this block on the blocklist.  */
1019       *block_list_end = bptr;
1020       block_list_end = &bptr->next;
1021     }
1022
1023   *block_list_end = NULL;
1024   *last_block = bptr;
1025   return block_list;
1026 }
1027
1028 /* Skip tabs and spaces, and return the first character after them.  */
1029
1030 static char *
1031 skipwhite (char *s)
1032 {
1033   while (*s == ' ' || *s == '\t')
1034     s++;
1035   return s;
1036 }
1037
1038 /* Read a nonnegative line number from S, returning the address of the
1039    first character after the line number, and storing the number into
1040    *PNUM.  Return 0 if S does not point to a valid line number.  */
1041
1042 static char *
1043 readnum (char *s, lin *pnum)
1044 {
1045   unsigned char c = *s;
1046   lin num = 0;
1047
1048   if (! ISDIGIT (c))
1049     return 0;
1050
1051   do
1052     {
1053       num = c - '0' + num * 10;
1054       c = *++s;
1055     }
1056   while (ISDIGIT (c));
1057
1058   *pnum = num;
1059   return s;
1060 }
1061
1062 /* Parse a normal format diff control string.  Return the type of the
1063    diff (ERROR if the format is bad).  All of the other important
1064    information is filled into to the structure pointed to by db, and
1065    the string pointer (whose location is passed to this routine) is
1066    updated to point beyond the end of the string parsed.  Note that
1067    only the ranges in the diff_block will be set by this routine.
1068
1069    If some specific pair of numbers has been reduced to a single
1070    number, then both corresponding numbers in the diff block are set
1071    to that number.  In general these numbers are interpreted as ranges
1072    inclusive, unless being used by the ADD or DELETE commands.  It is
1073    assumed that these will be special cased in a superior routine.   */
1074
1075 static enum diff_type
1076 process_diff_control (char **string, struct diff_block *db)
1077 {
1078   char *s = *string;
1079   enum diff_type type;
1080
1081   /* Read first set of digits */
1082   s = readnum (skipwhite (s), &db->ranges[0][RANGE_START]);
1083   if (! s)
1084     return ERROR;
1085
1086   /* Was that the only digit? */
1087   s = skipwhite (s);
1088   if (*s == ',')
1089     {
1090       s = readnum (s + 1, &db->ranges[0][RANGE_END]);
1091       if (! s)
1092         return ERROR;
1093     }
1094   else
1095     db->ranges[0][RANGE_END] = db->ranges[0][RANGE_START];
1096
1097   /* Get the letter */
1098   s = skipwhite (s);
1099   switch (*s)
1100     {
1101     case 'a':
1102       type = ADD;
1103       break;
1104     case 'c':
1105       type = CHANGE;
1106       break;
1107     case 'd':
1108       type = DELETE;
1109       break;
1110     default:
1111       return ERROR;                     /* Bad format */
1112     }
1113   s++;                          /* Past letter */
1114
1115   /* Read second set of digits */
1116   s = readnum (skipwhite (s), &db->ranges[1][RANGE_START]);
1117   if (! s)
1118     return ERROR;
1119
1120   /* Was that the only digit? */
1121   s = skipwhite (s);
1122   if (*s == ',')
1123     {
1124       s = readnum (s + 1, &db->ranges[1][RANGE_END]);
1125       if (! s)
1126         return ERROR;
1127       s = skipwhite (s);                /* To move to end */
1128     }
1129   else
1130     db->ranges[1][RANGE_END] = db->ranges[1][RANGE_START];
1131
1132   *string = s;
1133   return type;
1134 }
1135
1136 static char *
1137 read_diff (char const *filea,
1138            char const *fileb,
1139            char **output_placement)
1140 {
1141   char *diff_result;
1142   size_t current_chunk_size, total;
1143   int fd, wstatus, status;
1144   int werrno = 0;
1145   struct stat pipestat;
1146
1147 #if HAVE_WORKING_FORK || HAVE_WORKING_VFORK
1148
1149   char const *argv[9];
1150   char const **ap;
1151   int fds[2];
1152   pid_t pid;
1153
1154   ap = argv;
1155   *ap++ = diff_program;
1156   if (text)
1157     *ap++ = "-a";
1158   if (strip_trailing_cr)
1159     *ap++ = "--strip-trailing-cr";
1160   *ap++ = "--horizon-lines=100";
1161   *ap++ = "--";
1162   *ap++ = filea;
1163   *ap++ = fileb;
1164   *ap = 0;
1165
1166   if (pipe (fds) != 0)
1167     perror_with_exit ("pipe");
1168
1169   pid = vfork ();
1170   if (pid == 0)
1171     {
1172       /* Child */
1173       close (fds[0]);
1174       if (fds[1] != STDOUT_FILENO)
1175         {
1176           dup2 (fds[1], STDOUT_FILENO);
1177           close (fds[1]);
1178         }
1179
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);
1183
1184       _exit (errno == ENOENT ? 127 : 126);
1185     }
1186
1187   if (pid == -1)
1188     perror_with_exit ("fork");
1189
1190   close (fds[1]);               /* Prevent erroneous lack of EOF */
1191   fd = fds[0];
1192
1193 #else
1194
1195   FILE *fpipe;
1196   char const args[] = " --horizon-lines=100 -- ";
1197   char *command = xmalloc (shell_quote_length (diff_program)
1198                            + sizeof "-a"
1199                            + sizeof "--strip-trailing-cr"
1200                            + sizeof args - 1
1201                            + shell_quote_length (filea) + 1
1202                            + shell_quote_length (fileb) + 1);
1203   char *p = command;
1204   p = shell_quote_copy (p, diff_program);
1205   if (text)
1206     {
1207       strcpy (p, " -a");
1208       p += 3;
1209     }
1210   if (strip_trailing_cr)
1211     {
1212       strcpy (p, " --strip-trailing-cr");
1213       p += 20;
1214     }
1215   strcpy (p, args);
1216   p += sizeof args - 1;
1217   p = shell_quote_copy (p, filea);
1218   *p++ = ' ';
1219   p = shell_quote_copy (p, fileb);
1220   *p = 0;
1221   errno = 0;
1222   fpipe = popen (command, "r");
1223   if (!fpipe)
1224     perror_with_exit (command);
1225   free (command);
1226   fd = fileno (fpipe);
1227
1228 #endif
1229
1230   if (fstat (fd, &pipestat) != 0)
1231     perror_with_exit ("fstat");
1232   current_chunk_size = MAX (1, STAT_BLOCKSIZE (pipestat));
1233   diff_result = xmalloc (current_chunk_size);
1234   total = 0;
1235
1236   for (;;)
1237     {
1238       size_t bytes_to_read = current_chunk_size - total;
1239       size_t bytes = block_read (fd, diff_result + total, bytes_to_read);
1240       total += bytes;
1241       if (bytes != bytes_to_read)
1242         {
1243           if (bytes == SIZE_MAX)
1244             perror_with_exit (_("read failed"));
1245           break;
1246         }
1247       if (PTRDIFF_MAX / 2 <= current_chunk_size)
1248         xalloc_die ();
1249       current_chunk_size *= 2;
1250       diff_result = xrealloc (diff_result, current_chunk_size);
1251     }
1252
1253   if (total != 0 && diff_result[total-1] != '\n')
1254     fatal ("invalid diff format; incomplete last line");
1255
1256   *output_placement = diff_result;
1257
1258 #if ! (HAVE_WORKING_FORK || HAVE_WORKING_VFORK)
1259
1260   wstatus = pclose (fpipe);
1261   if (wstatus == -1)
1262     werrno = errno;
1263
1264 #else
1265
1266   if (close (fd) != 0)
1267     perror_with_exit ("close");
1268   if (waitpid (pid, &wstatus, 0) < 0)
1269     perror_with_exit ("waitpid");
1270
1271 #endif
1272
1273   status = ! werrno && WIFEXITED (wstatus) ? WEXITSTATUS (wstatus) : INT_MAX;
1274
1275   if (EXIT_TROUBLE <= status)
1276     error (EXIT_TROUBLE, werrno,
1277            _(status == 126
1278              ? "subsidiary program `%s' could not be invoked"
1279              : status == 127
1280              ? "subsidiary program `%s' not found"
1281              : status == INT_MAX
1282              ? "subsidiary program `%s' failed"
1283              : "subsidiary program `%s' failed (exit status %d)"),
1284            diff_program, status);
1285
1286   return diff_result + total;
1287 }
1288
1289
1290 /* Scan a regular diff line (consisting of > or <, followed by a
1291    space, followed by text (including nulls) up to a newline.
1292
1293    This next routine began life as a macro and many parameters in it
1294    are used as call-by-reference values.  */
1295 static char *
1296 scan_diff_line (char *scan_ptr, char **set_start, size_t *set_length,
1297                 char *limit, char leadingchar)
1298 {
1299   char *line_ptr;
1300
1301   if (!(scan_ptr[0] == leadingchar
1302         && scan_ptr[1] == ' '))
1303     fatal ("invalid diff format; incorrect leading line chars");
1304
1305   *set_start = line_ptr = scan_ptr + 2;
1306   while (*line_ptr++ != '\n')
1307     continue;
1308
1309   /* Include newline if the original line ended in a newline,
1310      or if an edit script is being generated.
1311      Copy any missing newline message to stderr if an edit script is being
1312      generated, because edit scripts cannot handle missing newlines.
1313      Return the beginning of the next line.  */
1314   *set_length = line_ptr - *set_start;
1315   if (line_ptr < limit && *line_ptr == '\\')
1316     {
1317       if (edscript)
1318         fprintf (stderr, "%s:", program_name);
1319       else
1320         --*set_length;
1321       line_ptr++;
1322       do
1323         {
1324           if (edscript)
1325             putc (*line_ptr, stderr);
1326         }
1327       while (*line_ptr++ != '\n');
1328     }
1329
1330   return line_ptr;
1331 }
1332
1333 /* Output a three way diff passed as a list of diff3_block's.  The
1334    argument MAPPING is indexed by external file number (in the
1335    argument list) and contains the internal file number (from the diff
1336    passed).  This is important because the user expects outputs in
1337    terms of the argument list number, and the diff passed may have
1338    been done slightly differently (if the last argument was "-", for
1339    example).  REV_MAPPING is the inverse of MAPPING.  */
1340
1341 static void
1342 output_diff3 (FILE *outputfile, struct diff3_block *diff,
1343               int const mapping[3], int const rev_mapping[3])
1344 {
1345   int i;
1346   int oddoneout;
1347   char *cp;
1348   struct diff3_block *ptr;
1349   lin line;
1350   size_t length;
1351   int dontprint;
1352   static int skew_increment[3] = { 2, 3, 1 }; /* 0==>2==>1==>3 */
1353   char const *line_prefix = initial_tab ? "\t" : "  ";
1354
1355   for (ptr = diff; ptr; ptr = D_NEXT (ptr))
1356     {
1357       char x[2];
1358
1359       switch (ptr->correspond)
1360         {
1361         case DIFF_ALL:
1362           x[0] = 0;
1363           dontprint = 3;        /* Print them all */
1364           oddoneout = 3;        /* Nobody's odder than anyone else */
1365           break;
1366         case DIFF_1ST:
1367         case DIFF_2ND:
1368         case DIFF_3RD:
1369           oddoneout = rev_mapping[ptr->correspond - DIFF_1ST];
1370
1371           x[0] = oddoneout + '1';
1372           x[1] = 0;
1373           dontprint = oddoneout == 0;
1374           break;
1375         default:
1376           fatal ("internal error: invalid diff type passed to output");
1377         }
1378       fprintf (outputfile, "====%s\n", x);
1379
1380       /* Go 0, 2, 1 if the first and third outputs are equivalent.  */
1381       for (i = 0; i < 3;
1382            i = (oddoneout == 1 ? skew_increment[i] : i + 1))
1383         {
1384           int realfile = mapping[i];
1385           lin lowt = D_LOWLINE (ptr, realfile);
1386           lin hight = D_HIGHLINE (ptr, realfile);
1387           long int llowt = lowt;
1388           long int lhight = hight;
1389
1390           fprintf (outputfile, "%d:", i + 1);
1391           switch (lowt - hight)
1392             {
1393             case 1:
1394               fprintf (outputfile, "%lda\n", llowt - 1);
1395               break;
1396             case 0:
1397               fprintf (outputfile, "%ldc\n", llowt);
1398               break;
1399             default:
1400               fprintf (outputfile, "%ld,%ldc\n", llowt, lhight);
1401               break;
1402             }
1403
1404           if (i == dontprint) continue;
1405
1406           if (lowt <= hight)
1407             {
1408               line = 0;
1409               do
1410                 {
1411                   fputs (line_prefix, outputfile);
1412                   cp = D_RELNUM (ptr, realfile, line);
1413                   length = D_RELLEN (ptr, realfile, line);
1414                   fwrite (cp, sizeof (char), length, outputfile);
1415                 }
1416               while (++line < hight - lowt + 1);
1417               if (cp[length - 1] != '\n')
1418                 fprintf (outputfile, "\n\\ %s\n",
1419                          _("No newline at end of file"));
1420             }
1421         }
1422     }
1423 }
1424
1425
1426 /* Output to OUTPUTFILE the lines of B taken from FILENUM.  Double any
1427    initial '.'s; yield nonzero if any initial '.'s were doubled.  */
1428
1429 static bool
1430 dotlines (FILE *outputfile, struct diff3_block *b, int filenum)
1431 {
1432   lin i;
1433   bool leading_dot = false;
1434
1435   for (i = 0;
1436        i < D_NUMLINES (b, filenum);
1437        i++)
1438     {
1439       char *line = D_RELNUM (b, filenum, i);
1440       if (line[0] == '.')
1441         {
1442           leading_dot = true;
1443           fputc ('.', outputfile);
1444         }
1445       fwrite (line, sizeof (char),
1446               D_RELLEN (b, filenum, i), outputfile);
1447     }
1448
1449   return leading_dot;
1450 }
1451
1452 /* Output to OUTPUTFILE a '.' line.  If LEADING_DOT is true, also
1453    output a command that removes initial '.'s starting with line START
1454    and continuing for NUM lines.  (START is long int, not lin, for
1455    convenience with printf %ld formats.)  */
1456
1457 static void
1458 undotlines (FILE *outputfile, bool leading_dot, long int start, lin num)
1459 {
1460   fputs (".\n", outputfile);
1461   if (leading_dot)
1462     {
1463       if (num == 1)
1464         fprintf (outputfile, "%lds/^\\.//\n", start);
1465       else
1466         fprintf (outputfile, "%ld,%lds/^\\.//\n", start, start + num - 1);
1467     }
1468 }
1469
1470 /* Output a diff3 set of blocks as an ed script.  This script applies
1471    the changes between file's 2 & 3 to file 1.  Take the precise
1472    format of the ed script to be output from global variables set
1473    during options processing.  Reverse the order of
1474    the set of diff3 blocks in DIFF; this gets
1475    around the problems involved with changing line numbers in an ed
1476    script.
1477
1478    As in `output_diff3', the variable MAPPING maps from file number
1479    according to the argument list to file number according to the diff
1480    passed.  All files listed below are in terms of the argument list.
1481    REV_MAPPING is the inverse of MAPPING.
1482
1483    FILE0, FILE1 and FILE2 are the strings to print as the names of the
1484    three files.  These may be the actual names, or may be the
1485    arguments specified with -L.
1486
1487    Return 1 if conflicts were found.  */
1488
1489 static bool
1490 output_diff3_edscript (FILE *outputfile, struct diff3_block *diff,
1491                        int const mapping[3], int const rev_mapping[3],
1492                        char const *file0, char const *file1, char const *file2)
1493 {
1494   bool leading_dot;
1495   bool conflicts_found = false;
1496   bool conflict;
1497   struct diff3_block *b;
1498
1499   for (b = reverse_diff3_blocklist (diff); b; b = b->next)
1500     {
1501       /* Must do mapping correctly.  */
1502       enum diff_type type
1503         = (b->correspond == DIFF_ALL
1504            ? DIFF_ALL
1505            : DIFF_1ST + rev_mapping[b->correspond - DIFF_1ST]);
1506
1507       long int low0, high0;
1508
1509       /* If we aren't supposed to do this output block, skip it.  */
1510       switch (type)
1511         {
1512         default: continue;
1513         case DIFF_2ND: if (!show_2nd) continue; conflict = true; break;
1514         case DIFF_3RD: if (overlap_only) continue; conflict = false; break;
1515         case DIFF_ALL: if (simple_only) continue; conflict = flagging; break;
1516         }
1517
1518       low0 = D_LOWLINE (b, mapping[FILE0]);
1519       high0 = D_HIGHLINE (b, mapping[FILE0]);
1520
1521       if (conflict)
1522         {
1523           conflicts_found = true;
1524
1525
1526           /* Mark end of conflict.  */
1527
1528           fprintf (outputfile, "%lda\n", high0);
1529           leading_dot = false;
1530           if (type == DIFF_ALL)
1531             {
1532               if (show_2nd)
1533                 {
1534                   /* Append lines from FILE1.  */
1535                   fprintf (outputfile, "||||||| %s\n", file1);
1536                   leading_dot = dotlines (outputfile, b, mapping[FILE1]);
1537                 }
1538               /* Append lines from FILE2.  */
1539               fputs ("=======\n", outputfile);
1540               leading_dot |= dotlines (outputfile, b, mapping[FILE2]);
1541             }
1542           fprintf (outputfile, ">>>>>>> %s\n", file2);
1543           undotlines (outputfile, leading_dot, high0 + 2,
1544                       (D_NUMLINES (b, mapping[FILE1])
1545                        + D_NUMLINES (b, mapping[FILE2]) + 1));
1546
1547
1548           /* Mark start of conflict.  */
1549
1550           fprintf (outputfile, "%lda\n<<<<<<< %s\n", low0 - 1,
1551                    type == DIFF_ALL ? file0 : file1);
1552           leading_dot = false;
1553           if (type == DIFF_2ND)
1554             {
1555               /* Prepend lines from FILE1.  */
1556               leading_dot = dotlines (outputfile, b, mapping[FILE1]);
1557               fputs ("=======\n", outputfile);
1558             }
1559           undotlines (outputfile, leading_dot, low0 + 1,
1560                       D_NUMLINES (b, mapping[FILE1]));
1561         }
1562       else if (D_NUMLINES (b, mapping[FILE2]) == 0)
1563         /* Write out a delete */
1564         {
1565           if (low0 == high0)
1566             fprintf (outputfile, "%ldd\n", low0);
1567           else
1568             fprintf (outputfile, "%ld,%ldd\n", low0, high0);
1569         }
1570       else
1571         /* Write out an add or change */
1572         {
1573           switch (high0 - low0)
1574             {
1575             case -1:
1576               fprintf (outputfile, "%lda\n", high0);
1577               break;
1578             case 0:
1579               fprintf (outputfile, "%ldc\n", high0);
1580               break;
1581             default:
1582               fprintf (outputfile, "%ld,%ldc\n", low0, high0);
1583               break;
1584             }
1585
1586           undotlines (outputfile, dotlines (outputfile, b, mapping[FILE2]),
1587                       low0, D_NUMLINES (b, mapping[FILE2]));
1588         }
1589     }
1590   if (finalwrite)
1591     fputs ("w\nq\n", outputfile);
1592   return conflicts_found;
1593 }
1594
1595 /* Read from INFILE and output to OUTPUTFILE a set of diff3_blocks
1596    DIFF as a merged file.  This acts like 'ed file0
1597    <[output_diff3_edscript]', except that it works even for binary
1598    data or incomplete lines.
1599
1600    As before, MAPPING maps from arg list file number to diff file
1601    number, REV_MAPPING is its inverse, and FILE0, FILE1, and FILE2 are
1602    the names of the files.
1603
1604    Return 1 if conflicts were found.  */
1605
1606 static bool
1607 output_diff3_merge (FILE *infile, FILE *outputfile, struct diff3_block *diff,
1608                     int const mapping[3], int const rev_mapping[3],
1609                     char const *file0, char const *file1, char const *file2)
1610 {
1611   int c;
1612   lin i;
1613   bool conflicts_found = false;
1614   bool conflict;
1615   struct diff3_block *b;
1616   lin linesread = 0;
1617
1618   for (b = diff; b; b = b->next)
1619     {
1620       /* Must do mapping correctly.  */
1621       enum diff_type type
1622         = ((b->correspond == DIFF_ALL)
1623            ? DIFF_ALL
1624            : DIFF_1ST + rev_mapping[b->correspond - DIFF_1ST]);
1625       char const *format_2nd = "<<<<<<< %s\n";
1626
1627       /* If we aren't supposed to do this output block, skip it.  */
1628       switch (type)
1629         {
1630         default: continue;
1631         case DIFF_2ND: if (!show_2nd) continue; conflict = true; break;
1632         case DIFF_3RD: if (overlap_only) continue; conflict = false; break;
1633         case DIFF_ALL: if (simple_only) continue; conflict = flagging;
1634           format_2nd = "||||||| %s\n";
1635           break;
1636         }
1637
1638       /* Copy I lines from file 0.  */
1639       i = D_LOWLINE (b, FILE0) - linesread - 1;
1640       linesread += i;
1641       while (0 <= --i)
1642         do
1643           {
1644             c = getc (infile);
1645             if (c == EOF)
1646               {
1647                 if (ferror (infile))
1648                   perror_with_exit (_("read failed"));
1649                 else if (feof (infile))
1650                   fatal ("input file shrank");
1651               }
1652             putc (c, outputfile);
1653           }
1654         while (c != '\n');
1655
1656       if (conflict)
1657         {
1658           conflicts_found = true;
1659
1660           if (type == DIFF_ALL)
1661             {
1662               /* Put in lines from FILE0 with bracket.  */
1663               fprintf (outputfile, "<<<<<<< %s\n", file0);
1664               for (i = 0;
1665                    i < D_NUMLINES (b, mapping[FILE0]);
1666                    i++)
1667                 fwrite (D_RELNUM (b, mapping[FILE0], i), sizeof (char),
1668                         D_RELLEN (b, mapping[FILE0], i), outputfile);
1669             }
1670
1671           if (show_2nd)
1672             {
1673               /* Put in lines from FILE1 with bracket.  */
1674               fprintf (outputfile, format_2nd, file1);
1675               for (i = 0;
1676                    i < D_NUMLINES (b, mapping[FILE1]);
1677                    i++)
1678                 fwrite (D_RELNUM (b, mapping[FILE1], i), sizeof (char),
1679                         D_RELLEN (b, mapping[FILE1], i), outputfile);
1680             }
1681
1682           fputs ("=======\n", outputfile);
1683         }
1684
1685       /* Put in lines from FILE2.  */
1686       for (i = 0;
1687            i < D_NUMLINES (b, mapping[FILE2]);
1688            i++)
1689         fwrite (D_RELNUM (b, mapping[FILE2], i), sizeof (char),
1690                 D_RELLEN (b, mapping[FILE2], i), outputfile);
1691
1692       if (conflict)
1693         fprintf (outputfile, ">>>>>>> %s\n", file2);
1694
1695       /* Skip I lines in file 0.  */
1696       i = D_NUMLINES (b, FILE0);
1697       linesread += i;
1698       while (0 <= --i)
1699         while ((c = getc (infile)) != '\n')
1700           if (c == EOF)
1701             {
1702               if (ferror (infile))
1703                 perror_with_exit (_("read failed"));
1704               else if (feof (infile))
1705                 {
1706                   if (i || b->next)
1707                     fatal ("input file shrank");
1708                   return conflicts_found;
1709                 }
1710             }
1711     }
1712   /* Copy rest of common file.  */
1713   while ((c = getc (infile)) != EOF || !(ferror (infile) | feof (infile)))
1714     putc (c, outputfile);
1715   return conflicts_found;
1716 }
1717
1718 /* Reverse the order of the list of diff3 blocks.  */
1719
1720 static struct diff3_block *
1721 reverse_diff3_blocklist (struct diff3_block *diff)
1722 {
1723   register struct diff3_block *tmp, *next, *prev;
1724
1725   for (tmp = diff, prev = 0;  tmp;  tmp = next)
1726     {
1727       next = tmp->next;
1728       tmp->next = prev;
1729       prev = tmp;
1730     }
1731
1732   return prev;
1733 }
1734 \f
1735 static void
1736 fatal (char const *msgid)
1737 {
1738   error (EXIT_TROUBLE, 0, "%s", _(msgid));
1739   abort ();
1740 }
1741
1742 static void
1743 perror_with_exit (char const *string)
1744 {
1745   error (EXIT_TROUBLE, errno, "%s", string);
1746   abort ();
1747 }