diff3.c

制作2.6内核的CLFS时 使用的diffutils-2.8.7.tar.gz包

  N_("-T  --initial-tab  Make tabs line up by prepending a tab."),
  N_("--diff-program=PROGRAM  Use PROGRAM to compare files."),
  "",
  N_("-v  --version  Output version info."),
  N_("--help  Output this help."),
  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."));
  for (p = option_help_msgid;  *p;  p++)
    if (**p)
      printf ("  %s\n", _(*p));
    else
      putchar ('\n');
  printf ("\n%s\n%s\n\n%s\n",
	  _("If a FILE is `-', read standard input."),
	  _("Exit status is 0 if successful, 1 if conflicts, 2 if trouble."),
	  _("Report bugs to <[e-mail]>."));
}

/* 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_diff = other_diff;
	      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;

  while (copynum--)
    {
      if (*t)
	{
	  if (*fl != *tl || memcmp (*f, *t, *fl) != 0)
	    return false;
	}
      else
	{
	  *t = *f;
	  *tl = *fl;
	}

      t++; f++; tl++; fl++;
    }

  return true;
}

/* Create a diff3_block, with ranges as specified in the arguments.
   Allocate the arrays for the various pointers (and zero them) based
   on the arguments passed.  Return the block as a result.  */

static struct diff3_block *
create_diff3_block (lin low0, lin high0,
		    lin low1, lin high1,
		    lin low2, lin high2)
{
  struct diff3_block *result = xmalloc (sizeof *result);
  lin numlines;

  D3_TYPE (result) = ERROR;
  D_NEXT (result) = 0;

  /* Assign ranges */
  D_LOWLINE (result, FILE0) = low0;
  D_HIGHLINE (result, FILE0) = high0;
  D_LOWLINE (result, FILE1) = low1;
  D_HIGHLINE (result, FILE1) = high1;
  D_LOWLINE (result, FILE2) = low2;
  D_HIGHLINE (result, FILE2) = high2;

  /* Allocate and zero space */
  numlines = D_NUMLINES (result, FILE0);
  if (numlines)
    {
      D_LINEARRAY (result, FILE0) = xcalloc (numlines, sizeof (char *));
      D_LENARRAY (result, FILE0) = xcalloc (numlines, sizeof (size_t));
    }
  else
    {
      D_LINEARRAY (result, FILE0) = 0;
      D_LENARRAY (result, FILE0) = 0;
    }

  numlines = D_NUMLINES (result, FILE1);
  if (numlines)
    {
      D_LINEARRAY (result, FILE1) = xcalloc (numlines, sizeof (char *));
      D_LENARRAY (result, FILE1) = xcalloc (numlines, sizeof (size_t));
    }