/* diff3 - compare three files line by line

   Copyright (C) 1988-1989, 1992-1996, 1998, 2001-2002, 2004, 2006, 2009-2013,

   2015-2017 Free Software Foundation, Inc.

   This program is free software: you can redistribute it and/or modify

   it under the terms of the GNU General Public License as published by

   the Free Software Foundation, either version 3 of the License, or

   (at your option) any later version.

   This program is distributed in the hope that it will be useful,

   but WITHOUT ANY WARRANTY; without even the implied warranty of

   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License

   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */

#include "system.h"

#include "paths.h"

#include <stdio.h>

#include <unlocked-io.h>

#include <c-stack.h>

#include <cmpbuf.h>

#include "die.h"

#include <error.h>

#include <exitfail.h>

#include <file-type.h>

#include <getopt.h>

#include <progname.h>

#include <system-quote.h>

#include <version-etc.h>

#include <xalloc.h>

#include <xfreopen.h>

/* The official name of this program (e.g., no 'g' prefix).  */

#define PROGRAM_NAME "diff3"

#define AUTHORS \

  proper_name ("Randy Smith")

/* Internal data structures and macros for the diff3 program; includes

   data structures for both diff3 diffs and normal diffs.  */

/* Different files within a three way diff.  */

#define	FILE0	0

#define	FILE1	1

#define	FILE2	2

/* A three way diff is built from two two-way diffs; the file which

   the two two-way diffs share is:  */

#define	FILEC	FILE2

/* Different files within a two way diff.

   FC is the common file, FO the other file.  */

#define FO 0

#define FC 1

/* The ranges are indexed by */

#define	RANGE_START	0

#define	RANGE_END	1

enum diff_type {

  ERROR,			/* Should not be used */

  ADD,				/* Two way diff add */

  CHANGE,			/* Two way diff change */

  DELETE,			/* Two way diff delete */

  DIFF_ALL,			/* All three are different */

  DIFF_1ST,			/* Only the first is different */

  DIFF_2ND,			/* Only the second */

  DIFF_3RD			/* Only the third */

};

/* Two way diff */

struct diff_block {

  lin ranges[2][2];		/* Ranges are inclusive */

  char **lines[2];		/* The actual lines (may contain nulls) */

  size_t *lengths[2];		/* Line lengths (including newlines, if any) */

  struct diff_block *next;

#ifdef lint

  struct diff_block *n2;	/* Used only when freeing.  */

#endif

};

/* Three way diff */

struct diff3_block {

  enum diff_type correspond;	/* Type of diff */

  lin ranges[3][2];		/* Ranges are inclusive */

  char **lines[3];		/* The actual lines (may contain nulls) */

  size_t *lengths[3];		/* Line lengths (including newlines, if any) */

  struct diff3_block *next;

};

/* Access the ranges on a diff block.  */

#define	D_LOWLINE(diff, filenum)	\

  ((diff)->ranges[filenum][RANGE_START])

#define	D_HIGHLINE(diff, filenum)	\

  ((diff)->ranges[filenum][RANGE_END])

#define	D_NUMLINES(diff, filenum)	\

  (D_HIGHLINE (diff, filenum) - D_LOWLINE (diff, filenum) + 1)

/* Access the line numbers in a file in a diff by relative line

   numbers (i.e. line number within the diff itself).  Note that these

   are lvalues and can be used for assignment.  */

#define	D_RELNUM(diff, filenum, linenum)	\

  ((diff)->lines[filenum][linenum])

#define	D_RELLEN(diff, filenum, linenum)	\

  ((diff)->lengths[filenum][linenum])

/* And get at them directly, when that should be necessary.  */

#define	D_LINEARRAY(diff, filenum)	\

  ((diff)->lines[filenum])

#define	D_LENARRAY(diff, filenum)	\

  ((diff)->lengths[filenum])

/* Next block.  */

#define	D_NEXT(diff)	((diff)->next)

/* Access the type of a diff3 block.  */

#define	D3_TYPE(diff)	((diff)->correspond)

/* Line mappings based on diffs.  The first maps off the top of the

   diff, the second off of the bottom.  */

#define	D_HIGH_MAPLINE(diff, fromfile, tofile, linenum)	\

  ((linenum)						\

   - D_HIGHLINE ((diff), (fromfile))			\

   + D_HIGHLINE ((diff), (tofile)))

#define	D_LOW_MAPLINE(diff, fromfile, tofile, linenum)	\

  ((linenum)						\

   - D_LOWLINE ((diff), (fromfile))			\

   + D_LOWLINE ((diff), (tofile)))

/* Options variables for flags set on command line.  */

/* If nonzero, treat all files as text files, never as binary.  */

static bool text;

/* Remove trailing carriage returns from input.  */

static bool strip_trailing_cr;

/* If nonzero, write out an ed script instead of the standard diff3 format.  */

static bool edscript;

/* If nonzero, in the case of overlapping diffs (type DIFF_ALL),

   preserve the lines which would normally be deleted from

   file 1 with a special flagging mechanism.  */

static bool flagging;

/* Use a tab to align output lines (-T).  */

static bool initial_tab;

/* If nonzero, do not output information for overlapping diffs.  */

static bool simple_only;

/* If nonzero, do not output information for non-overlapping diffs.  */

static bool overlap_only;

/* If nonzero, show information for DIFF_2ND diffs.  */

static bool show_2nd;

/* If nonzero, include ':wq' at the end of the script

   to write out the file being edited.   */

static bool finalwrite;

/* If nonzero, output a merged file.  */

static bool merge;

static char *read_diff (char const *, char const *, char **);

static char *scan_diff_line (char *, char **, size_t *, char *, char);

static enum diff_type process_diff_control (char **, struct diff_block *);

static bool compare_line_list (char * const[], size_t const[], char * const[], size_t const[], lin);

static bool copy_stringlist (char * const[], size_t const[], char *[], size_t[], lin);

static bool output_diff3_edscript (FILE *, struct diff3_block *, int const[3], int const[3], char const *, char const *, char const *);

static bool output_diff3_merge (FILE *, FILE *, struct diff3_block *, int const[3], int const[3], char const *, char const *, char const *);

static struct diff3_block *create_diff3_block (lin, lin, lin, lin, lin, lin);

static struct diff3_block *make_3way_diff (struct diff_block *, struct diff_block *);

static struct diff3_block *reverse_diff3_blocklist (struct diff3_block *);

static struct diff3_block *using_to_diff3_block (struct diff_block *[2], struct diff_block *[2], int, int, struct diff3_block const *);

static struct diff_block *process_diff (char const *, char const *, struct diff_block **, char **);

static void check_stdout (void);

static void fatal (char const *) __attribute__((noreturn));

static void output_diff3 (FILE *, struct diff3_block *, int const[3], int const[3]);

static void perror_with_exit (char const *) __attribute__((noreturn));

static void try_help (char const *, char const *) __attribute__((noreturn));

static void usage (void);

static char const *diff_program = DEFAULT_DIFF_PROGRAM;

/* Values for long options that do not have single-letter equivalents.  */

enum

{

  DIFF_PROGRAM_OPTION = CHAR_MAX + 1,

  HELP_OPTION,

  STRIP_TRAILING_CR_OPTION

};

static struct option const longopts[] =

{

  {"diff-program", 1, 0, DIFF_PROGRAM_OPTION},

  {"easy-only", 0, 0, '3'},

  {"ed", 0, 0, 'e'},

  {"help", 0, 0, HELP_OPTION},

  {"initial-tab", 0, 0, 'T'},

  {"label", 1, 0, 'L'},

  {"merge", 0, 0, 'm'},

  {"overlap-only", 0, 0, 'x'},

  {"show-all", 0, 0, 'A'},

  {"show-overlap", 0, 0, 'E'},

  {"strip-trailing-cr", 0, 0, STRIP_TRAILING_CR_OPTION},

  {"text", 0, 0, 'a'},

  {"version", 0, 0, 'v'},

  {0, 0, 0, 0}

};

static void

free_diff_block (struct diff_block *p)

{

#ifndef lint

  (void)p;

#else

  while (p)

    {

      free (p->lines[0]);

      free (p->lines[1]);

      free (p->lengths[0]);

      free (p->lengths[1]);

      struct diff_block *next = p->n2;

      free (p);

      p = next;

    }

#endif

}

/* Copy each next pointer to n2, since make_3way_diff would clobber the former,

   yet we will still need something to free these buffers.  */

static void

next_to_n2 (struct diff_block *p)

{

#ifndef lint

  (void)p;

#else

  while (p)

    p = p->n2 = p->next;

#endif

}

int

main (int argc, char **argv)

{

  int c, i;

  int common;

  int mapping[3];

  int rev_mapping[3];

  int incompat = 0;

  bool conflicts_found;

  struct diff_block *thread0, *thread1, *last_block;

  struct diff3_block *diff3;

  int tag_count = 0;

  char *tag_strings[3];

  char *commonname;

  char **file;

  struct stat statb;

  exit_failure = EXIT_TROUBLE;

  initialize_main (&argc, &argv);

  set_program_name (argv[0]);

  setlocale (LC_ALL, "");

  bindtextdomain (PACKAGE, LOCALEDIR);

  textdomain (PACKAGE);

  c_stack_action (0);

  while ((c = getopt_long (argc, argv, "aeimvx3AEL:TX", longopts, 0)) != -1)

    {

      switch (c)

	{

	case 'a':

	  text = true;

	  break;

	case 'A':

	  show_2nd = true;

	  flagging = true;

	  incompat++;

	  break;

	case 'x':

	  overlap_only = true;

	  incompat++;

	  break;

	case '3':

	  simple_only = true;

	  incompat++;

	  break;

	case 'i':

	  finalwrite = true;

	  break;

	case 'm':

	  merge = true;

	  break;

	case 'X':

	  overlap_only = true;

	  FALLTHROUGH;

	case 'E':

	  flagging = true;

	  FALLTHROUGH;

	case 'e':

	  incompat++;

	  break;

	case 'T':

	  initial_tab = true;

	  break;

	case STRIP_TRAILING_CR_OPTION:

	  strip_trailing_cr = true;

	  break;

	case 'v':

	  version_etc (stdout, PROGRAM_NAME, PACKAGE_NAME, Version,

		       AUTHORS, (char *) NULL);

	  check_stdout ();

	  return EXIT_SUCCESS;

	case DIFF_PROGRAM_OPTION:

	  diff_program = optarg;

	  break;

	case HELP_OPTION:

	  usage ();

	  check_stdout ();

	  return EXIT_SUCCESS;

	case 'L':

	  /* Handle up to three -L options.  */

	  if (tag_count < 3)

	    {

	      tag_strings[tag_count++] = optarg;

	      break;

	    }

	  try_help ("too many file label options", 0);

	default:

	  try_help (0, 0);

	}

    }

  /* -AeExX3 without -m implies ed script.  */

  edscript = incompat & ~(int) merge;

  show_2nd |= ~incompat & merge;  /* -m without -AeExX3 implies -A.  */

  flagging |= ~incompat & merge;

  if (incompat > 1  /* Ensure at most one of -AeExX3.  */

      || finalwrite & merge /* -i -m would rewrite input file.  */

      || (tag_count && ! flagging)) /* -L requires one of -AEX.  */

    try_help ("incompatible options", 0);

  if (argc - optind != 3)

    {

      if (argc - optind < 3)

	try_help ("missing operand after '%s'", argv[argc - 1]);

      else

	try_help ("extra operand '%s'", argv[optind + 3]);

    }

  file = &argv[optind];

  for (i = tag_count; i < 3; i++)

    tag_strings[i] = file[i];

  /* Always compare file1 to file2, even if file2 is "-".

     This is needed for -mAeExX3.  Using the file0 as

     the common file would produce wrong results, because if the

     file0-file1 diffs didn't line up with the file0-file2 diffs

     (which is entirely possible since we don't use diff's -n option),

     diff3 might report phantom changes from file1 to file2.

     Also, try to compare file0 to file1, because this is where

     changes are expected to come from.  Diffing between these pairs

     of files is more likely to avoid phantom changes from file0 to file1.

     Historically, the default common file was file2, so some older

     applications (e.g. Emacs ediff) used file2 as the ancestor.  So,

     for compatibility, if this is a 3-way diff (not a merge or

     edscript), prefer file2 as the common file.  */

  common = 2 - (edscript | merge);

  if (STREQ (file[common], "-"))

    {

      /* Sigh.  We've got standard input as the common file.  We can't

	 call diff twice on stdin.  Use the other arg as the common

	 file instead.  */

      common = 3 - common;

      if (STREQ (file[0], "-") || STREQ (file[common], "-"))

	fatal ("'-' specified for more than one input file");

    }

  mapping[0] = 0;

  mapping[1] = 3 - common;

  mapping[2] = common;

  for (i = 0; i < 3; i++)

    rev_mapping[mapping[i]] = i;

  for (i = 0; i < 3; i++)

    if (! STREQ (file[i], "-"))

      {

	if (stat (file[i], &statb) < 0)

	  perror_with_exit (file[i]);

	else if (S_ISDIR (statb.st_mode))

	  die (EXIT_TROUBLE, EISDIR, "%s", file[i]);

      }

#ifdef SIGCHLD

  /* System V fork+wait does not work if SIGCHLD is ignored.  */

  signal (SIGCHLD, SIG_DFL);

#endif

  /* Invoke diff twice on two pairs of input files, combine the two

     diffs, and output them.  */

  char *b0, *b1;

  commonname = file[rev_mapping[FILEC]];

  thread1 = process_diff (file[rev_mapping[FILE1]], commonname, &last_block, &b1;;

  thread0 = process_diff (file[rev_mapping[FILE0]], commonname, &last_block, &b0;;

  next_to_n2 (thread0);

  next_to_n2 (thread1);

  diff3 = make_3way_diff (thread0, thread1);

  free_diff_block (thread0);

  free_diff_block (thread1);

  if (edscript)

    conflicts_found

      = output_diff3_edscript (stdout, diff3, mapping, rev_mapping,

			       tag_strings[0], tag_strings[1], tag_strings[2]);

  else if (merge)

    {

      xfreopen (file[rev_mapping[FILE0]], "r", stdin);

      conflicts_found

	= output_diff3_merge (stdin, stdout, diff3, mapping, rev_mapping,

			      tag_strings[0], tag_strings[1], tag_strings[2]);

      if (ferror (stdin))

	fatal ("read failed");

    }

  else

    {

      output_diff3 (stdout, diff3, mapping, rev_mapping);

      conflicts_found = false;

    }

  free (b0);

  free (b1);

  check_stdout ();

  exit (conflicts_found);

}

static void

try_help (char const *reason_msgid, char const *operand)

{

  if (reason_msgid)

    error (0, 0, _(reason_msgid), operand);

  die (EXIT_TROUBLE, 0,

	 _("Try '%s --help' for more information."), program_name);

}

static void

check_stdout (void)

{

  if (ferror (stdout))

    fatal ("write failed");

  else if (fclose (stdout) != 0)

    perror_with_exit (_("standard output"));

}

static char const * const option_help_msgid[] = {

  N_("-A, --show-all              output all changes, bracketing conflicts"),

  "",

  N_("-e, --ed                    output ed script incorporating changes\n"

     "                                from OLDFILE to YOURFILE into MYFILE"),

  N_("-E, --show-overlap          like -e, but bracket conflicts"),

  N_("-3, --easy-only             like -e, but incorporate only nonoverlapping changes"),

  N_("-x, --overlap-only          like -e, but incorporate only overlapping changes"),

  N_("-X                          like -x, but bracket conflicts"),

  N_("-i                          append 'w' and 'q' commands to ed scripts"),

  "",

  N_("-m, --merge                 output actual merged file, according to\n"

     "                                -A if no other options are given"),

  "",

  N_("-a, --text                  treat all files as text"),

  N_("    --strip-trailing-cr     strip trailing carriage return on input"),

  N_("-T, --initial-tab           make tabs line up by prepending a tab"),

  N_("    --diff-program=PROGRAM  use PROGRAM to compare files"),

  N_("-L, --label=LABEL           use LABEL instead of file name\n"

     "                                (can be repeated up to three times)"),

  "",

  N_("    --help                  display this help and exit"),

  N_("-v, --version               output version information and exit"),

  0

};

static void

usage (void)

{

  char const * const *p;

  printf (_("Usage: %s [OPTION]... MYFILE OLDFILE YOURFILE\n"),

	  program_name);

  printf ("%s\n\n", _("Compare three files line by line."));

  fputs (_("\

Mandatory arguments to long options are mandatory for short options too.\n\

"), stdout);

  for (p = option_help_msgid;  *p;  p++)

    if (**p)

      printf ("  %s\n", _(*p));

    else

      putchar ('\n');

  fputs (_("\n\

The default output format is a somewhat human-readable representation of\n\

the changes.\n\

\n\

The -e, -E, -x, -X (and corresponding long) options cause an ed script\n\

to be output instead of the default.\n\

\n\

Finally, the -m (--merge) option causes diff3 to do the merge internally\n\

and output the actual merged file.  For unusual input, this is more\n\

robust than using ed.\n"), stdout);

  printf ("\n%s\n%s\n",

	  _("If a FILE is '-', read standard input."),

	  _("Exit status is 0 if successful, 1 if conflicts, 2 if trouble."));

  emit_bug_reporting_address ();

}

/* Combine the two diffs together into one.

   Here is the algorithm:

     File2 is shared in common between the two diffs.

     Diff02 is the diff between 0 and 2.

     Diff12 is the diff between 1 and 2.

	1) Find the range for the first block in File2.

	    a) Take the lowest of the two ranges (in File2) in the two

	       current blocks (one from each diff) as being the low

	       water mark.  Assign the upper end of this block as

	       being the high water mark and move the current block up

	       one.  Mark the block just moved over as to be used.

	    b) Check the next block in the diff that the high water

	       mark is *not* from.

	       *If* the high water mark is above

	       the low end of the range in that block,

		   mark that block as to be used and move the current

		   block up.  Set the high water mark to the max of

		   the high end of this block and the current.  Repeat b.

	 2) Find the corresponding ranges in File0 (from the blocks

	    in diff02; line per line outside of diffs) and in File1.

	    Create a diff3_block, reserving space as indicated by the ranges.

	 3) Copy all of the pointers for file2 in.  At least for now,

	    do memcmp's between corresponding strings in the two diffs.

	 4) Copy all of the pointers for file0 and 1 in.  Get what is

	    needed from file2 (when there isn't a diff block, it's

	    identical to file2 within the range between diff blocks).

	 5) If the diff blocks used came from only one of the two

	    strings of diffs, then that file (i.e. the one other than

	    the common file in that diff) is the odd person out.  If

	    diff blocks are used from both sets, check to see if files

	    0 and 1 match:

		Same number of lines?  If so, do a set of memcmp's (if

	    a memcmp matches; copy the pointer over; it'll be easier

	    later during comparisons).  If they match, 0 & 1 are the

	    same.  If not, all three different.

     Then do it again, until the blocks are exhausted.  */

/* Make a three way diff (chain of diff3_block's) from two two way

   diffs (chains of diff_block's).  Assume that each of the two diffs

   passed are onto the same file (i.e. that each of the diffs were

   made "to" the same file).  Return a three way diff pointer with

   numbering FILE0 = the other file in diff02, FILE1 = the other file

   in diff12, and FILEC = the common file.  */

static struct diff3_block *

make_3way_diff (struct diff_block *thread0, struct diff_block *thread1)

{

  /* Work on the two diffs passed to it as threads.  Thread number 0

     is diff02, thread number 1 is diff12.  USING is the base of the

     list of blocks to be used to construct each block of the three

     way diff; if no blocks from a particular thread are to be used,

     that element of USING is 0.  LAST_USING contains the last

     elements on each of the using lists.

     HIGH_WATER_MARK is the highest line number in the common file

     described in any of the diffs in either of the USING lists.

     HIGH_WATER_THREAD names the thread.  Similarly BASE_WATER_MARK

     and BASE_WATER_THREAD describe the lowest line number in the

     common file described in any of the diffs in either of the USING

     lists.  HIGH_WATER_DIFF is the diff from which the

     HIGH_WATER_MARK was taken.

     HIGH_WATER_DIFF should always be equal to

     LAST_USING[HIGH_WATER_THREAD].  OTHER_DIFF is the next diff to

     check for higher water, and should always be equal to

     CURRENT[HIGH_WATER_THREAD ^ 1].  OTHER_THREAD is the thread in

     which the OTHER_DIFF is, and hence should always be equal to

     HIGH_WATER_THREAD ^ 1.

     LAST_DIFF is the last diff block produced by this routine, for

     line correspondence purposes between that diff and the one

     currently being worked on.  It is ZERO_DIFF before any blocks

     have been created.  */

  struct diff_block *using[2];

  struct diff_block *last_using[2];

  struct diff_block *current[2];

  lin high_water_mark;

  int high_water_thread;

  int base_water_thread;

  int other_thread;

  struct diff_block *high_water_diff;

  struct diff_block *other_diff;

  struct diff3_block *result;

  struct diff3_block *tmpblock;

  struct diff3_block **result_end;

  struct diff3_block const *last_diff3;

  static struct diff3_block const zero_diff3;

  /* Initialization */

  result = 0;

  result_end = &result;

  current[0] = thread0; current[1] = thread1;

  last_diff3 = &zero_diff3;

  /* Sniff up the threads until we reach the end */

  while (current[0] || current[1])

    {

      using[0] = using[1] = last_using[0] = last_using[1] = 0;

      /* Setup low and high water threads, diffs, and marks.  */

      if (!current[0])

	base_water_thread = 1;

      else if (!current[1])

	base_water_thread = 0;

      else

	base_water_thread =

	  (D_LOWLINE (current[0], FC) > D_LOWLINE (current[1], FC));

      high_water_thread = base_water_thread;

      high_water_diff = current[high_water_thread];

      high_water_mark = D_HIGHLINE (high_water_diff, FC);

      /* Make the diff you just got info from into the using class */

      using[high_water_thread]

	= last_using[high_water_thread]

	= high_water_diff;

      current[high_water_thread] = high_water_diff->next;

      last_using[high_water_thread]->next = 0;

      /* And mark the other diff */

      other_thread = high_water_thread ^ 0x1;

      other_diff = current[other_thread];

      /* Shuffle up the ladder, checking the other diff to see if it

	 needs to be incorporated.  */

      while (other_diff

	     && D_LOWLINE (other_diff, FC) <= high_water_mark + 1)

	{

	  /* Incorporate this diff into the using list.  Note that

	     this doesn't take it off the current list */

	  if (using[other_thread])

	    last_using[other_thread]->next = other_diff;

	  else

	    using[other_thread] = other_diff;

	  last_using[other_thread] = other_diff;

	  /* Take it off the current list.  Note that this following

	     code assumes that other_diff enters it equal to

	     current[high_water_thread ^ 0x1] */

	  current[other_thread] = current[other_thread]->next;

	  other_diff->next = 0;

	  /* Set the high_water stuff

	     If this comparison is equal, then this is the last pass

	     through this loop; since diff blocks within a given

	     thread cannot overlap, the high_water_mark will be

	     *below* the range_start of either of the next diffs.  */

	  if (high_water_mark < D_HIGHLINE (other_diff, FC))

	    {

	      high_water_thread ^= 1;

	      high_water_mark = D_HIGHLINE (other_diff, FC);

	    }

	  /* Set the other diff */

	  other_thread = high_water_thread ^ 0x1;

	  other_diff = current[other_thread];

	}

      /* The using lists contain a list of all of the blocks to be

	 included in this diff3_block.  Create it.  */

      tmpblock = using_to_diff3_block (using, last_using,

				       base_water_thread, high_water_thread,

				       last_diff3);

      if (!tmpblock)

	fatal ("internal error: screwup in format of diff blocks");

      /* Put it on the list.  */

      *result_end = tmpblock;

      result_end = &tmpblock->next;

      /* Set up corresponding lines correctly.  */

      last_diff3 = tmpblock;

    }

  return result;

}

/* Take two lists of blocks (from two separate diff threads) and put

   them together into one diff3 block.  Return a pointer to this diff3

   block or 0 for failure.

   All arguments besides using are for the convenience of the routine;

   they could be derived from the using array.  LAST_USING is a pair

   of pointers to the last blocks in the using structure.  LOW_THREAD

   and HIGH_THREAD tell which threads contain the lowest and highest

   line numbers for File0.  LAST_DIFF3 contains the last diff produced

   in the calling routine.  This is used for lines mappings that

   would still be identical to the state that diff ended in.

   A distinction should be made in this routine between the two diffs

   that are part of a normal two diff block, and the three diffs that

   are part of a diff3_block.  */

static struct diff3_block *

using_to_diff3_block (struct diff_block *using[2],

		      struct diff_block *last_using[2],

		      int low_thread, int high_thread,

		      struct diff3_block const *last_diff3)

{

  lin low[2], high[2];

  struct diff3_block *result;

  struct diff_block *ptr;

  int d;

  lin i;

  /* Find the range in the common file.  */

  lin lowc = D_LOWLINE (using[low_thread], FC);

  lin highc = D_HIGHLINE (last_using[high_thread], FC);

  /* Find the ranges in the other files.

     If using[d] is null, that means that the file to which that diff

     refers is equivalent to the common file over this range.  */

  for (d = 0; d < 2; d++)

    if (using[d])

      {

	low[d] = D_LOW_MAPLINE (using[d], FC, FO, lowc);

	high[d] = D_HIGH_MAPLINE (last_using[d], FC, FO, highc);

      }

    else

      {

	low[d] = D_HIGH_MAPLINE (last_diff3, FILEC, FILE0 + d, lowc);

	high[d] = D_HIGH_MAPLINE (last_diff3, FILEC, FILE0 + d, highc);

      }

  /* Create a block with the appropriate sizes */

  result = create_diff3_block (low[0], high[0], low[1], high[1], lowc, highc);

  /* Copy information for the common file.

     Return with a zero if any of the compares failed.  */

  for (d = 0; d < 2; d++)

    for (ptr = using[d]; ptr; ptr = D_NEXT (ptr))

      {

	lin result_offset = D_LOWLINE (ptr, FC) - lowc;

	if (!copy_stringlist (D_LINEARRAY (ptr, FC),

			      D_LENARRAY (ptr, FC),

			      D_LINEARRAY (result, FILEC) + result_offset,

			      D_LENARRAY (result, FILEC) + result_offset,

			      D_NUMLINES (ptr, FC)))

	  return 0;

      }

  /* Copy information for file d.  First deal with anything that might be

     before the first diff.  */

  for (d = 0; d < 2; d++)

    {

      struct diff_block *u = using[d];

      lin lo = low[d], hi = high[d];

      for (i = 0;

	   i + lo < (u ? D_LOWLINE (u, FO) : hi + 1);

	   i++)

	{

	  D_RELNUM (result, FILE0 + d, i) = D_RELNUM (result, FILEC, i);

	  D_RELLEN (result, FILE0 + d, i) = D_RELLEN (result, FILEC, i);

	}

      for (ptr = u; ptr; ptr = D_NEXT (ptr))

	{

	  lin result_offset = D_LOWLINE (ptr, FO) - lo;

	  lin linec;

	  if (!copy_stringlist (D_LINEARRAY (ptr, FO),

				D_LENARRAY (ptr, FO),

				D_LINEARRAY (result, FILE0 + d) + result_offset,

				D_LENARRAY (result, FILE0 + d) + result_offset,

				D_NUMLINES (ptr, FO)))

	    return 0;

	  /* Catch the lines between here and the next diff */

	  linec = D_HIGHLINE (ptr, FC) + 1 - lowc;

	  for (i = D_HIGHLINE (ptr, FO) + 1 - lo;

	       i < (D_NEXT (ptr) ? D_LOWLINE (D_NEXT (ptr), FO) : hi + 1) - lo;

	       i++)

	    {

	      D_RELNUM (result, FILE0 + d, i) = D_RELNUM (result, FILEC, linec);

	      D_RELLEN (result, FILE0 + d, i) = D_RELLEN (result, FILEC, linec);

	      linec++;

	    }

	}

    }

  /* Set correspond */

  if (!using[0])

    D3_TYPE (result) = DIFF_2ND;

  else if (!using[1])

    D3_TYPE (result) = DIFF_1ST;

  else

    {

      lin nl0 = D_NUMLINES (result, FILE0);

      lin nl1 = D_NUMLINES (result, FILE1);

      if (nl0 != nl1

	  || !compare_line_list (D_LINEARRAY (result, FILE0),

				 D_LENARRAY (result, FILE0),

				 D_LINEARRAY (result, FILE1),

				 D_LENARRAY (result, FILE1),

				 nl0))

	D3_TYPE (result) = DIFF_ALL;

      else

	D3_TYPE (result) = DIFF_3RD;

    }

  return result;

}

/* Copy pointers from a list of strings to a different list of

   strings.  If a spot in the second list is already filled, make sure

   that it is filled with the same string; if not, return false, the copy

   incomplete.  Upon successful completion of the copy, return true.  */

static bool

copy_stringlist (char * const fromptrs[], size_t const fromlengths[],

		 char *toptrs[], size_t tolengths[],

		 lin copynum)

{

  register char * const *f = fromptrs;

  register char **t = toptrs;

  register size_t const *fl = fromlengths;

  register size_t *tl = tolengths;