contrib/diffutils-2.8/src/diff3.c

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