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