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