diff3.c

这是一个同样来自贝尔实验室的和UNIX有着渊源的操作系统, 其简洁的设计和实现易于我们学习和理解

/* Three way file comparison program (diff3) for Project GNU.
   Copyright (C) 1988, 1989, 1992, 1993, 1994 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 2, 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, write to the Free Software
   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */

/* Written by Randy Smith */

#include "system.h"
#include <stdio.h>
#include <signal.h>
#include "getopt.h"

extern char const version_string[];

/*
 * 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	START	0
#define	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 {
  int 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;
};

/* Three way diff */

struct diff3_block {
  enum diff_type correspond;	/* Type of diff */
  int 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][START])
#define	D_HIGHLINE(diff, filenum)	\
  ((diff)->ranges[filenum][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, lineno)	\
  ((lineno)						\
   - D_HIGHLINE ((diff), (fromfile))			\
   + D_HIGHLINE ((diff), (tofile)))

#define	D_LOW_MAPLINE(diff, fromfile, tofile, lineno)	\
  ((lineno)						\
   - D_LOWLINE ((diff), (fromfile))			\
   + D_LOWLINE ((diff), (tofile)))

/*
 * General memory allocation function.
 */
#define	ALLOCATE(number, type)	\
  (type *) xmalloc ((number) * sizeof (type))

/* Options variables for flags set on command line.  */

/* If nonzero, treat all files as text files, never as binary.  */
static int always_text;

/* If nonzero, write out an ed script instead of the standard diff3 format.  */
static int 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 int flagging;

/* Number of lines to keep in identical prefix and suffix.  */
static int horizon_lines = 10;

/* Use a tab to align output lines (-T).  */
static int tab_align_flag;

/* If nonzero, do not output information for overlapping diffs.  */
static int simple_only;

/* If nonzero, do not output information for non-overlapping diffs.  */
static int overlap_only;

/* If nonzero, show information for DIFF_2ND diffs.  */
static int show_2nd;

/* If nonzero, include `:wq' at the end of the script
   to write out the file being edited.   */
static int finalwrite;

/* If nonzero, output a merged file.  */
static int merge;

static char *program_name;

static VOID *xmalloc PARAMS((size_t));
static VOID *xrealloc PARAMS((VOID *, size_t));

static char *read_diff PARAMS((char const *, char const *, char **));
static char *scan_diff_line PARAMS((char *, char **, size_t *, char *, int));
static enum diff_type process_diff_control PARAMS((char **, struct diff_block *));
static int compare_line_list PARAMS((char * const[], size_t const[], char * const[], size_t const[], int));
static int copy_stringlist PARAMS((char * const[], size_t const[], char *[], size_t[], int));
static int dotlines PARAMS((FILE *, struct diff3_block *, int));
static int output_diff3_edscript PARAMS((FILE *, struct diff3_block *, int const[3], int const[3], char const *, char const *, char const *));
static int output_diff3_merge PARAMS((FILE *, FILE *, struct diff3_block *, int const[3], int const[3], char const *, char const *, char const *));
static size_t myread PARAMS((int, char *, size_t));
static struct diff3_block *create_diff3_block PARAMS((int, int, int, int, int, int));
static struct diff3_block *make_3way_diff PARAMS((struct diff_block *, struct diff_block *));
static struct diff3_block *reverse_diff3_blocklist PARAMS((struct diff3_block *));
static struct diff3_block *using_to_diff3_block PARAMS((struct diff_block *[2], struct diff_block *[2], int, int, struct diff3_block const *));
static struct diff_block *process_diff PARAMS((char const *, char const *, struct diff_block **));
static void check_stdout PARAMS((void));
static void fatal PARAMS((char const *));
static void output_diff3 PARAMS((FILE *, struct diff3_block *, int const[3], int const[3]));
static void perror_with_exit PARAMS((char const *));
static void try_help PARAMS((char const *));
static void undotlines PARAMS((FILE *, int, int, int));
static void usage PARAMS((void));

static char const diff_program[] = DIFF_PROGRAM;

static struct option const longopts[] =
{
  {"text", 0, 0, 'a'},
  {"show-all", 0, 0, 'A'},
  {"ed", 0, 0, 'e'},
  {"show-overlap", 0, 0, 'E'},
  {"label", 1, 0, 'L'},
  {"merge", 0, 0, 'm'},
  {"initial-tab", 0, 0, 'T'},
  {"overlap-only", 0, 0, 'x'},
  {"easy-only", 0, 0, '3'},
  {"version", 0, 0, 'v'},
  {"help", 0, 0, 129},
  {0, 0, 0, 0}
};

/*
 * Main program.  Calls diff twice on two pairs of input files,
 * combines the two diffs, and outputs them.
 */
int
main (argc, argv)
     int argc;
     char **argv;
{
  int c, i;
  int mapping[3];
  int rev_mapping[3];
  int incompat = 0;
  int 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;

  initialize_main (&argc, &argv);
  program_name = argv[0];

  while ((c = getopt_long (argc, argv, "aeimvx3AEL:TX", longopts, 0)) != EOF)
    {
      switch (c)
	{
	case 'a':
	  always_text = 1;
	  break;
	case 'A':
	  show_2nd = 1;
	  flagging = 1;
	  incompat++;
	  break;
	case 'x':
	  overlap_only = 1;
	  incompat++;
	  break;
	case '3':
	  simple_only = 1;
	  incompat++;
	  break;
	case 'i':
	  finalwrite = 1;
	  break;
	case 'm':
	  merge = 1;
	  break;
	case 'X':
	  overlap_only = 1;
	  /* Falls through */
	case 'E':
	  flagging = 1;
	  /* Falls through */
	case 'e':
	  incompat++;
	  break;
	case 'T':
	  tab_align_flag = 1;
	  break;
	case 'v':
	  printf ("diff3 - GNU diffutils version %s\n", version_string);
	  exit (0);
	case 129:
	  usage ();
	  check_stdout ();
	  exit (0);
	case 'L':
	  /* Handle up to three -L options.  */
	  if (tag_count < 3)
	    {
	      tag_strings[tag_count++] = optarg;
	      break;
	    }
	  try_help ("Too many labels were given.  The limit is 3.");
	default:
	  try_help (0);
	}
    }

  edscript = incompat & ~merge;  /* -AeExX3 without -m implies ed script.  */
  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");

  if (argc - optind != 3)
    try_help (argc - optind < 3 ? "missing operand" : "extra operand");

  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.  */

  if (strcmp (file[2], "-") == 0)
    {
      /* Sigh.  We've got standard input as the last arg.  We can't
	 call diff twice on stdin.  Use the middle arg as the common
	 file instead.  */
      if (strcmp (file[0], "-") == 0 || strcmp (file[1], "-") == 0)
	fatal ("`-' specified for more than one input file");
      mapping[0] = 0;
      mapping[1] = 2;
      mapping[2] = 1;
    }
  else
    {
      /* Normal, what you'd expect */
      mapping[0] = 0;
      mapping[1] = 1;
      mapping[2] = 2;
    }

  for (i = 0; i < 3; i++)
    rev_mapping[mapping[i]] = i;

  for (i = 0; i < 3; i++)
    if (strcmp (file[i], "-") != 0)
      {
	if (stat (file[i], &statb) < 0)
	  perror_with_exit (file[i]);
	else if (S_ISDIR(statb.st_mode))
	  {
	    fprintf (stderr, "%s: %s: Is a directory\n",
		     program_name, file[i]);
	    exit (2);
	  }
      }

#if !defined(SIGCHLD) && defined(SIGCLD)
#define SIGCHLD SIGCLD
#endif
#ifdef SIGCHLD
  /* System V fork+wait does not work if SIGCHLD is ignored.  */
  signal (SIGCHLD, SIG_DFL);
#endif

  commonname = file[rev_mapping[FILEC]];
  thread1 = process_diff (file[rev_mapping[FILE1]], commonname, &last_block);
  if (thread1)
    for (i = 0; i < 2; i++)
      {
	horizon_lines = max (horizon_lines, D_NUMLINES (thread1, i));
	horizon_lines = max (horizon_lines, D_NUMLINES (last_block, i));
      }
  thread0 = process_diff (file[rev_mapping[FILE0]], commonname, &last_block);
  diff3 = make_3way_diff (thread0, 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)
    {
      if (! freopen (file[rev_mapping[FILE0]], "r", stdin))
	perror_with_exit (file[rev_mapping[FILE0]]);
      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 error");
    }
  else
    {
      output_diff3 (stdout, diff3, mapping, rev_mapping);
      conflicts_found = 0;
    }

  check_stdout ();
  exit (conflicts_found);
  return conflicts_found;
}

static void
try_help (reason)
     char const *reason;
{
  if (reason)
    fprintf (stderr, "%s: %s\n", program_name, reason);
  fprintf (stderr, "%s: Try `%s --help' for more information.\n",
	   program_name, program_name);
  exit (2);
}

static void
check_stdout ()
{
  if (ferror (stdout) || fclose (stdout) != 0)
    fatal ("write error");
}

/*
 * Explain, patiently and kindly, how to use this program.
 */
static void
usage ()
{
  printf ("Usage: %s [OPTION]... MYFILE OLDFILE YOURFILE\n\n", program_name);

  printf ("%s", "\
  -e  --ed  Output unmerged changes from OLDFILE to YOURFILE into MYFILE.\n\
  -E  --show-overlap  Output unmerged changes, bracketing conflicts.\n\
  -A  --show-all  Output all changes, bracketing conflicts.\n\
  -x  --overlap-only  Output overlapping changes.\n\
  -X  Output overlapping changes, bracketing them.\n\
  -3  --easy-only  Output unmerged nonoverlapping changes.\n\n");
  printf ("%s", "\
  -m  --merge  Output merged file instead of ed script (default -A).\n\
  -L LABEL  --label=LABEL  Use LABEL instead of file name.\n\
  -i  Append `w' and `q' commands to ed scripts.\n\
  -a  --text  Treat all files as text.\n\
  -T  --initial-tab  Make tabs line up by prepending a tab.\n\n");
  printf ("%s", "\