analyze.c

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

   INSERTED is the number of lines inserted here in file 1.

   If DELETED is 0 then LINE0 is the number of the line before
   which the insertion was done; vice versa for INSERTED and LINE1.  */

static struct change *
add_change (line0, line1, deleted, inserted, old)
     int line0, line1, deleted, inserted;
     struct change *old;
{
  struct change *new = (struct change *) xmalloc (sizeof (struct change));

  new->line0 = line0;
  new->line1 = line1;
  new->inserted = inserted;
  new->deleted = deleted;
  new->link = old;
  return new;
}

/* Scan the tables of which lines are inserted and deleted,
   producing an edit script in reverse order.  */

static struct change *
build_reverse_script (filevec)
     struct file_data const filevec[];
{
  struct change *script = 0;
  char *changed0 = filevec[0].changed_flag;
  char *changed1 = filevec[1].changed_flag;
  int len0 = filevec[0].buffered_lines;
  int len1 = filevec[1].buffered_lines;

  /* Note that changedN[len0] does exist, and contains 0.  */

  int i0 = 0, i1 = 0;

  while (i0 < len0 || i1 < len1)
    {
      if (changed0[i0] || changed1[i1])
	{
	  int line0 = i0, line1 = i1;

	  /* Find # lines changed here in each file.  */
	  while (changed0[i0]) ++i0;
	  while (changed1[i1]) ++i1;

	  /* Record this change.  */
	  script = add_change (line0, line1, i0 - line0, i1 - line1, script);
	}

      /* We have reached lines in the two files that match each other.  */
      i0++, i1++;
    }

  return script;
}

/* Scan the tables of which lines are inserted and deleted,
   producing an edit script in forward order.  */

static struct change *
build_script (filevec)
     struct file_data const filevec[];
{
  struct change *script = 0;
  char *changed0 = filevec[0].changed_flag;
  char *changed1 = filevec[1].changed_flag;
  int i0 = filevec[0].buffered_lines, i1 = filevec[1].buffered_lines;

  /* Note that changedN[-1] does exist, and contains 0.  */

  while (i0 >= 0 || i1 >= 0)
    {
      if (changed0[i0 - 1] || changed1[i1 - 1])
	{
	  int line0 = i0, line1 = i1;

	  /* Find # lines changed here in each file.  */
	  while (changed0[i0 - 1]) --i0;
	  while (changed1[i1 - 1]) --i1;

	  /* Record this change.  */
	  script = add_change (i0, i1, line0 - i0, line1 - i1, script);
	}

      /* We have reached lines in the two files that match each other.  */
      i0--, i1--;
    }

  return script;
}

/* If CHANGES, briefly report that two files differed.  */
static void
briefly_report (changes, filevec)
     int changes;
     struct file_data const filevec[];
{
  if (changes)
    message (no_details_flag ? "Files %s and %s differ\n"
	     : "Binary files %s and %s differ\n",
	     filevec[0].name, filevec[1].name);
}

/* Report the differences of two files.  DEPTH is the current directory
   depth. */
int
diff_2_files (filevec, depth)
     struct file_data filevec[];
     int depth;
{
  int diags;
  int i;
  struct change *e, *p;
  struct change *script;
  int changes;


  /* If we have detected that either file is binary,
     compare the two files as binary.  This can happen
     only when the first chunk is read.
     Also, --brief without any --ignore-* options means
     we can speed things up by treating the files as binary.  */

  if (read_files (filevec, no_details_flag & ~ignore_some_changes))
    {
      /* Files with different lengths must be different.  */
      if (filevec[0].stat.st_size != filevec[1].stat.st_size
	  && (filevec[0].desc < 0 || S_ISREG (filevec[0].stat.st_mode))
	  && (filevec[1].desc < 0 || S_ISREG (filevec[1].stat.st_mode)))
	changes = 1;

      /* Standard input equals itself.  */
      else if (filevec[0].desc == filevec[1].desc)
	changes = 0;

      else
	/* Scan both files, a buffer at a time, looking for a difference.  */
	{
	  /* Allocate same-sized buffers for both files.  */
	  size_t buffer_size = buffer_lcm (STAT_BLOCKSIZE (filevec[0].stat),
					   STAT_BLOCKSIZE (filevec[1].stat));
	  for (i = 0; i < 2; i++)
	    filevec[i].buffer = xrealloc (filevec[i].buffer, buffer_size);

	  for (;;  filevec[0].buffered_chars = filevec[1].buffered_chars = 0)
	    {
	      /* Read a buffer's worth from both files.  */
	      for (i = 0; i < 2; i++)
		if (0 <= filevec[i].desc)
		  while (filevec[i].buffered_chars != buffer_size)
		    {
		      int r = read (filevec[i].desc,
				    filevec[i].buffer
				    + filevec[i].buffered_chars,
				    buffer_size - filevec[i].buffered_chars);
		      if (r == 0)
			break;
		      if (r < 0)
			pfatal_with_name (filevec[i].name);
		      filevec[i].buffered_chars += r;
		    }

	      /* If the buffers differ, the files differ.  */
	      if (filevec[0].buffered_chars != filevec[1].buffered_chars
		  || (filevec[0].buffered_chars != 0
		      && memcmp (filevec[0].buffer,
				 filevec[1].buffer,
				 filevec[0].buffered_chars) != 0))
		{
		  changes = 1;
		  break;
		}

	      /* If we reach end of file, the files are the same.  */
	      if (filevec[0].buffered_chars != buffer_size)
		{
		  changes = 0;
		  break;
		}
	    }
	}

      briefly_report (changes, filevec);
    }
  else
    {
      /* Allocate vectors for the results of comparison:
	 a flag for each line of each file, saying whether that line
	 is an insertion or deletion.
	 Allocate an extra element, always zero, at each end of each vector.  */

      size_t s = filevec[0].buffered_lines + filevec[1].buffered_lines + 4;
      filevec[0].changed_flag = xmalloc (s);
      bzero (filevec[0].changed_flag, s);
      filevec[0].changed_flag++;
      filevec[1].changed_flag = filevec[0].changed_flag
				+ filevec[0].buffered_lines + 2;

      /* Some lines are obviously insertions or deletions
	 because they don't match anything.  Detect them now, and
	 avoid even thinking about them in the main comparison algorithm.  */

      discard_confusing_lines (filevec);

      /* Now do the main comparison algorithm, considering just the
	 undiscarded lines.  */

      xvec = filevec[0].undiscarded;
      yvec = filevec[1].undiscarded;
      diags = filevec[0].nondiscarded_lines + filevec[1].nondiscarded_lines + 3;
      fdiag = (int *) xmalloc (diags * (2 * sizeof (int)));
      bdiag = fdiag + diags;
      fdiag += filevec[1].nondiscarded_lines + 1;
      bdiag += filevec[1].nondiscarded_lines + 1;

      /* Set TOO_EXPENSIVE to be approximate square root of input size,
	 bounded below by 256.  */
      too_expensive = 1;
      for (i = filevec[0].nondiscarded_lines + filevec[1].nondiscarded_lines;
	   i != 0; i >>= 2)
	too_expensive <<= 1;
      too_expensive = max (256, too_expensive);

      files[0] = filevec[0];
      files[1] = filevec[1];

      compareseq (0, filevec[0].nondiscarded_lines,
		  0, filevec[1].nondiscarded_lines, no_discards);

      free (fdiag - (filevec[1].nondiscarded_lines + 1));

      /* Modify the results slightly to make them prettier
	 in cases where that can validly be done.  */

      shift_boundaries (filevec);

      /* Get the results of comparison in the form of a chain
	 of `struct change's -- an edit script.  */

      if (output_style == OUTPUT_ED)
	script = build_reverse_script (filevec);
      else
	script = build_script (filevec);

      /* Set CHANGES if we had any diffs.
	 If some changes are ignored, we must scan the script to decide.  */
      if (ignore_blank_lines_flag || ignore_regexp_list)
	{
	  struct change *next = script;
	  changes = 0;

	  while (next && changes == 0)
	    {
	      struct change *this, *end;
	      int first0, last0, first1, last1, deletes, inserts;

	      /* Find a set of changes that belong together.  */
	      this = next;
	      end = find_change (next);

	      /* Disconnect them from the rest of the changes, making them
		 a hunk, and remember the rest for next iteration.  */
	      next = end->link;
	      end->link = 0;

	      /* Determine whether this hunk is really a difference.  */
	      analyze_hunk (this, &first0, &last0, &first1, &last1,
			    &deletes, &inserts);

	      /* Reconnect the script so it will all be freed properly.  */
	      end->link = next;

	      if (deletes || inserts)
		changes = 1;
	    }
	}
      else
	changes = (script != 0);

      if (no_details_flag)
	briefly_report (changes, filevec);
      else
	{
	  if (changes || ! no_diff_means_no_output)
	    {
	      /* Record info for starting up output,
		 to be used if and when we have some output to print.  */
	      setup_output (files[0].name, files[1].name, depth);

	      switch (output_style)
		{
		case OUTPUT_CONTEXT:
		  print_context_script (script, 0);
		  break;

		case OUTPUT_UNIFIED:
		  print_context_script (script, 1);
		  break;

		case OUTPUT_ED:
		  print_ed_script (script);
		  break;

		case OUTPUT_FORWARD_ED:
		  pr_forward_ed_script (script);
		  break;

		case OUTPUT_RCS:
		  print_rcs_script (script);
		  break;

		case OUTPUT_NORMAL:
		  print_normal_script (script);
		  break;

		case OUTPUT_IFDEF:
		  print_ifdef_script (script);
		  break;

		case OUTPUT_SDIFF:
		  print_sdiff_script (script);
		}

	      finish_output ();
	    }
	}

      free (filevec[0].undiscarded);

      free (filevec[0].changed_flag - 1);

      for (i = 1; i >= 0; --i)
	free (filevec[i].equivs);

      for (i = 0; i < 2; ++i)
	free (filevec[i].linbuf + filevec[i].linbuf_base);

      for (e = script; e; e = p)
	{
	  p = e->link;
	  free (e);
	}

      if (! ROBUST_OUTPUT_STYLE (output_style))
	for (i = 0; i < 2; ++i)
	  if (filevec[i].missing_newline)
	    {
	      error ("No newline at end of file %s", filevec[i].name, "");
	      changes = 2;
	    }
    }

  if (filevec[0].buffer != filevec[1].buffer)
    free (filevec[0].buffer);
  free (filevec[1].buffer);

  return changes;
}