diff3.c

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

  if (numlines)
    {
      D_LINEARRAY (result, FILE2) = ALLOCATE (numlines, char *);
      D_LENARRAY (result, FILE2) = ALLOCATE (numlines, size_t);
      bzero (D_LINEARRAY (result, FILE2), (numlines * sizeof (char *)));
      bzero (D_LENARRAY (result, FILE2), (numlines * sizeof (size_t)));
    }
  else
    {
      D_LINEARRAY (result, FILE2) = 0;
      D_LENARRAY (result, FILE2) = 0;
    }

  /* Return */
  return result;
}

/*
 * Compare two lists of lines of text.
 * Return 1 if they are equivalent, 0 if not.
 */
static int
compare_line_list (list1, lengths1, list2, lengths2, nl)
     char * const list1[], * const list2[];
     size_t const lengths1[], lengths2[];
     int nl;
{
  char
    * const *l1 = list1,
    * const *l2 = list2;
  size_t const
    *lgths1 = lengths1,
    *lgths2 = lengths2;

  while (nl--)
    if (!*l1 || !*l2 || *lgths1 != *lgths2++
	|| memcmp (*l1++, *l2++, *lgths1++))
      return 0;
  return 1;
}

/*
 * Routines to input and parse two way diffs.
 */

extern char **environ;

static struct diff_block *
process_diff (filea, fileb, last_block)
     char const *filea, *fileb;
     struct diff_block **last_block;
{
  char *diff_contents;
  char *diff_limit;
  char *scan_diff;
  enum diff_type dt;
  int i;
  struct diff_block *block_list, **block_list_end, *bptr;

  diff_limit = read_diff (filea, fileb, &diff_contents);
  scan_diff = diff_contents;
  block_list_end = &block_list;
  bptr = 0; /* Pacify `gcc -W'.  */

  while (scan_diff < diff_limit)
    {
      bptr = ALLOCATE (1, struct diff_block);
      bptr->lines[0] = bptr->lines[1] = 0;
      bptr->lengths[0] = bptr->lengths[1] = 0;

      dt = process_diff_control (&scan_diff, bptr);
      if (dt == ERROR || *scan_diff != '\n')
	{
	  fprintf (stderr, "%s: diff error: ", program_name);
	  do
	    {
	      putc (*scan_diff, stderr);
	    }
	  while (*scan_diff++ != '\n');
	  exit (2);
	}
      scan_diff++;

      /* Force appropriate ranges to be null, if necessary */
      switch (dt)
	{
	case ADD:
	  bptr->ranges[0][0]++;
	  break;
	case DELETE:
	  bptr->ranges[1][0]++;
	  break;
	case CHANGE:
	  break;
	default:
	  fatal ("internal error: invalid diff type in process_diff");
	  break;
	}

      /* Allocate space for the pointers for the lines from filea, and
	 parcel them out among these pointers */
      if (dt != ADD)
	{
	  int numlines = D_NUMLINES (bptr, 0);
	  bptr->lines[0] = ALLOCATE (numlines, char *);
	  bptr->lengths[0] = ALLOCATE (numlines, size_t);
	  for (i = 0; i < numlines; i++)
	    scan_diff = scan_diff_line (scan_diff,
					&(bptr->lines[0][i]),
					&(bptr->lengths[0][i]),
					diff_limit,
					'<');
	}

      /* Get past the separator for changes */
      if (dt == CHANGE)
	{
	  if (strncmp (scan_diff, "---\n", 4))
	    fatal ("invalid diff format; invalid change separator");
	  scan_diff += 4;
	}

      /* Allocate space for the pointers for the lines from fileb, and
	 parcel them out among these pointers */
      if (dt != DELETE)
	{
	  int numlines = D_NUMLINES (bptr, 1);
	  bptr->lines[1] = ALLOCATE (numlines, char *);
	  bptr->lengths[1] = ALLOCATE (numlines, size_t);
	  for (i = 0; i < numlines; i++)
	    scan_diff = scan_diff_line (scan_diff,
					&(bptr->lines[1][i]),
					&(bptr->lengths[1][i]),
					diff_limit,
					'>');
	}

      /* Place this block on the blocklist.  */
      *block_list_end = bptr;
      block_list_end = &bptr->next;
    }

  *block_list_end = 0;
  *last_block = bptr;
  return block_list;
}

/*
 * This routine will parse a normal format diff control string.  It
 * returns the type of the diff (ERROR if the format is bad).  All of
 * the other important information is filled into to the structure
 * pointed to by db, and the string pointer (whose location is passed
 * to this routine) is updated to point beyond the end of the string
 * parsed.  Note that only the ranges in the diff_block will be set by
 * this routine.
 *
 * If some specific pair of numbers has been reduced to a single
 * number, then both corresponding numbers in the diff block are set
 * to that number.  In general these numbers are interpetted as ranges
 * inclusive, unless being used by the ADD or DELETE commands.  It is
 * assumed that these will be special cased in a superior routine.
 */

static enum diff_type
process_diff_control (string, db)
     char **string;
     struct diff_block *db;
{
  char *s = *string;
  int holdnum;
  enum diff_type type;

/* These macros are defined here because they can use variables
   defined in this function.  Don't try this at home kids, we're
   trained professionals!

   Also note that SKIPWHITE only recognizes tabs and spaces, and
   that READNUM can only read positive, integral numbers */

#define	SKIPWHITE(s)	{ while (*s == ' ' || *s == '\t') s++; }
#define	READNUM(s, num)	\
	{ unsigned char c = *s; if (!ISDIGIT (c)) return ERROR; holdnum = 0; \
	  do { holdnum = (c - '0' + holdnum * 10); }	\
	  while (ISDIGIT (c = *++s)); (num) = holdnum; }

  /* Read first set of digits */
  SKIPWHITE (s);
  READNUM (s, db->ranges[0][START]);

  /* Was that the only digit? */
  SKIPWHITE (s);
  if (*s == ',')
    {
      /* Get the next digit */
      s++;
      READNUM (s, db->ranges[0][END]);
    }
  else
    db->ranges[0][END] = db->ranges[0][START];

  /* Get the letter */
  SKIPWHITE (s);
  switch (*s)
    {
    case 'a':
      type = ADD;
      break;
    case 'c':
      type = CHANGE;
      break;
    case 'd':
      type = DELETE;
      break;
    default:
      return ERROR;			/* Bad format */
    }
  s++;				/* Past letter */

  /* Read second set of digits */
  SKIPWHITE (s);
  READNUM (s, db->ranges[1][START]);

  /* Was that the only digit? */
  SKIPWHITE (s);
  if (*s == ',')
    {
      /* Get the next digit */
      s++;
      READNUM (s, db->ranges[1][END]);
      SKIPWHITE (s);		/* To move to end */
    }
  else
    db->ranges[1][END] = db->ranges[1][START];

  *string = s;
  return type;
}

static char *
read_diff (filea, fileb, output_placement)
     char const *filea, *fileb;
     char **output_placement;
{
  char *diff_result;
  size_t bytes, current_chunk_size, total;
  int fd, wstatus;
  struct stat pipestat;

  /* 302 / 1000 is log10(2.0) rounded up.  Subtract 1 for the sign bit;
     add 1 for integer division truncation; add 1 more for a minus sign.  */
#define INT_STRLEN_BOUND(type) ((sizeof(type)*CHAR_BIT - 1) * 302 / 1000 + 2)

#if HAVE_FORK

  char const *argv[7];
  char horizon_arg[17 + INT_STRLEN_BOUND (int)];
  char const **ap;
  int fds[2];
  pid_t pid;

  ap = argv;
  *ap++ = diff_program;
  if (always_text)
    *ap++ = "-a";
  sprintf (horizon_arg, "--horizon-lines=%d", horizon_lines);
  *ap++ = horizon_arg;
  *ap++ = "--";
  *ap++ = filea;
  *ap++ = fileb;
  *ap = 0;

  if (pipe (fds) != 0)
    perror_with_exit ("pipe");

  pid = fork ();
  if (pid == 0)
    {
      /* Child */
      close (fds[0]);
      if (fds[1] != STDOUT_FILENO)
	{
	  dup2 (fds[1], STDOUT_FILENO);
	  close (fds[1]);
	}
      execve (diff_program, (char **) argv, environ);
      /* Avoid stdio, because the parent process's buffers are inherited.  */
      write (STDERR_FILENO, diff_program, strlen (diff_program));
      write (STDERR_FILENO, ": not found\n", 12);
      _exit (2);
    }

  if (pid == -1)
    perror_with_exit ("fork failed");

  close (fds[1]);		/* Prevent erroneous lack of EOF */
  fd = fds[0];

#else /* ! HAVE_FORK */

  FILE *fpipe;
  char *command = xmalloc (sizeof (diff_program) + 30 + INT_STRLEN_BOUND (int)
			   + 4 * (strlen (filea) + strlen (fileb)));
  char *p;
  sprintf (command, "%s -a --horizon-lines=%d -- ",
	   diff_program, horizon_lines);
  p = command + strlen (command);
  SYSTEM_QUOTE_ARG (p, filea);
  *p++ = ' ';
  SYSTEM_QUOTE_ARG (p, fileb);
  *p = '\0';
  fpipe = popen (command, "r");
  if (!fpipe)
    perror_with_exit (command);
  free (command);
  fd = fileno (fpipe);

#endif /* ! HAVE_FORK */

  current_chunk_size = 8 * 1024;
  if (fstat (fd, &pipestat) == 0)
    current_chunk_size = max (current_chunk_size, STAT_BLOCKSIZE (pipestat));

  diff_result = xmalloc (current_chunk_size);
  total = 0;
  do {
    bytes = myread (fd,
		    diff_result + total,
		    current_chunk_size - total);
    total += bytes;
    if (total == current_chunk_size)
      {
	if (current_chunk_size < 2 * current_chunk_size)
	  current_chunk_size = 2 * current_chunk_size;
	else if (current_chunk_size < (size_t) -1)
	  current_chunk_size = (size_t) -1;
	else
	  fatal ("files are too large to fit into memory");
	diff_result = xrealloc (diff_result, (current_chunk_size *= 2));
      }
  } while (bytes);

  if (total != 0 && diff_result[total-1] != '\n')
    fatal ("invalid diff format; incomplete last line");

  *output_placement = diff_result;

#if ! HAVE_FORK

  wstatus = pclose (fpipe);

#else /* HAVE_FORK */

  if (close (fd) != 0)
    perror_with_exit ("pipe close");
  if (waitpid (pid, &wstatus, 0) < 0)
    perror_with_exit ("waitpid failed");

#endif /* HAVE_FORK */

  if (! (WIFEXITED (wstatus) && WEXITSTATUS (wstatus) < 2))
    fatal ("subsidiary diff failed");

  return diff_result + total;
}


/*
 * Scan a regular diff line (consisting of > or <, followed by a
 * space, followed by text (including nulls) up to a newline.
 *
 * This next routine began life as a macro and many parameters in it
 * are used as call-by-reference values.
 */
static char *
scan_diff_line (scan_ptr, set_start, set_length, limit, leadingchar)
     char *scan_ptr, **set_start;
     size_t *set_length;
     char *limit;
     int leadingchar;
{
  char *line_ptr;

  if (!(scan_ptr[0] == leadingchar
	&& scan_ptr[1] == ' '))
    fatal ("invalid diff format; incorrect leading line chars");

  *set_start = line_ptr = scan_ptr + 2;
  while (*line_ptr++ != '\n')
    ;

  /* Include newline if the original line ended in a newline,
     or if an edit script is being generated.
     Copy any missing newline message to stderr if an edit script is being
     generated, because edit scripts cannot handle missing newlines.
     Return the beginning of the next line.  */
  *set_length = line_ptr - *set_start;
  if (line_ptr < limit && *line_ptr == '\\')
    {
      if (edscript)
	fprintf (stderr, "%s:", program_name);
      else
	--*set_length;
      line_ptr++;
      do
	{
	  if (edscript)
	    putc (*line_ptr, stderr);
	}
      while (*line_ptr++ != '\n');
    }

  return line_ptr;
}

/*
 * This routine outputs a three way diff passed as a list of
 * diff3_block's.
 * The argument MAPPING is indexed by external file number (in the
 * argument list) and contains the internal file number (from the
 * diff passed).  This is important because the user expects his
 * outputs in terms of the argument list number, and the diff passed
 * may have been done slightly differently (if the last argument
 * was "-", for example).
 * REV_MAPPING is the inverse of MAPPING.
 */
static void
output_diff3 (outputfile, diff, mapping, rev_mapping)
     FILE *outputfile;
     struct diff3_block *diff;
     int const mapping[3], rev_mapping[3];
{
  int i;
  int oddoneout;
  char *cp;
  struct diff3_block *ptr;
  int line;
  size_t length;
  int dontprint;
  static int skew_increment[3] = { 2, 3, 1 }; /* 0==>2==>1==>3 */
  char const *line_prefix = tab_align_flag ? "\t" : "  ";

  for (ptr = diff; ptr; ptr = D_NEXT (ptr))
    {
      char x[2];