Blame src/analyze.c

Packit 33f14e
/* Analyze file differences for GNU DIFF.
Packit 33f14e
Packit 33f14e
   Copyright (C) 1988-1989, 1992-1995, 1998, 2001-2002, 2004, 2006-2007,
Packit 33f14e
   2009-2013, 2015-2017 Free Software Foundation, Inc.
Packit 33f14e
Packit 33f14e
   This file is part of GNU DIFF.
Packit 33f14e
Packit 33f14e
   This program is free software: you can redistribute it and/or modify
Packit 33f14e
   it under the terms of the GNU General Public License as published by
Packit 33f14e
   the Free Software Foundation, either version 3 of the License, or
Packit 33f14e
   (at your option) any later version.
Packit 33f14e
Packit 33f14e
   This program is distributed in the hope that it will be useful,
Packit 33f14e
   but WITHOUT ANY WARRANTY; without even the implied warranty of
Packit 33f14e
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
Packit 33f14e
   GNU General Public License for more details.
Packit 33f14e
Packit 33f14e
   You should have received a copy of the GNU General Public License
Packit 33f14e
   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
Packit 33f14e
Packit 33f14e
#include "diff.h"
Packit 33f14e
#include <cmpbuf.h>
Packit 33f14e
#include <error.h>
Packit 33f14e
#include <file-type.h>
Packit 33f14e
#include <xalloc.h>
Packit 33f14e
Packit 33f14e
/* The core of the Diff algorithm.  */
Packit 33f14e
#define ELEMENT lin
Packit 33f14e
#define EQUAL(x,y) ((x) == (y))
Packit 33f14e
#define OFFSET lin
Packit 33f14e
#define EXTRA_CONTEXT_FIELDS /* none */
Packit 33f14e
#define NOTE_DELETE(c, xoff) (files[0].changed[files[0].realindexes[xoff]] = 1)
Packit 33f14e
#define NOTE_INSERT(c, yoff) (files[1].changed[files[1].realindexes[yoff]] = 1)
Packit 33f14e
#define USE_HEURISTIC 1
Packit 33f14e
#include <diffseq.h>
Packit 33f14e
Packit 33f14e
/* Discard lines from one file that have no matches in the other file.
Packit 33f14e
Packit 33f14e
   A line which is discarded will not be considered by the actual
Packit 33f14e
   comparison algorithm; it will be as if that line were not in the file.
Packit 33f14e
   The file's 'realindexes' table maps virtual line numbers
Packit 33f14e
   (which don't count the discarded lines) into real line numbers;
Packit 33f14e
   this is how the actual comparison algorithm produces results
Packit 33f14e
   that are comprehensible when the discarded lines are counted.
Packit 33f14e
Packit 33f14e
   When we discard a line, we also mark it as a deletion or insertion
Packit 33f14e
   so that it will be printed in the output.  */
Packit 33f14e
Packit 33f14e
static void
Packit 33f14e
discard_confusing_lines (struct file_data filevec[])
Packit 33f14e
{
Packit 33f14e
  int f;
Packit 33f14e
  lin i;
Packit 33f14e
  char *discarded[2];
Packit 33f14e
  lin *equiv_count[2];
Packit 33f14e
  lin *p;
Packit 33f14e
Packit 33f14e
  /* Allocate our results.  */
Packit 33f14e
  p = xmalloc ((filevec[0].buffered_lines + filevec[1].buffered_lines)
Packit 33f14e
	       * (2 * sizeof *p));
Packit 33f14e
  for (f = 0; f < 2; f++)
Packit 33f14e
    {
Packit 33f14e
      filevec[f].undiscarded = p;  p += filevec[f].buffered_lines;
Packit 33f14e
      filevec[f].realindexes = p;  p += filevec[f].buffered_lines;
Packit 33f14e
    }
Packit 33f14e
Packit 33f14e
  /* Set up equiv_count[F][I] as the number of lines in file F
Packit 33f14e
     that fall in equivalence class I.  */
Packit 33f14e
Packit 33f14e
  p = zalloc (filevec[0].equiv_max * (2 * sizeof *p));
Packit 33f14e
  equiv_count[0] = p;
Packit 33f14e
  equiv_count[1] = p + filevec[0].equiv_max;
Packit 33f14e
Packit 33f14e
  for (i = 0; i < filevec[0].buffered_lines; ++i)
Packit 33f14e
    ++equiv_count[0][filevec[0].equivs[i]];
Packit 33f14e
  for (i = 0; i < filevec[1].buffered_lines; ++i)
Packit 33f14e
    ++equiv_count[1][filevec[1].equivs[i]];
Packit 33f14e
Packit 33f14e
  /* Set up tables of which lines are going to be discarded.  */
Packit 33f14e
Packit 33f14e
  discarded[0] = zalloc (filevec[0].buffered_lines
Packit 33f14e
			 + filevec[1].buffered_lines);
Packit 33f14e
  discarded[1] = discarded[0] + filevec[0].buffered_lines;
Packit 33f14e
Packit 33f14e
  /* Mark to be discarded each line that matches no line of the other file.
Packit 33f14e
     If a line matches many lines, mark it as provisionally discardable.  */
Packit 33f14e
Packit 33f14e
  for (f = 0; f < 2; f++)
Packit 33f14e
    {
Packit 33f14e
      size_t end = filevec[f].buffered_lines;
Packit 33f14e
      char *discards = discarded[f];
Packit 33f14e
      lin *counts = equiv_count[1 - f];
Packit 33f14e
      lin *equivs = filevec[f].equivs;
Packit 33f14e
      size_t many = 5;
Packit 33f14e
      size_t tem = end / 64;
Packit 33f14e
Packit 33f14e
      /* Multiply MANY by approximate square root of number of lines.
Packit 33f14e
	 That is the threshold for provisionally discardable lines.  */
Packit 33f14e
      while ((tem = tem >> 2) > 0)
Packit 33f14e
	many *= 2;
Packit 33f14e
Packit 33f14e
      for (i = 0; i < end; i++)
Packit 33f14e
	{
Packit 33f14e
	  lin nmatch;
Packit 33f14e
	  if (equivs[i] == 0)
Packit 33f14e
	    continue;
Packit 33f14e
	  nmatch = counts[equivs[i]];
Packit 33f14e
	  if (nmatch == 0)
Packit 33f14e
	    discards[i] = 1;
Packit 33f14e
	  else if (nmatch > many)
Packit 33f14e
	    discards[i] = 2;
Packit 33f14e
	}
Packit 33f14e
    }
Packit 33f14e
Packit 33f14e
  /* Don't really discard the provisional lines except when they occur
Packit 33f14e
     in a run of discardables, with nonprovisionals at the beginning
Packit 33f14e
     and end.  */
Packit 33f14e
Packit 33f14e
  for (f = 0; f < 2; f++)
Packit 33f14e
    {
Packit 33f14e
      lin end = filevec[f].buffered_lines;
Packit 33f14e
      register char *discards = discarded[f];
Packit 33f14e
Packit 33f14e
      for (i = 0; i < end; i++)
Packit 33f14e
	{
Packit 33f14e
	  /* Cancel provisional discards not in middle of run of discards.  */
Packit 33f14e
	  if (discards[i] == 2)
Packit 33f14e
	    discards[i] = 0;
Packit 33f14e
	  else if (discards[i] != 0)
Packit 33f14e
	    {
Packit 33f14e
	      /* We have found a nonprovisional discard.  */
Packit 33f14e
	      register lin j;
Packit 33f14e
	      lin length;
Packit 33f14e
	      lin provisional = 0;
Packit 33f14e
Packit 33f14e
	      /* Find end of this run of discardable lines.
Packit 33f14e
		 Count how many are provisionally discardable.  */
Packit 33f14e
	      for (j = i; j < end; j++)
Packit 33f14e
		{
Packit 33f14e
		  if (discards[j] == 0)
Packit 33f14e
		    break;
Packit 33f14e
		  if (discards[j] == 2)
Packit 33f14e
		    ++provisional;
Packit 33f14e
		}
Packit 33f14e
Packit 33f14e
	      /* Cancel provisional discards at end, and shrink the run.  */
Packit 33f14e
	      while (j > i && discards[j - 1] == 2)
Packit 33f14e
		discards[--j] = 0, --provisional;
Packit 33f14e
Packit 33f14e
	      /* Now we have the length of a run of discardable lines
Packit 33f14e
		 whose first and last are not provisional.  */
Packit 33f14e
	      length = j - i;
Packit 33f14e
Packit 33f14e
	      /* If 1/4 of the lines in the run are provisional,
Packit 33f14e
		 cancel discarding of all provisional lines in the run.  */
Packit 33f14e
	      if (provisional * 4 > length)
Packit 33f14e
		{
Packit 33f14e
		  while (j > i)
Packit 33f14e
		    if (discards[--j] == 2)
Packit 33f14e
		      discards[j] = 0;
Packit 33f14e
		}
Packit 33f14e
	      else
Packit 33f14e
		{
Packit 33f14e
		  register lin consec;
Packit 33f14e
		  lin minimum = 1;
Packit 33f14e
		  lin tem = length >> 2;
Packit 33f14e
Packit 33f14e
		  /* MINIMUM is approximate square root of LENGTH/4.
Packit 33f14e
		     A subrun of two or more provisionals can stand
Packit 33f14e
		     when LENGTH is at least 16.
Packit 33f14e
		     A subrun of 4 or more can stand when LENGTH >= 64.  */
Packit 33f14e
		  while (0 < (tem >>= 2))
Packit 33f14e
		    minimum <<= 1;
Packit 33f14e
		  minimum++;
Packit 33f14e
Packit 33f14e
		  /* Cancel any subrun of MINIMUM or more provisionals
Packit 33f14e
		     within the larger run.  */
Packit 33f14e
		  for (j = 0, consec = 0; j < length; j++)
Packit 33f14e
		    if (discards[i + j] != 2)
Packit 33f14e
		      consec = 0;
Packit 33f14e
		    else if (minimum == ++consec)
Packit 33f14e
		      /* Back up to start of subrun, to cancel it all.  */
Packit 33f14e
		      j -= consec;
Packit 33f14e
		    else if (minimum < consec)
Packit 33f14e
		      discards[i + j] = 0;
Packit 33f14e
Packit 33f14e
		  /* Scan from beginning of run
Packit 33f14e
		     until we find 3 or more nonprovisionals in a row
Packit 33f14e
		     or until the first nonprovisional at least 8 lines in.
Packit 33f14e
		     Until that point, cancel any provisionals.  */
Packit 33f14e
		  for (j = 0, consec = 0; j < length; j++)
Packit 33f14e
		    {
Packit 33f14e
		      if (j >= 8 && discards[i + j] == 1)
Packit 33f14e
			break;
Packit 33f14e
		      if (discards[i + j] == 2)
Packit 33f14e
			consec = 0, discards[i + j] = 0;
Packit 33f14e
		      else if (discards[i + j] == 0)
Packit 33f14e
			consec = 0;
Packit 33f14e
		      else
Packit 33f14e
			consec++;
Packit 33f14e
		      if (consec == 3)
Packit 33f14e
			break;
Packit 33f14e
		    }
Packit 33f14e
Packit 33f14e
		  /* I advances to the last line of the run.  */
Packit 33f14e
		  i += length - 1;
Packit 33f14e
Packit 33f14e
		  /* Same thing, from end.  */
Packit 33f14e
		  for (j = 0, consec = 0; j < length; j++)
Packit 33f14e
		    {
Packit 33f14e
		      if (j >= 8 && discards[i - j] == 1)
Packit 33f14e
			break;
Packit 33f14e
		      if (discards[i - j] == 2)
Packit 33f14e
			consec = 0, discards[i - j] = 0;
Packit 33f14e
		      else if (discards[i - j] == 0)
Packit 33f14e
			consec = 0;
Packit 33f14e
		      else
Packit 33f14e
			consec++;
Packit 33f14e
		      if (consec == 3)
Packit 33f14e
			break;
Packit 33f14e
		    }
Packit 33f14e
		}
Packit 33f14e
	    }
Packit 33f14e
	}
Packit 33f14e
    }
Packit 33f14e
Packit 33f14e
  /* Actually discard the lines. */
Packit 33f14e
  for (f = 0; f < 2; f++)
Packit 33f14e
    {
Packit 33f14e
      char *discards = discarded[f];
Packit 33f14e
      lin end = filevec[f].buffered_lines;
Packit 33f14e
      lin j = 0;
Packit 33f14e
      for (i = 0; i < end; ++i)
Packit 33f14e
	if (minimal || discards[i] == 0)
Packit 33f14e
	  {
Packit 33f14e
	    filevec[f].undiscarded[j] = filevec[f].equivs[i];
Packit 33f14e
	    filevec[f].realindexes[j++] = i;
Packit 33f14e
	  }
Packit 33f14e
	else
Packit 33f14e
	  filevec[f].changed[i] = 1;
Packit 33f14e
      filevec[f].nondiscarded_lines = j;
Packit 33f14e
    }
Packit 33f14e
Packit 33f14e
  free (discarded[0]);
Packit 33f14e
  free (equiv_count[0]);
Packit 33f14e
}
Packit 33f14e

Packit 33f14e
/* Adjust inserts/deletes of identical lines to join changes
Packit 33f14e
   as much as possible.
Packit 33f14e
Packit 33f14e
   We do something when a run of changed lines include a
Packit 33f14e
   line at one end and have an excluded, identical line at the other.
Packit 33f14e
   We are free to choose which identical line is included.
Packit 33f14e
   'compareseq' usually chooses the one at the beginning,
Packit 33f14e
   but usually it is cleaner to consider the following identical line
Packit 33f14e
   to be the "change".  */
Packit 33f14e
Packit 33f14e
static void
Packit 33f14e
shift_boundaries (struct file_data filevec[])
Packit 33f14e
{
Packit 33f14e
  int f;
Packit 33f14e
Packit 33f14e
  for (f = 0; f < 2; f++)
Packit 33f14e
    {
Packit 33f14e
      char *changed = filevec[f].changed;
Packit 33f14e
      char *other_changed = filevec[1 - f].changed;
Packit 33f14e
      lin const *equivs = filevec[f].equivs;
Packit 33f14e
      lin i = 0;
Packit 33f14e
      lin j = 0;
Packit 33f14e
      lin i_end = filevec[f].buffered_lines;
Packit 33f14e
Packit 33f14e
      while (1)
Packit 33f14e
	{
Packit 33f14e
	  lin runlength, start, corresponding;
Packit 33f14e
Packit 33f14e
	  /* Scan forwards to find beginning of another run of changes.
Packit 33f14e
	     Also keep track of the corresponding point in the other file.  */
Packit 33f14e
Packit 33f14e
	  while (i < i_end && !changed[i])
Packit 33f14e
	    {
Packit 33f14e
	      while (other_changed[j++])
Packit 33f14e
		continue;
Packit 33f14e
	      i++;
Packit 33f14e
	    }
Packit 33f14e
Packit 33f14e
	  if (i == i_end)
Packit 33f14e
	    break;
Packit 33f14e
Packit 33f14e
	  start = i;
Packit 33f14e
Packit 33f14e
	  /* Find the end of this run of changes.  */
Packit 33f14e
Packit 33f14e
	  while (changed[++i])
Packit 33f14e
	    continue;
Packit 33f14e
	  while (other_changed[j])
Packit 33f14e
	    j++;
Packit 33f14e
Packit 33f14e
	  do
Packit 33f14e
	    {
Packit 33f14e
	      /* Record the length of this run of changes, so that
Packit 33f14e
		 we can later determine whether the run has grown.  */
Packit 33f14e
	      runlength = i - start;
Packit 33f14e
Packit 33f14e
	      /* Move the changed region back, so long as the
Packit 33f14e
		 previous unchanged line matches the last changed one.
Packit 33f14e
		 This merges with previous changed regions.  */
Packit 33f14e
Packit 33f14e
	      while (start && equivs[start - 1] == equivs[i - 1])
Packit 33f14e
		{
Packit 33f14e
		  changed[--start] = 1;
Packit 33f14e
		  changed[--i] = 0;
Packit 33f14e
		  while (changed[start - 1])
Packit 33f14e
		    start--;
Packit 33f14e
		  while (other_changed[--j])
Packit 33f14e
		    continue;
Packit 33f14e
		}
Packit 33f14e
Packit 33f14e
	      /* Set CORRESPONDING to the end of the changed run, at the last
Packit 33f14e
		 point where it corresponds to a changed run in the other file.
Packit 33f14e
		 CORRESPONDING == I_END means no such point has been found.  */
Packit 33f14e
	      corresponding = other_changed[j - 1] ? i : i_end;
Packit 33f14e
Packit 33f14e
	      /* Move the changed region forward, so long as the
Packit 33f14e
		 first changed line matches the following unchanged one.
Packit 33f14e
		 This merges with following changed regions.
Packit 33f14e
		 Do this second, so that if there are no merges,
Packit 33f14e
		 the changed region is moved forward as far as possible.  */
Packit 33f14e
Packit 33f14e
	      while (i != i_end && equivs[start] == equivs[i])
Packit 33f14e
		{
Packit 33f14e
		  changed[start++] = 0;
Packit 33f14e
		  changed[i++] = 1;
Packit 33f14e
		  while (changed[i])
Packit 33f14e
		    i++;
Packit 33f14e
		  while (other_changed[++j])
Packit 33f14e
		    corresponding = i;
Packit 33f14e
		}
Packit 33f14e
	    }
Packit 33f14e
	  while (runlength != i - start);
Packit 33f14e
Packit 33f14e
	  /* If possible, move the fully-merged run of changes
Packit 33f14e
	     back to a corresponding run in the other file.  */
Packit 33f14e
Packit 33f14e
	  while (corresponding < i)
Packit 33f14e
	    {
Packit 33f14e
	      changed[--start] = 1;
Packit 33f14e
	      changed[--i] = 0;
Packit 33f14e
	      while (other_changed[--j])
Packit 33f14e
		continue;
Packit 33f14e
	    }
Packit 33f14e
	}
Packit 33f14e
    }
Packit 33f14e
}
Packit 33f14e

Packit 33f14e
/* Cons an additional entry onto the front of an edit script OLD.
Packit 33f14e
   LINE0 and LINE1 are the first affected lines in the two files (origin 0).
Packit 33f14e
   DELETED is the number of lines deleted here from file 0.
Packit 33f14e
   INSERTED is the number of lines inserted here in file 1.
Packit 33f14e
Packit 33f14e
   If DELETED is 0 then LINE0 is the number of the line before
Packit 33f14e
   which the insertion was done; vice versa for INSERTED and LINE1.  */
Packit 33f14e
Packit 33f14e
static struct change *
Packit 33f14e
add_change (lin line0, lin line1, lin deleted, lin inserted,
Packit 33f14e
	    struct change *old)
Packit 33f14e
{
Packit 33f14e
  struct change *new = xmalloc (sizeof *new);
Packit 33f14e
Packit 33f14e
  new->line0 = line0;
Packit 33f14e
  new->line1 = line1;
Packit 33f14e
  new->inserted = inserted;
Packit 33f14e
  new->deleted = deleted;
Packit 33f14e
  new->link = old;
Packit 33f14e
  return new;
Packit 33f14e
}
Packit 33f14e
Packit 33f14e
/* Scan the tables of which lines are inserted and deleted,
Packit 33f14e
   producing an edit script in reverse order.  */
Packit 33f14e
Packit 33f14e
static struct change *
Packit 33f14e
build_reverse_script (struct file_data const filevec[])
Packit 33f14e
{
Packit 33f14e
  struct change *script = 0;
Packit 33f14e
  char *changed0 = filevec[0].changed;
Packit 33f14e
  char *changed1 = filevec[1].changed;
Packit 33f14e
  lin len0 = filevec[0].buffered_lines;
Packit 33f14e
  lin len1 = filevec[1].buffered_lines;
Packit 33f14e
Packit 33f14e
  /* Note that changedN[lenN] does exist, and is 0.  */
Packit 33f14e
Packit 33f14e
  lin i0 = 0, i1 = 0;
Packit 33f14e
Packit 33f14e
  while (i0 < len0 || i1 < len1)
Packit 33f14e
    {
Packit 33f14e
      if (changed0[i0] | changed1[i1])
Packit 33f14e
	{
Packit 33f14e
	  lin line0 = i0, line1 = i1;
Packit 33f14e
Packit 33f14e
	  /* Find # lines changed here in each file.  */
Packit 33f14e
	  while (changed0[i0]) ++i0;
Packit 33f14e
	  while (changed1[i1]) ++i1;
Packit 33f14e
Packit 33f14e
	  /* Record this change.  */
Packit 33f14e
	  script = add_change (line0, line1, i0 - line0, i1 - line1, script);
Packit 33f14e
	}
Packit 33f14e
Packit 33f14e
      /* We have reached lines in the two files that match each other.  */
Packit 33f14e
      i0++, i1++;
Packit 33f14e
    }
Packit 33f14e
Packit 33f14e
  return script;
Packit 33f14e
}
Packit 33f14e
Packit 33f14e
/* Scan the tables of which lines are inserted and deleted,
Packit 33f14e
   producing an edit script in forward order.  */
Packit 33f14e
Packit 33f14e
static struct change *
Packit 33f14e
build_script (struct file_data const filevec[])
Packit 33f14e
{
Packit 33f14e
  struct change *script = 0;
Packit 33f14e
  char *changed0 = filevec[0].changed;
Packit 33f14e
  char *changed1 = filevec[1].changed;
Packit 33f14e
  lin i0 = filevec[0].buffered_lines, i1 = filevec[1].buffered_lines;
Packit 33f14e
Packit 33f14e
  /* Note that changedN[-1] does exist, and is 0.  */
Packit 33f14e
Packit 33f14e
  while (i0 >= 0 || i1 >= 0)
Packit 33f14e
    {
Packit 33f14e
      if (changed0[i0 - 1] | changed1[i1 - 1])
Packit 33f14e
	{
Packit 33f14e
	  lin line0 = i0, line1 = i1;
Packit 33f14e
Packit 33f14e
	  /* Find # lines changed here in each file.  */
Packit 33f14e
	  while (changed0[i0 - 1]) --i0;
Packit 33f14e
	  while (changed1[i1 - 1]) --i1;
Packit 33f14e
Packit 33f14e
	  /* Record this change.  */
Packit 33f14e
	  script = add_change (i0, i1, line0 - i0, line1 - i1, script);
Packit 33f14e
	}
Packit 33f14e
Packit 33f14e
      /* We have reached lines in the two files that match each other.  */
Packit 33f14e
      i0--, i1--;
Packit 33f14e
    }
Packit 33f14e
Packit 33f14e
  return script;
Packit 33f14e
}
Packit 33f14e

Packit 33f14e
/* If CHANGES, briefly report that two files differed.  */
Packit 33f14e
static void
Packit 33f14e
briefly_report (int changes, struct file_data const filevec[])
Packit 33f14e
{
Packit 33f14e
  if (changes)
Packit 33f14e
    message ((brief
Packit 33f14e
	      ? _("Files %s and %s differ\n")
Packit 33f14e
	      : _("Binary files %s and %s differ\n")),
Packit 33f14e
	     file_label[0] ? file_label[0] : filevec[0].name,
Packit 33f14e
	     file_label[1] ? file_label[1] : filevec[1].name);
Packit 33f14e
}
Packit 33f14e
Packit 33f14e
/* Report the differences of two files.  */
Packit 33f14e
int
Packit 33f14e
diff_2_files (struct comparison *cmp)
Packit 33f14e
{
Packit 33f14e
  int f;
Packit 33f14e
  struct change *e, *p;
Packit 33f14e
  struct change *script;
Packit 33f14e
  int changes;
Packit 33f14e
Packit 33f14e
Packit 33f14e
  /* If we have detected that either file is binary,
Packit 33f14e
     compare the two files as binary.  This can happen
Packit 33f14e
     only when the first chunk is read.
Packit 33f14e
     Also, --brief without any --ignore-* options means
Packit 33f14e
     we can speed things up by treating the files as binary.  */
Packit 33f14e
Packit 33f14e
  if (read_files (cmp->file, files_can_be_treated_as_binary))
Packit 33f14e
    {
Packit 33f14e
      /* Files with different lengths must be different.  */
Packit 33f14e
      if (cmp->file[0].stat.st_size != cmp->file[1].stat.st_size
Packit 33f14e
	  && 0 < cmp->file[0].stat.st_size
Packit 33f14e
	  && 0 < cmp->file[1].stat.st_size
Packit 33f14e
	  && (cmp->file[0].desc < 0 || S_ISREG (cmp->file[0].stat.st_mode))
Packit 33f14e
	  && (cmp->file[1].desc < 0 || S_ISREG (cmp->file[1].stat.st_mode)))
Packit 33f14e
	changes = 1;
Packit 33f14e
Packit 33f14e
      /* Standard input equals itself.  */
Packit 33f14e
      else if (cmp->file[0].desc == cmp->file[1].desc)
Packit 33f14e
	changes = 0;
Packit 33f14e
Packit 33f14e
      else
Packit 33f14e
	/* Scan both files, a buffer at a time, looking for a difference.  */
Packit 33f14e
	{
Packit 33f14e
	  /* Allocate same-sized buffers for both files.  */
Packit 33f14e
	  size_t lcm_max = PTRDIFF_MAX - 1;
Packit 33f14e
	  size_t buffer_size =
Packit 33f14e
	    buffer_lcm (sizeof (word),
Packit 33f14e
			buffer_lcm (STAT_BLOCKSIZE (cmp->file[0].stat),
Packit 33f14e
				    STAT_BLOCKSIZE (cmp->file[1].stat),
Packit 33f14e
				    lcm_max),
Packit 33f14e
			lcm_max);
Packit 33f14e
	  for (f = 0; f < 2; f++)
Packit 33f14e
	    cmp->file[f].buffer = xrealloc (cmp->file[f].buffer, buffer_size);
Packit 33f14e
Packit 33f14e
	  for (;; cmp->file[0].buffered = cmp->file[1].buffered = 0)
Packit 33f14e
	    {
Packit 33f14e
	      /* Read a buffer's worth from both files.  */
Packit 33f14e
	      for (f = 0; f < 2; f++)
Packit 33f14e
		if (0 <= cmp->file[f].desc)
Packit 33f14e
		  file_block_read (&cmp->file[f],
Packit 33f14e
				   buffer_size - cmp->file[f].buffered);
Packit 33f14e
Packit 33f14e
	      /* If the buffers differ, the files differ.  */
Packit 33f14e
	      if (cmp->file[0].buffered != cmp->file[1].buffered
Packit 33f14e
		  || memcmp (cmp->file[0].buffer,
Packit 33f14e
			     cmp->file[1].buffer,
Packit 33f14e
			     cmp->file[0].buffered))
Packit 33f14e
		{
Packit 33f14e
		  changes = 1;
Packit 33f14e
		  break;
Packit 33f14e
		}
Packit 33f14e
Packit 33f14e
	      /* If we reach end of file, the files are the same.  */
Packit 33f14e
	      if (cmp->file[0].buffered != buffer_size)
Packit 33f14e
		{
Packit 33f14e
		  changes = 0;
Packit 33f14e
		  break;
Packit 33f14e
		}
Packit 33f14e
	    }
Packit 33f14e
	}
Packit 33f14e
Packit 33f14e
      briefly_report (changes, cmp->file);
Packit 33f14e
    }
Packit 33f14e
  else
Packit 33f14e
    {
Packit 33f14e
      struct context ctxt;
Packit 33f14e
      lin diags;
Packit 33f14e
      lin too_expensive;
Packit 33f14e
Packit 33f14e
      /* Allocate vectors for the results of comparison:
Packit 33f14e
	 a flag for each line of each file, saying whether that line
Packit 33f14e
	 is an insertion or deletion.
Packit 33f14e
	 Allocate an extra element, always 0, at each end of each vector.  */
Packit 33f14e
Packit 33f14e
      size_t s = cmp->file[0].buffered_lines + cmp->file[1].buffered_lines + 4;
Packit 33f14e
      char *flag_space = zalloc (s);
Packit 33f14e
      cmp->file[0].changed = flag_space + 1;
Packit 33f14e
      cmp->file[1].changed = flag_space + cmp->file[0].buffered_lines + 3;
Packit 33f14e
Packit 33f14e
      /* Some lines are obviously insertions or deletions
Packit 33f14e
	 because they don't match anything.  Detect them now, and
Packit 33f14e
	 avoid even thinking about them in the main comparison algorithm.  */
Packit 33f14e
Packit 33f14e
      discard_confusing_lines (cmp->file);
Packit 33f14e
Packit 33f14e
      /* Now do the main comparison algorithm, considering just the
Packit 33f14e
	 undiscarded lines.  */
Packit 33f14e
Packit 33f14e
      ctxt.xvec = cmp->file[0].undiscarded;
Packit 33f14e
      ctxt.yvec = cmp->file[1].undiscarded;
Packit 33f14e
      diags = (cmp->file[0].nondiscarded_lines
Packit 33f14e
	       + cmp->file[1].nondiscarded_lines + 3);
Packit 33f14e
      ctxt.fdiag = xmalloc (diags * (2 * sizeof *ctxt.fdiag));
Packit 33f14e
      ctxt.bdiag = ctxt.fdiag + diags;
Packit 33f14e
      ctxt.fdiag += cmp->file[1].nondiscarded_lines + 1;
Packit 33f14e
      ctxt.bdiag += cmp->file[1].nondiscarded_lines + 1;
Packit 33f14e
Packit 33f14e
      ctxt.heuristic = speed_large_files;
Packit 33f14e
Packit 33f14e
      /* Set TOO_EXPENSIVE to be the approximate square root of the
Packit 33f14e
	 input size, bounded below by 4096.  4096 seems to be good for
Packit 33f14e
	 circa-2016 CPUs; see Bug#16848 and Bug#24715.  */
Packit 33f14e
      too_expensive = 1;
Packit 33f14e
      for (;  diags != 0;  diags >>= 2)
Packit 33f14e
	too_expensive <<= 1;
Packit 33f14e
      ctxt.too_expensive = MAX (4096, too_expensive);
Packit 33f14e
Packit 33f14e
      files[0] = cmp->file[0];
Packit 33f14e
      files[1] = cmp->file[1];
Packit 33f14e
Packit 33f14e
      compareseq (0, cmp->file[0].nondiscarded_lines,
Packit 33f14e
		  0, cmp->file[1].nondiscarded_lines, minimal, &ctxt);
Packit 33f14e
Packit 33f14e
      free (ctxt.fdiag - (cmp->file[1].nondiscarded_lines + 1));
Packit 33f14e
Packit 33f14e
      /* Modify the results slightly to make them prettier
Packit 33f14e
	 in cases where that can validly be done.  */
Packit 33f14e
Packit 33f14e
      shift_boundaries (cmp->file);
Packit 33f14e
Packit 33f14e
      /* Get the results of comparison in the form of a chain
Packit 33f14e
	 of 'struct change's -- an edit script.  */
Packit 33f14e
Packit 33f14e
      if (output_style == OUTPUT_ED)
Packit 33f14e
	script = build_reverse_script (cmp->file);
Packit 33f14e
      else
Packit 33f14e
	script = build_script (cmp->file);
Packit 33f14e
Packit 33f14e
      /* Set CHANGES if we had any diffs.
Packit 33f14e
	 If some changes are ignored, we must scan the script to decide.  */
Packit 33f14e
      if (ignore_blank_lines || ignore_regexp.fastmap)
Packit 33f14e
	{
Packit 33f14e
	  struct change *next = script;
Packit 33f14e
	  changes = 0;
Packit 33f14e
Packit 33f14e
	  while (next && changes == 0)
Packit 33f14e
	    {
Packit 33f14e
	      struct change *this, *end;
Packit 33f14e
	      lin first0, last0, first1, last1;
Packit 33f14e
Packit 33f14e
	      /* Find a set of changes that belong together.  */
Packit 33f14e
	      this = next;
Packit 33f14e
	      end = find_change (next);
Packit 33f14e
Packit 33f14e
	      /* Disconnect them from the rest of the changes, making them
Packit 33f14e
		 a hunk, and remember the rest for next iteration.  */
Packit 33f14e
	      next = end->link;
Packit 33f14e
	      end->link = 0;
Packit 33f14e
Packit 33f14e
	      /* Determine whether this hunk is really a difference.  */
Packit 33f14e
	      if (analyze_hunk (this, &first0, &last0, &first1, &last1))
Packit 33f14e
		changes = 1;
Packit 33f14e
Packit 33f14e
	      /* Reconnect the script so it will all be freed properly.  */
Packit 33f14e
	      end->link = next;
Packit 33f14e
	    }
Packit 33f14e
	}
Packit 33f14e
      else
Packit 33f14e
	changes = (script != 0);
Packit 33f14e
Packit 33f14e
      if (brief)
Packit 33f14e
	briefly_report (changes, cmp->file);
Packit 33f14e
      else
Packit 33f14e
	{
Packit 33f14e
	  if (changes || !no_diff_means_no_output)
Packit 33f14e
	    {
Packit 33f14e
	      /* Record info for starting up output,
Packit 33f14e
		 to be used if and when we have some output to print.  */
Packit 33f14e
	      setup_output (file_label[0] ? file_label[0] : cmp->file[0].name,
Packit 33f14e
			    file_label[1] ? file_label[1] : cmp->file[1].name,
Packit 33f14e
			    cmp->parent != 0);
Packit 33f14e
Packit 33f14e
	      switch (output_style)
Packit 33f14e
		{
Packit 33f14e
		case OUTPUT_CONTEXT:
Packit 33f14e
		  print_context_script (script, false);
Packit 33f14e
		  break;
Packit 33f14e
Packit 33f14e
		case OUTPUT_UNIFIED:
Packit 33f14e
		  print_context_script (script, true);
Packit 33f14e
		  break;
Packit 33f14e
Packit 33f14e
		case OUTPUT_ED:
Packit 33f14e
		  print_ed_script (script);
Packit 33f14e
		  break;
Packit 33f14e
Packit 33f14e
		case OUTPUT_FORWARD_ED:
Packit 33f14e
		  pr_forward_ed_script (script);
Packit 33f14e
		  break;
Packit 33f14e
Packit 33f14e
		case OUTPUT_RCS:
Packit 33f14e
		  print_rcs_script (script);
Packit 33f14e
		  break;
Packit 33f14e
Packit 33f14e
		case OUTPUT_NORMAL:
Packit 33f14e
		  print_normal_script (script);
Packit 33f14e
		  break;
Packit 33f14e
Packit 33f14e
		case OUTPUT_IFDEF:
Packit 33f14e
		  print_ifdef_script (script);
Packit 33f14e
		  break;
Packit 33f14e
Packit 33f14e
		case OUTPUT_SDIFF:
Packit 33f14e
		  print_sdiff_script (script);
Packit 33f14e
		  break;
Packit 33f14e
Packit 33f14e
		default:
Packit 33f14e
		  abort ();
Packit 33f14e
		}
Packit 33f14e
Packit 33f14e
	      finish_output ();
Packit 33f14e
	    }
Packit 33f14e
	}
Packit 33f14e
Packit 33f14e
      free (cmp->file[0].undiscarded);
Packit 33f14e
Packit 33f14e
      free (flag_space);
Packit 33f14e
Packit 33f14e
      for (f = 0; f < 2; f++)
Packit 33f14e
	{
Packit 33f14e
	  free (cmp->file[f].equivs);
Packit 33f14e
	  free (cmp->file[f].linbuf + cmp->file[f].linbuf_base);
Packit 33f14e
	}
Packit 33f14e
Packit 33f14e
      for (e = script; e; e = p)
Packit 33f14e
	{
Packit 33f14e
	  p = e->link;
Packit 33f14e
	  free (e);
Packit 33f14e
	}
Packit 33f14e
Packit 33f14e
      if (! ROBUST_OUTPUT_STYLE (output_style))
Packit 33f14e
	for (f = 0; f < 2; ++f)
Packit 33f14e
	  if (cmp->file[f].missing_newline)
Packit 33f14e
	    {
Packit 33f14e
	      error (0, 0, "%s: %s\n",
Packit 33f14e
		     file_label[f] ? file_label[f] : cmp->file[f].name,
Packit 33f14e
		     _("No newline at end of file"));
Packit 33f14e
	      changes = 2;
Packit 33f14e
	    }
Packit 33f14e
    }
Packit 33f14e
Packit 33f14e
  if (cmp->file[0].buffer != cmp->file[1].buffer)
Packit 33f14e
    free (cmp->file[0].buffer);
Packit 33f14e
  free (cmp->file[1].buffer);
Packit 33f14e
Packit 33f14e
  return changes;
Packit 33f14e
}