# This is a shell archive.
# Remove anything above and including the cut line.
# Then run the rest of the file through 'sh'.
# Unpacked files will be owned by you and have default permissions.
#----cut here-----cut here-----cut here-----cut here----#
#!/bin/sh
# shar: SHell ARchive
# Run the following text through 'sh' to create:
#       diff/analyze.c
#       diff/context.c
#       diff/diff.c
#       diff/diff3.c
# This is archive 2 of a 14-part kit.
# This archive created: Sun Nov 19 01:12:04 1989
if `test ! -d diff`
then
  mkdir diff
  echo "mkdir diff"
fi
echo "extracting diff/analyze.c"
sed 's/^X//' << \SHAR_EOF > diff/analyze.c
X/* Analyze file differences for GNU DIFF.
X   Copyright (C) 1988, 1989 Free Software Foundation, Inc.
X
XThis file is part of GNU DIFF.
X
XGNU DIFF is free software; you can redistribute it and/or modify
Xit under the terms of the GNU General Public License as published by
Xthe Free Software Foundation; either version 1, or (at your option)
Xany later version.
X
XGNU DIFF is distributed in the hope that it will be useful,
Xbut WITHOUT ANY WARRANTY; without even the implied warranty of
XMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
XGNU General Public License for more details.
X
XYou should have received a copy of the GNU General Public License
Xalong with GNU DIFF; see the file COPYING.  If not, write to
Xthe Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
X
X/* The basic algorithm is described in:
X   "An O(ND) Difference Algorithm and its Variations", Eugene Myers,
X   Algorithmica Vol. 1 No. 2, 1986, p 251.  */
X
X#include "regex.h"
X#include "diff.h"
X
Xextern int no_discards;
X
Xstatic int *xvec, *yvec;       /* Vectors being compared. */
Xstatic int *fdiag;             /* Vector, indexed by diagonal, containing
X                                  the X coordinate of the point furthest
X                                  along the given diagonal in the forward
X                                  search of the edit matrix. */
Xstatic int *bdiag;             /* Vector, indexed by diagonal, containing
X                                  the X coordinate of the point furthest
X                                  along the given diagonal in the backward
X                                  search of the edit matrix. */
X
X/* Find the midpoint of the shortest edit script for a specified
X   portion of the two files.
X
X   We scan from the beginnings of the files, and simultaneously from the ends,
X   doing a breadth-first search through the space of edit-sequence.
X   When the two searches meet, we have found the midpoint of the shortest
X   edit sequence.
X
X   The value returned is the number of the diagonal on which the midpoint lies.
X   The diagonal number equals the number of inserted lines minus the number
X   of deleted lines (counting only lines before the midpoint).
X   The edit cost is stored into *COST; this is the total number of
X   lines inserted or deleted (counting only lines before the midpoint).
X
X   This function assumes that the first lines of the specified portions
X   of the two files do not match, and likewise that the last lines do not
X   match.  The caller must trim matching lines from the beginning and end
X   of the portions it is going to specify.
X
X   Note that if we return the "wrong" diagonal value, or if
X   the value of bdiag at that diagonal is "wrong",
X   the worst this can do is cause suboptimal diff output.
X   It cannot cause incorrect diff output.  */
X
Xstatic int
Xdiag (xoff, xlim, yoff, ylim, cost)
X     int xoff, xlim, yoff, ylim;
X     int *cost;
X{
X  int *const fd = fdiag;       /* Give the compiler a chance. */
X  int *const bd = bdiag;       /* Additional help for the compiler. */
X  int *const xv = xvec;                /* Still more help for the comiler. */
X  int *const yv = yvec;                /* And more and more . . . */
X  const int dmin = xoff - ylim;        /* Minimum valid diagonal. */
X  const int dmax = xlim - yoff;        /* Maximum valid diagonal. */
X  const int fmid = xoff - yoff;        /* Center diagonal of top-down search. */
X  const int bmid = xlim - ylim;        /* Center diagonal of bottom-up search. */
X  int fmin = fmid, fmax = fmid;        /* Limits of top-down search. */
X  int bmin = bmid, bmax = bmid;        /* Limits of bottom-up search. */
X  int c;                       /* Cost. */
X  int odd = fmid - bmid & 1;       /* True if southeast corner is on an odd
X                                  diagonal with respect to the northwest. */
X
X  fd[fmid] = xoff;
X  bd[bmid] = xlim;
X
X  for (c = 1;; ++c)
X    {
X      int d;                   /* Active diagonal. */
X      int big_snake = 0;
X
X      /* Extend the top-down search by an edit step in each diagonal. */
X      fmin > dmin ? fd[--fmin - 1] = -1 : ++fmin;
X      fmax < dmax ? fd[++fmax + 1] = -1 : --fmax;
X      for (d = fmax; d >= fmin; d -= 2)
X       {
X         int x, y, oldx, tlo = fd[d - 1], thi = fd[d + 1];
X
X         if (tlo >= thi)
X           x = tlo + 1;
X         else
X           x = thi;
X         oldx = x;
X         y = x - d;
X         while (x < xlim && y < ylim && xv[x] == yv[y])
X           ++x, ++y;
X         if (x - oldx > 20)
X           big_snake = 1;
X         fd[d] = x;
X         if (odd && bmin <= d && d <= bmax && bd[d] <= fd[d])
X           {
X             *cost = 2 * c - 1;
X             return d;
X           }
X       }
X
X      /* Similar extend the bottom-up search. */
X      bmin > dmin ? bd[--bmin - 1] = INT_MAX : ++bmin;
X      bmax < dmax ? bd[++bmax + 1] = INT_MAX : --bmax;
X      for (d = bmax; d >= bmin; d -= 2)
X       {
X         int x, y, oldx, tlo = bd[d - 1], thi = bd[d + 1];
X
X         if (tlo < thi)
X           x = tlo;
X         else
X           x = thi - 1;
X         oldx = x;
X         y = x - d;
X         while (x > xoff && y > yoff && xv[x - 1] == yv[y - 1])
X           --x, --y;
X         if (oldx - x > 20)
X           big_snake = 1;
X         bd[d] = x;
X         if (!odd && fmin <= d && d <= fmax && bd[d] <= fd[d])
X           {
X             *cost = 2 * c;
X             return d;
X           }
X       }
X
X      /* Heuristic: check occasionally for a diagonal that has made
X        lots of progress compared with the edit distance.
X        If we have any such, find the one that has made the most
X        progress and return it as if it had succeeded.
X
X        With this heuristic, for files with a constant small density
X        of changes, the algorithm is linear in the file size.  */
X
X      if (c > 200 && big_snake && heuristic)
X       {
X         int best;
X         int bestpos;
X
X         best = 0;
X         for (d = fmax; d >= fmin; d -= 2)
X           {
X             int dd = d - fmid;
X             if ((fd[d] - xoff)*2 - dd > 12 * (c + (dd > 0 ? dd : -dd)))
X               {
X                 if (fd[d] * 2 - dd > best
X                     && fd[d] - xoff > 20
X                     && fd[d] - d - yoff > 20)
X                   {
X                     int k;
X                     int x = fd[d];
X
X                     /* We have a good enough best diagonal;
X                        now insist that it end with a significant snake.  */
X                     for (k = 1; k <= 20; k++)
X                       if (xvec[x - k] != yvec[x - d - k])
X                         break;
X
X                     if (k == 21)
X                       {
X                         best = fd[d] * 2 - dd;
X                         bestpos = d;
X                       }
X                   }
X               }
X           }
X         if (best > 0)
X           {
X             *cost = 2 * c - 1;
X             return bestpos;
X           }
X
X         best = 0;
X         for (d = bmax; d >= bmin; d -= 2)
X           {
X             int dd = d - bmid;
X             if ((xlim - bd[d])*2 + dd > 12 * (c + (dd > 0 ? dd : -dd)))
X               {
X                 if ((xlim - bd[d]) * 2 + dd > best
X                     && xlim - bd[d] > 20
X                     && ylim - (bd[d] - d) > 20)
X                   {
X                     /* We have a good enough best diagonal;
X                        now insist that it end with a significant snake.  */
X                     int k;
X                     int x = bd[d];
X
X                     for (k = 0; k < 20; k++)
X                       if (xvec[x + k] != yvec[x - d + k])
X                         break;
X                     if (k == 20)
X                       {
X                         best = (xlim - bd[d]) * 2 + dd;
X                         bestpos = d;
X                       }
X                   }
X               }
X           }
X         if (best > 0)
X           {
X             *cost = 2 * c - 1;
X             return bestpos;
X           }
X       }
X    }
X}
X
X/* Compare in detail contiguous subsequences of the two files
X   which are known, as a whole, to match each other.
X
X   The results are recorded in the vectors files[N].changed_flag, by
X   storing a 1 in the element for each line that is an insertion or deletion.
X
X   The subsequence of file 0 is [XOFF, XLIM) and likewise for file 1.
X
X   Note that XLIM, YLIM are exclusive bounds.
X   All line numbers are origin-0 and discarded lines are not counted.  */
X
Xstatic void
Xcompareseq (xoff, xlim, yoff, ylim)
X     int xoff, xlim, yoff, ylim;
X{
X  /* Slide down the bottom initial diagonal. */
X  while (xoff < xlim && yoff < ylim && xvec[xoff] == yvec[yoff])
X    ++xoff, ++yoff;
X  /* Slide up the top initial diagonal. */
X  while (xlim > xoff && ylim > yoff && xvec[xlim - 1] == yvec[ylim - 1])
X    --xlim, --ylim;
X  
X  /* Handle simple cases. */
X  if (xoff == xlim)
X    while (yoff < ylim)
X      files[1].changed_flag[files[1].realindexes[yoff++]] = 1;
X  else if (yoff == ylim)
X    while (xoff < xlim)
X      files[0].changed_flag[files[0].realindexes[xoff++]] = 1;
X  else
X    {
X      int c, d, f, b;
X
X      /* Find a point of correspondence in the middle of the files.  */
X
X      d = diag (xoff, xlim, yoff, ylim, &c);
X      f = fdiag[d];
X      b = bdiag[d];
X
X      if (c == 1)
X       {
X         /* This should be impossible, because it implies that
X            one of the two subsequences is empty,
X            and that case was handled above without calling `diag'.
X            Let's verify that this is true.  */
X         abort ();
X#if 0
X         /* The two subsequences differ by a single insert or delete;
X            record it and we are done.  */
X         if (d < xoff - yoff)
X           files[1].changed_flag[files[1].realindexes[b - d - 1]] = 1;
X         else
X           files[0].changed_flag[files[0].realindexes[b]] = 1;
X#endif
X       }
X      else
X       {
X         /* Use that point to split this problem into two subproblems.  */
X         compareseq (xoff, b, yoff, b - d);
X         /* This used to use f instead of b,
X            but that is incorrect!
X            It is not necessarily the case that diagonal d
X            has a snake from b to f.  */
X         compareseq (b, xlim, b - d, ylim);
X       }
X    }
X}
X
X/* Discard lines from one file that have no matches in the other file.
X
X   A line which is discarded will not be considered by the actual
X   comparison algorithm; it will be as if that line were not in the file.
X   The file's `realindexes' table maps virtual line numbers
X   (which don't count the discarded lines) into real line numbers;
X   this is how the actual comparison algorithm produces results
X   that are comprehensible when the discarded lines are counted.
X
X   When we discard a line, we also mark it as a deletion or insertion
X   so that it will be printed in the output.  */
X
Xvoid
Xdiscard_confusing_lines (filevec)
X     struct file_data filevec[];
X{
X  int f, i, j;
X  char *discarded[2];
X  int *equiv_count[2];
X
X  /* Allocate our results.  */
X  for (f = 0; f < 2; f++)
X    {
X      filevec[f].undiscarded
X       = (int *) xmalloc (filevec[f].buffered_lines * sizeof (int));
X      filevec[f].realindexes
X       = (int *) xmalloc (filevec[f].buffered_lines * sizeof (int));
X    }
X
X  /* Set up equiv_count[F][I] as the number of lines in file F
X     that fall in equivalence class I.  */
X
X  equiv_count[0] = (int *) xmalloc (filevec[0].equiv_max * sizeof (int));
X  bzero (equiv_count[0], filevec[0].equiv_max * sizeof (int));
X  equiv_count[1] = (int *) xmalloc (filevec[1].equiv_max * sizeof (int));
X  bzero (equiv_count[1], filevec[1].equiv_max * sizeof (int));
X
X  for (i = 0; i < filevec[0].buffered_lines; ++i)
X    ++equiv_count[0][filevec[0].equivs[i]];
X  for (i = 0; i < filevec[1].buffered_lines; ++i)
X    ++equiv_count[1][filevec[1].equivs[i]];
X
X  /* Set up tables of which lines are going to be discarded.  */
X
X  discarded[0] = (char *) xmalloc (filevec[0].buffered_lines);
X  discarded[1] = (char *) xmalloc (filevec[1].buffered_lines);
X  bzero (discarded[0], filevec[0].buffered_lines);
X  bzero (discarded[1], filevec[1].buffered_lines);
X
X  /* Mark to be discarded each line that matches no line of the other file.
X     If a line matches many lines, mark it as provisionally discardable.  */
X
X  for (f = 0; f < 2; f++)
X    {
X      int end = filevec[f].buffered_lines;
X      char *discards = discarded[f];
X      int *counts = equiv_count[1 - f];
X      int *equivs = filevec[f].equivs;
X      for (i = 0; i < end; i++)
X       {
X         int nmatch = counts[equivs[i]];
X         if (equivs[i] == 0)
X           continue;
X         if (nmatch == 0)
X           discards[i] = 1;
X         else if (nmatch > 5)
X           discards[i] = 2;
X       }
X    }
X
X  /* Don't really discard the provisional lines if there are less than ten
X     discardable lines in a row.  */
X
X  for (f = 0; f < 2; f++)
X    {
X      int end = filevec[f].buffered_lines;
X      char *discards = discarded[f];
X
X      for (i = 0; i < end; i++)
X       if (discards[i])
X         {
X           register int j;
X           int length;
X           int provisional = 0;
X
X           /* Cancel provisional discards at the beginning.  */
X           while (i < end && discards[i] == 2)
X             discards[i] = 0;
X
X           /* Find end of this run of discardable lines.
X              Count how many are provisionally discardable.  */
X           for (j = i; j < end; j++)
X             {
X               if (discards[j] == 0)
X                 break;
X               if (discards[j] == 2)
X                 ++provisional;
X             }
X
X           /* Cancel provisional discards at the end, and shrink the run.  */
X           while (j > i && discards[j - 1] == 2)
X             discards[j - 1] = 0, --provisional;
X
X           /* Now we have the length of a run of discardable lines
X              whose first and last are not provisional.  */
X           length = j - i;
X
X           /* If half the lines in the run are provisional,
X              cancel discarding of all provisional lines in the run.  */
X           if (provisional * 2 > length)
X             {
X               while (j > i)
X                 if (discards[--j] == 2)
X                   discards[j] = 0;
X             }
X           else
X             {
X               /* Cancel provisional discards that are near either end.  */
X               for (j = 0; j < 5 && j < length; j++)
X                 if (discards[i + j] == 2)
X                   discards[i + j] = 0;
X               /* Meanwhile, I advances to the last line of the run.  */
X               i += length - 1;
X               length -= 5;
X               for (j = 0; j < 5 && j < length; j++)
X                 if (discards[i - j] == 2)
X                   discards[i - j] = 0;
X             }
X         }
X    }
X
X  /* Discard from file 0. */
X  for (f = 0; f < 2; f++)
X    {
X      char *discards = discarded[f];
X      int end = filevec[f].buffered_lines;
X      j = 0;
X      for (i = 0; i < end; ++i)
X       if (no_discards || discards[i] == 0)
X         {
X           filevec[f].undiscarded[j] = filevec[f].equivs[i];
X           filevec[f].realindexes[j++] = i;
X         }
X       else
X         filevec[f].changed_flag[i] = 1;
X      filevec[f].nondiscarded_lines = j;
X    }
X
X  free (discarded[1]);
X  free (discarded[0]);
X  free (equiv_count[1]);
X  free (equiv_count[0]);
X}
X
X/* Adjust inserts/deletes of blank lines to join changes
X   as much as possible.
X
X   We do something when a run of changed lines include a blank
X   line at one end and have an excluded blank line at the other.
X   We are free to choose which blank line is included.
X   `compareseq' always chooses the one at the beginning,
X   but usually it is cleaner to consider the following blank line
X   to be the "change".  The only exception is if the preceding blank line
X   would join this change to other changes.  */
X
Xint inhibit;
X
Xstatic void
Xshift_boundaries (filevec)
X     struct file_data filevec[];
X{
X  int f;
X
X  if (inhibit)
X    return;
X
X  for (f = 0; f < 2; f++)
X    {
X      char *changed = filevec[f].changed_flag;
X      char *other_changed = filevec[1-f].changed_flag;
X      int i = 0;
X      int j = 0;
X      int i_end = filevec[f].buffered_lines;
X      int preceeding = -1;
X      int other_preceeding = -1;
X
X      while (1)
X       {
X         int start, end, other_start;
X
X         /* Scan forwards to find beginning of another run of changes.
X            Also keep track of the corresponding point in the other file.  */
X
X         while (i < i_end && changed[i] == 0)
X           {
X             while (other_changed[j++])
X               /* Non-corresponding lines in the other file
X                  will count as the preceeding batch of changes.  */
X               other_preceeding = j;
X             i++;
X           }
X
X         if (i == i_end)
X           break;
X
X         start = i;
X         other_start = j;
X
X         while (1)
X           {
X             /* Now find the end of this run of changes.  */
X
X             while (i < i_end && changed[i] != 0) i++;
X             end = i;
X
X             /* If the first changed line matches the following unchanged one,
X                and this run does not follow right after a previous run,
X                and there are no lines deleted from the other file here,
X                then classify the first changed line as unchanged
X                and the following line as changed in its place.  */
X
X             /* You might ask, how could this run follow right after another?
X                Only because the previous run was shifted here.  */
X
X             if (files[f].equivs[start] == files[f].equivs[end]
X                 && !other_changed[j]
X                 && end != i_end
X                 && !((preceeding >= 0 && start == preceeding)
X                      || (other_preceeding >= 0
X                          && other_start == other_preceeding)))
X               {
X                 changed[end++] = 1;
X                 changed[start++] = 0;
X                 ++i;
X                 /* Since one line-that-matches is now before this run
X                    instead of after, we must advance in the other file
X                    to keep in synch.  */
X                 ++j;
X               }
X             else
X               break;
X           }
X
X         preceeding = i;
X         other_preceeding = j;
X       }
X    }
X}
X
X/* Cons an additional entry onto the front of an edit script OLD.
X   LINE0 and LINE1 are the first affected lines in the two files (origin 0).
X   DELETED is the number of lines deleted here from file 0.
X   INSERTED is the number of lines inserted here in file 1.
X
X   If DELETED is 0 then LINE0 is the number of the line before
X   which the insertion was done; vice versa for INSERTED and LINE1.  */
X
Xstatic struct change *
Xadd_change (line0, line1, deleted, inserted, old)
X     int line0, line1, deleted, inserted;
X     struct change *old;
X{
X  struct change *new = (struct change *) xmalloc (sizeof (struct change));
X
X  new->line0 = line0;
X  new->line1 = line1;
X  new->inserted = inserted;
X  new->deleted = deleted;
X  new->link = old;
X  return new;
X}
X
X/* Scan the tables of which lines are inserted and deleted,
X   producing an edit script in reverse order.  */
X
Xstatic struct change *
Xbuild_reverse_script (filevec)
X     struct file_data filevec[];
X{
X  struct change *script = 0;
X  char *changed0 = filevec[0].changed_flag;
X  char *changed1 = filevec[1].changed_flag;
X  int len0 = filevec[0].buffered_lines;
X  int len1 = filevec[1].buffered_lines;
X
X  /* Note that changedN[len0] does exist, and contains 0.  */
X
X  int i0 = 0, i1 = 0;
X
X  while (i0 < len0 || i1 < len1)
X    {
X      if (changed0[i0] || changed1[i1])
X       {
X         int line0 = i0, line1 = i1;
X
X         /* Find # lines changed here in each file.  */
X         while (changed0[i0]) ++i0;
X         while (changed1[i1]) ++i1;
X
X         /* Record this change.  */
X         script = add_change (line0, line1, i0 - line0, i1 - line1, script);
X       }
X
X      /* We have reached lines in the two files that match each other.  */
X      i0++, i1++;
X    }
X
X  return script;
X}
X
X/* Scan the tables of which lines are inserted and deleted,
X   producing an edit script in forward order.  */
X
Xstatic struct change *
Xbuild_script (filevec)
X     struct file_data filevec[];
X{
X  struct change *script = 0;
X  char *changed0 = filevec[0].changed_flag;
X  char *changed1 = filevec[1].changed_flag;
X  int len0 = filevec[0].buffered_lines;
X  int len1 = filevec[1].buffered_lines;
X
X  /* Note that changedN[-1] does exist, and contains 0.  */
X
X  int i0 = len0, i1 = len1;
X
X  while (i0 >= 0 || i1 >= 0)
X    {
X      if (changed0[i0 - 1] || changed1[i1 - 1])
X       {
X         int line0 = i0, line1 = i1;
X
X         /* Find # lines changed here in each file.  */
X         while (changed0[i0 - 1]) --i0;
X         while (changed1[i1 - 1]) --i1;
X
X         /* Record this change.  */
X         script = add_change (i0, i1, line0 - i0, line1 - i1, script);
X       }
X
X      /* We have reached lines in the two files that match each other.  */
X      i0--, i1--;
X    }
X
X  return script;
X}
X
X/* Report the differences of two files.  DEPTH is the current directory
X   depth. */
Xint
Xdiff_2_files (filevec, depth)
X     struct file_data filevec[];
X     int depth;
X{
X  int diags;
X  int i;
X  struct change *e, *p;
X  struct change *script;
X  int binary;
X
X  /* See if the two named files are actually the same physical file.
X     If so, we know they are identical without actually reading them.  */
X
X#ifndef AMIGA
X  if (filevec[0].stat.st_ino == filevec[1].stat.st_ino
X      && filevec[0].stat.st_dev == filevec[1].stat.st_dev)
X    return 0;
X#endif
X
X  binary = read_files (filevec);
X
X  /* If we have detected that file 0 is a binary file,
X     compare the two files as binary.  This can happen
X     only when the first chunk is read.  */
X
X  if (binary)
X    {
X      int differs = (filevec[0].buffered_chars != filevec[1].buffered_chars
X                    || bcmp (filevec[0].buffer, filevec[1].buffer,
X                             filevec[1].buffered_chars));
X      if (differs)
X       message ("Binary files %s and %s differ\n",
X                filevec[0].name, filevec[1].name);
X
X      for (i = 0; i < 2; ++i)
X       if (filevec[i].buffer)
X         free (filevec[i].buffer);
X      return differs;
X    }
X
X  if (filevec[0].missing_newline != filevec[1].missing_newline)
X    {
X      if (filevec[0].missing_newline)
X       error ("No newline at end of file %s\n", filevec[0].name);
X      if (filevec[1].missing_newline)
X       error ("No newline at end of file %s\n", filevec[1].name);
X    }
X
X  /* Allocate vectors for the results of comparison:
X     a flag for each line of each file, saying whether that line
X     is an insertion or deletion.
X     Allocate an extra element, always zero, at each end of each vector.  */
X
X  filevec[0].changed_flag = (char *) xmalloc (filevec[0].buffered_lines + 2);
X  filevec[1].changed_flag = (char *) xmalloc (filevec[1].buffered_lines + 2);
X  bzero (filevec[0].changed_flag, filevec[0].buffered_lines + 2);
X  bzero (filevec[1].changed_flag, filevec[1].buffered_lines + 2);
X  filevec[0].changed_flag++;
X  filevec[1].changed_flag++;
X
X  /* Some lines are obviously insertions or deletions
X     because they don't match anything.  Detect them now,
X     and avoid even thinking about them in the main comparison algorithm.  */
X
X  discard_confusing_lines (filevec);
X
X  /* Now do the main comparison algorithm, considering just the
X     undiscarded lines.  */
X
X  xvec = filevec[0].undiscarded;
X  yvec = filevec[1].undiscarded;
X  diags = filevec[0].nondiscarded_lines + filevec[1].nondiscarded_lines + 3;
X  fdiag = (int *) xmalloc (diags * sizeof (int));
X  fdiag += filevec[1].nondiscarded_lines + 1;
X  bdiag = (int *) xmalloc (diags * sizeof (int));
X  bdiag += filevec[1].nondiscarded_lines + 1;
X
X  files[0] = filevec[0];
X  files[1] = filevec[1];
X
X  compareseq (0, filevec[0].nondiscarded_lines,
X             0, filevec[1].nondiscarded_lines);
X
X  bdiag -= filevec[1].nondiscarded_lines + 1;
X  free (bdiag);
X  fdiag -= filevec[1].nondiscarded_lines + 1;
X  free (fdiag);
X
X  /* Modify the results slightly to make them prettier
X     in cases where that can validly be done.  */
X
X  shift_boundaries (filevec);
X
X  /* Get the results of comparison in the form of a chain
X     of `struct change's -- an edit script.  */
X
X  if (output_style == OUTPUT_ED)
X    script = build_reverse_script (filevec);
X  else
X    script = build_script (filevec);
X
X  if (script)
X    {
X      setup_output (files[0].name, files[1].name, depth);
X      if (output_style == OUTPUT_CONTEXT)
X       print_context_header (files);
X
X      switch (output_style)
X       {
X       case OUTPUT_CONTEXT:
X         print_context_script (script);
X         break;
X
X       case OUTPUT_ED:
X         print_ed_script (script);
X         break;
X
X       case OUTPUT_FORWARD_ED:
X         pr_forward_ed_script (script);
X         break;
X
X       case OUTPUT_RCS:
X         print_rcs_script (script);
X         break;
X
X       case OUTPUT_NORMAL:
X         print_normal_script (script);
X         break;
X       }
X
X      finish_output ();
X    }
X
X  for (i = 1; i >= 0; --i)
X    {
X      free (filevec[i].realindexes);
X      free (filevec[i].undiscarded);
X    }
X
X  for (i = 1; i >= 0; --i)
X    free (--filevec[i].changed_flag);
X
X  for (i = 1; i >= 0; --i)
X    free (filevec[i].equivs);
X
X  for (i = 0; i < 2; ++i)
X    {
X      if (filevec[i].buffer != 0)
X       free (filevec[i].buffer);
X      free (filevec[i].linbuf);
X    }
X
X  for (e = script; e; e = p)
X    {
X      p = e->link;
X      free (e);
X    }
X
X  return script ? 1 : 0;
X}
SHAR_EOF
echo "extracting diff/context.c"
sed 's/^X//' << \SHAR_EOF > diff/context.c
X/* Context-format output routines for GNU DIFF.
X   Copyright (C) 1988, 1989 Free Software Foundation, Inc.
X
XThis file is part of GNU DIFF.
X
XGNU DIFF is free software; you can redistribute it and/or modify
Xit under the terms of the GNU General Public License as published by
Xthe Free Software Foundation; either version 1, or (at your option)
Xany later version.
X
XGNU DIFF is distributed in the hope that it will be useful,
Xbut WITHOUT ANY WARRANTY; without even the implied warranty of
XMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
XGNU General Public License for more details.
X
XYou should have received a copy of the GNU General Public License
Xalong with GNU DIFF; see the file COPYING.  If not, write to
Xthe Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
X
X#include "diff.h"
X
Xstatic void pr_context_hunk ();
Xstatic struct change *find_hunk ();
Xstatic void mark_ignorable ();
Xstatic int find_function ();
X
X/* Last place find_function started searching from.  */
Xstatic int find_function_last_search;
X
X/* The value find_function returned when it started searching there.  */
Xstatic int find_function_last_match;
X
X/* Print a header for a context diff, with the file names and dates.  */
X
Xvoid
Xprint_context_header (inf)
X     struct file_data *inf;
X{
X  fprintf (outfile, "*** %s\t%s", inf[0].name,
X          ctime (&inf[0].stat.st_mtime));
X  fprintf (outfile, "--- %s\t%s", inf[1].name,
X          ctime (&inf[1].stat.st_mtime));
X}
X
X/* Print an edit script in context format.  */
X
Xvoid
Xprint_context_script (script)
X     struct change *script;
X{
X  if (ignore_blank_lines_flag || ignore_regexp)
X    mark_ignorable (script);
X  else
X    {
X      struct change *e;
X      for (e = script; e; e = e->link)
X       e->ignore = 0;
X    }
X
X  find_function_last_search = 0;
X  find_function_last_match = -1;
X
X  print_script (script, find_hunk, pr_context_hunk);
X}
X
X/* Print a pair of line numbers with a comma, translated for file FILE.
X   If the second number is smaller, use the first in place of it.
X
X   Args A and B are internal line numbers.
X   We print the translated (real) line numbers.  */
X
Xstatic void
Xprint_context_number_range (file, a, b)
X     struct file_data *file;
X     int a, b;
X{
X  int trans_a, trans_b;
X  translate_range (file, a, b, &trans_a, &trans_b);
X
X  /* Note: we can have B < A in the case of a range of no lines.
X     In this case, we should print the line number before the range,
X     which is B.  */
X  if (trans_b >= trans_a)
X    fprintf (outfile, "%d,%d", trans_a, trans_b);
X  else
X    fprintf (outfile, "%d", trans_b);
X}
X
X/* Print a portion of an edit script in context format.
X   HUNK is the beginning of the portion to be printed.
X   The end is marked by a `link' that has been nulled out.
X
X   Prints out lines from both files, and precedes each
X   line with the appropriate flag-character.  */
X
Xstatic void
Xpr_context_hunk (hunk)
X     struct change *hunk;
X{
X  int first0, last0, first1, last1, show_from, show_to, i;
X  struct change *next;
X  char *prefix;
X  char *function;
X  int function_length;
X
X  /* Determine range of line numbers involved in each file.  */
X
X  analyze_hunk (hunk, &first0, &last0, &first1, &last1, &show_from, &show_to);
X
X  if (!show_from && !show_to)
X    return;
X
X  /* Include a context's width before and after.  */
X
X  first0 = max (first0 - context, 0);
X  first1 = max (first1 - context, 0);
X  last0 = min (last0 + context, files[0].buffered_lines - 1);
X  last1 = min (last1 + context, files[1].buffered_lines - 1);
X
X  /* If desired, find the preceding function definition line in file 0.  */
X  function = 0;
X  if (function_regexp)
X    find_function (&files[0], first0, &function, &function_length);
X
X  /* If we looked for and found a function this is part of,
X     include its name in the header of the diff section.  */
X  fprintf (outfile, "***************");
X
X  if (function)
X    {
X      fprintf (outfile, " ");
X      fwrite (function, 1, min (function_length - 1, 40), outfile);
X    }
X
X  fprintf (outfile, "\n*** ");
X  print_context_number_range (&files[0], first0, last0);
X  fprintf (outfile, " ****\n");
X
X  if (show_from)
X    {
X      next = hunk;
X
X      for (i = first0; i <= last0; i++)
X       {
X         /* Skip past changes that apply (in file 0)
X            only to lines before line I.  */
X
X         while (next && next->line0 + next->deleted <= i)
X           next = next->link;
X
X         /* Compute the marking for line I.  */
X
X         prefix = " ";
X         if (next && next->line0 <= i)
X           /* The change NEXT covers this line.
X              If lines were inserted here in file 1, this is "changed".
X              Otherwise it is "deleted".  */
X           prefix = (next->inserted > 0 ? "!" : "-");
X
X         print_1_line (prefix, &files[0].linbuf[i]);
X       }
X    }
X
X  fprintf (outfile, "--- ");
X  print_context_number_range (&files[1], first1, last1);
X  fprintf (outfile, " ----\n");
X
X  if (show_to)
X    {
X      next = hunk;
X
X      for (i = first1; i <= last1; i++)
X       {
X         /* Skip past changes that apply (in file 1)
X            only to lines before line I.  */
X
X         while (next && next->line1 + next->inserted <= i)
X           next = next->link;
X
X         /* Compute the marking for line I.  */
X
X         prefix = " ";
X         if (next && next->line1 <= i)
X           /* The change NEXT covers this line.
X              If lines were deleted here in file 0, this is "changed".
X              Otherwise it is "inserted".  */
X           prefix = (next->deleted > 0 ? "!" : "+");
X
X         print_1_line (prefix, &files[1].linbuf[i]);
X       }
X    }
X}
X
X/* Scan a (forward-ordered) edit script for the first place that at least
X   2*CONTEXT unchanged lines appear, and return a pointer
X   to the `struct change' for the last change before those lines.  */
X
Xstatic struct change *
Xfind_hunk (start)
X     struct change *start;
X{
X  struct change *prev;
X  int top0, top1;
X  int thresh;
X
X  do
X    {
X      /* Computer number of first line in each file beyond this changed.  */
X      top0 = start->line0 + start->deleted;
X      top1 = start->line1 + start->inserted;
X      prev = start;
X      start = start->link;
X      /* Threshold distance is 2*CONTEXT between two non-ignorable changes,
X        but only CONTEXT if one is ignorable.  */
X      thresh = ((prev->ignore || (start && start->ignore))
X               ? context
X               : 2 * context);
X      /* It is not supposed to matter which file we check in the end-test.
X        If it would matter, crash.  */
X      if (start && start->line0 - top0 != start->line1 - top1)
X       abort ();
X    } while (start
X            /* Keep going if less than THRESH lines
X               elapse before the affected line.  */
X            && start->line0 < top0 + thresh);
X
X  return prev;
X}
X
X/* Set the `ignore' flag properly in each change in SCRIPT.
X   It should be 1 if all the lines inserted or deleted in that change
X   are ignorable lines.  */
X
Xstatic void
Xmark_ignorable (script)
X     struct change *script;
X{
X  while (script)
X    {
X      struct change *next = script->link;
X      int first0, last0, first1, last1, deletes, inserts;
X
X      /* Turn this change into a hunk: detach it from the others.  */
X      script->link = 0;
X
X      /* Determine whether this change is ignorable.  */
X      analyze_hunk (script, &first0, &last0, &first1, &last1, &deletes, &inserts);
X      /* Reconnect the chain as before.  */
X      script->link = next;
X
X      /* If the change is ignorable, mark it.  */
X      script->ignore = (!deletes && !inserts);
X
X      /* Advance to the following change.  */
X      script = next;
X    }
X}
X
X/* Find the last function-header line in FILE prior to line number LINENUM.
X   This is a line containing a match for the regexp in `function_regexp'.
X   Store the address of the line text into LINEP and the length of the
X   line into LENP.
X   Do not store anything if no function-header is found.  */
X
Xstatic int
Xfind_function (file, linenum, linep, lenp)
X     struct file_data *file;
X     int linenum;
X     char **linep;
X     int *lenp;
X{
X  int i = linenum;
X  int last = find_function_last_search;
X  find_function_last_search = i;
X
X  while (--i >= last)
X    {
X      /* See if this line is what we want.  */
X
X      if (0 <= re_search (&function_regexp_compiled,
X                         files[0].linbuf[i].text,
X                         files[0].linbuf[i].length,
X                         0, files[0].linbuf[i].length,
X                         0))
X       {
X         *linep = files[0].linbuf[i].text;
X         *lenp = files[0].linbuf[i].length;
X         find_function_last_match = i;
X         return 1;
X       }
X    }
X  /* If we search back to where we started searching the previous time,
X     find the line we found last time.  */
X  if (find_function_last_match >= 0)
X    {
X      i = find_function_last_match;
X      *linep = files[0].linbuf[i].text;
X      *lenp = files[0].linbuf[i].length;
X      return 1;
X    }
X  return 0;
X}
SHAR_EOF
echo "extracting diff/diff.c"
sed 's/^X//' << \SHAR_EOF > diff/diff.c
X/* GNU DIFF main routine.
X   Copyright (C) 1988, 1989 Free Software Foundation, Inc.
X
XThis file is part of GNU DIFF.
X
XGNU DIFF is free software; you can redistribute it and/or modify
Xit under the terms of the GNU General Public License as published by
Xthe Free Software Foundation; either version 1, or (at your option)
Xany later version.
X
XGNU DIFF is distributed in the hope that it will be useful,
Xbut WITHOUT ANY WARRANTY; without even the implied warranty of
XMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
XGNU General Public License for more details.
X
XYou should have received a copy of the GNU General Public License
Xalong with GNU DIFF; see the file COPYING.  If not, write to
Xthe Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
X
X/* GNU DIFF was written by Mike Haertel, David Hayes,
X   Richard Stallman and Len Tower.  */
X
X#define GDIFF_MAIN
X#include "regex.h"
X#include "diff.h"
X
X
X/* Nonzero for -r: if comparing two directories,
X   compare their common subdirectories recursively.  */
X
Xint recursive;
X
X/* For debugging: don't do discard_confusing_lines.  */
X
Xint no_discards;
X
Xvoid specify_style();
X
X/* Return a string containing the command options with which diff was invoked.
X   Spaces appear between what were separate ARGV-elements.
X   There is a space at the beginning but none at the end.
X   If there were no options, the result is an empty string.
X
X   Arguments: VECTOR, a vector containing separate ARGV-elements, and COUNT,
X   the length of that vector.  */
X
Xstatic char *
Xoption_list (vector, count)
X     char **vector;
X     int count;
X{
X  int i;
X  int length = 0;
X  char *result;
X
X  for (i = 0; i < count; i++)
X    length += strlen (vector[i]) + 1;
X
X  result = (char *) xmalloc (length + 1);
X  result[0] = 0;
X
X  for (i = 0; i < count; i++)
X    {
X      strcat (result, " ");
X      strcat (result, vector[i]);
X    }
X
X  return result;
X}
X
Xmain (argc, argv)
X     int argc;
X     char *argv[];
X{
X  int val;
X  int c;
X  int prev = -1;
X
X  extern int optind;
X  extern char *optarg;
X
X  program = argv[0];
X
X  /* Do our initializations. */
X  output_style = OUTPUT_NORMAL;
X  always_text_flag = FALSE;
X  ignore_space_change_flag = FALSE;
X  ignore_all_space_flag = FALSE;
X  length_varies = FALSE;
X  ignore_case_flag = FALSE;
X  ignore_blank_lines_flag = FALSE;
X  ignore_regexp = 0;
X  function_regexp = 0;
X  print_file_same_flag = FALSE;
X  entire_new_file_flag = FALSE;
X  context = -1;
X  line_end_char = '\n';
X  tab_align_flag = FALSE;
X  tab_expand_flag = FALSE;
X  recursive = FALSE;
X  paginate_flag = FALSE;
X  heuristic = FALSE;
X  dir_start_file = NULL;
X  msg_chain = NULL;
X  msg_chain_end = NULL;
X  no_discards = 0;
X
X  /* Decode the options.  */
X
X  while ((c = getopt (argc, argv, "0123456789abBcC:defF:hHiI:lnNprsS:tTw"))
X        != EOF)
X    {
X      switch (c)
X       {
X         /* All digits combine in decimal to specify the context-size.  */
X       case '1':
X       case '2':
X       case '3':
X       case '4':
X       case '5':
X       case '6':
X       case '7':
X       case '8':
X       case '9':
X       case '0':
X         if (context == -1)
X           context = 0;
X         /* If a context length has already been specified,
X            more digits allowed only if they follow right after the others.
X            Reject two separate runs of digits, or digits after -C.  */
X         else if (prev < '0' || prev > '9')
X           fatal ("context length specified twice");
X
X         context = context * 10 + c - '0';
X         break;
X
X       case 'a':
X         /* Treat all files as text files; never treat as binary.  */
X         always_text_flag = 1;
X         break;
X
X       case 'b':
X         /* Ignore changes in amount of whitespace.  */
X         ignore_space_change_flag = 1;
X         length_varies = 1;
X         break;
X
X       case 'B':
X         /* Ignore changes affecting only blank lines.  */
X         ignore_blank_lines_flag = 1;
X         break;
X
X       case 'c':
X         /* Make context-style output.  */
X         specify_style (OUTPUT_CONTEXT);
X         break;
X
X       case 'C':
X         if (context >= 0)
X           fatal ("context length specified twice");
X         {
X           char *p;
X           for (p = optarg; *p; p++)
X             if (*p < '0' || *p > '9')
X               fatal ("invalid context length argument (-C option)");
X         }
X         context = atoi (optarg);
X         break;
X
X       case 'd':
X         /* Don't discard lines.  This makes things slower (sometimes much
X            slower) but will find a guaranteed minimal set of changes.  */
X         no_discards = 1;
X         break;
X
X       case 'e':
X         /* Make output that is a valid `ed' script.  */
X         specify_style (OUTPUT_ED);
X         break;
X
X       case 'f':
X         /* Make output that looks vaguely like an `ed' script
X            but has changes in the order they appear in the file.  */
X         specify_style (OUTPUT_FORWARD_ED);
X         break;
X
X       case 'F':
X         /* Show, for each set of changes, the previous line that
X            matches the specified regexp.  Currently affects only
X            context-style output.  */
X         function_regexp = optarg;
X         break;
X
X       case 'h':
X         /* Split the files into chunks of around 1500 lines
X            for faster processing.  Usually does not change the result.
X
X            This currently has no effect.  */
X         break;
X
X       case 'H':
X         /* Turn on heuristics that speed processing of large files
X            with a small density of changes.  */
X         heuristic = 1;
X         break;
X
X       case 'i':
X         /* Ignore changes in case.  */
X         ignore_case_flag = 1;
X         break;
X
X       case 'I':
X         /* Ignore changes affecting only lines that match the
X            specified regexp.  */
X         ignore_regexp = optarg;
X         break;
X
X       case 'l':
X         /* Pass the output through `pr' to paginate it.  */
X         paginate_flag = 1;
X         break;
X
X       case 'n':
X         /* Output RCS-style diffs, like `-f' except that each command
X            specifies the number of lines affected.  */
X         specify_style (OUTPUT_RCS);
X         break;
X
X       case 'N':
X         /* When comparing directories, if a file appears only in one
X            directory, treat it as present but empty in the other.  */
X         entire_new_file_flag = 1;
X         break;
X
X       case 'p':
X         /* Make context-style output and show name of last C function.  */
X         specify_style (OUTPUT_CONTEXT);
X         function_regexp = "^[_a-zA-Z]";
X         break;
X
X       case 'r':
X         /* When comparing directories,
X            recursively compare any subdirectories found.  */
X         recursive = 1;
X         break;
X
X       case 's':
X         /* Print a message if the files are the same.  */
X         print_file_same_flag = 1;
X         break;
X
X       case 'S':
X         /* When comparing directories, start with the specified
X            file name.  This is used for resuming an aborted comparison.  */
X         dir_start_file = optarg;
X         break;
X
X       case 't':
X         /* Expand tabs to spaces in the output so that it preserves
X            the alignment of the input files.  */
X         tab_expand_flag = 1;
X         break;
X
X       case 'T':
X         /* Use a tab in the output, rather than a space, before the
X            text of an input line, so as to keep the proper alignment
X            in the input line without changing the characters in it.  */
X         tab_align_flag = 1;
X         break;
X
X       case 'w':
X         /* Ignore horizontal whitespace when comparing lines.  */
X         ignore_all_space_flag = 1;
X         length_varies = 1;
X         break;
X       }
X      prev = c;
X    }
X
X  if (optind != argc - 2)
X    fatal ("requires two file names.  Usage: diff [-options] file1 file2");
X
X  /*
X   * @@ need more complicated usage string for directory options??
X   * Note three liner at top of BSD documentation, and John Gilmore
X   * message in his public domain tar being used by GNU.  
X   */
X
X  if (ignore_regexp)
X    {
X      char *val;
X      bzero (&ignore_regexp_compiled, sizeof ignore_regexp_compiled);
X      val = re_compile_pattern (ignore_regexp, strlen (ignore_regexp),
X                               &ignore_regexp_compiled);
X      if (val != 0)
X       error ("-I option: ", val);
X      ignore_regexp_compiled.fastmap = (char *) xmalloc (256);
X    }
X
X  if (function_regexp)
X    {
X      char *val;
X      bzero (&function_regexp_compiled, sizeof function_regexp_compiled);
X      val = re_compile_pattern (function_regexp, strlen (function_regexp),
X                               &function_regexp_compiled);
X      if (val != 0)
X       error ("-F option: ", val);
X      function_regexp_compiled.fastmap = (char *) xmalloc (256);
X    }
X
X  if (output_style != OUTPUT_CONTEXT)
X    context = 0;
X  else if (context == -1)
X    /* Default amount of context for -c.  */
X    context = 3;
X
X  switch_string = option_list (argv + 1, optind - 1);
X
X  val = compare_files (0, argv[optind], 0, argv[optind + 1], 0);
X
X  /* Print any messages that were saved up for last.  */
X  print_message_queue ();
X
X  exit (val);
X}
X
Xvoid specify_style (style)
X     enum output_style style;
X{
X  if (output_style != OUTPUT_NORMAL
X      && output_style != style)
X    error ("conflicting specifications of output style");
X  output_style = style;
X}
X
X/* Compare two files (or dirs) with specified names
X   DIR0/NAME0 and DIR1/NAME1, at level DEPTH in directory recursion.
X   (if DIR0 is 0, then the name is just NAME0, etc.)
X   This is self-contained; it opens the files and closes them.
X
X   Value is 0 if files are identical, 1 if different,
X   2 if there is a problem opening them.  */
X
Xint
Xcompare_files (dir0, name0, dir1, name1, depth)
X     char *dir0, *dir1;
X     char *name0, *name1;
X     int depth;
X{
X  struct file_data inf[2];
X  register int i;
X  int val;
X  int errorcount = 0;
X  int stat_result[2];
X
X  /* If this is directory comparison, perhaps we have a file
X     that exists only in one of the directories.
X     If so, just print a message to that effect.  */
X
X  if (! entire_new_file_flag && (name0 == 0 || name1 == 0))
X    {
X      char *name = name0 == 0 ? name1 : name0;
X      char *dir = name0 == 0 ? dir1 : dir0;
X      message ("Only in %s: %s\n", dir, name);
X      /* Return 1 so that diff_dirs will return 1 ("some files differ").  */
X      return 1;
X    }
X
X  /* Mark any nonexistent file with -1 in the desc field.  */
X
X  inf[0].desc = name0 == 0 ? -1 : 0;
X  inf[1].desc = name1 == 0 ? -1 : 0;
X
X  /* Now record the full name of each file, including nonexistent ones.  */
X
X  if (name0 == 0)
X    name0 = name1;
X  if (name1 == 0)
X    name1 = name0;
X
X  inf[0].name = dir0 == 0 ? name0 : concat (dir0, "/", name0);
X  inf[1].name = dir1 == 0 ? name1 : concat (dir1, "/", name1);
X
X  /* Stat the files.  Record whether they are directories.
X     Record in stat_result whether stat fails.  */
X
X  for (i = 0; i <= 1; i++)
X    {
X      inf[i].stat.st_size = 0;
X      inf[i].stat.st_mtime = 0;
X      inf[i].dir_p = 0;
X      stat_result[i] = 0;
X
X      if (inf[i].desc != -1
X         && strcmp (inf[i].name, "-"))
X       {
X         char *filename = inf[i].name;
X
X         stat_result[i] = stat (filename, &inf[i].stat);
X         if (stat_result[i] < 0)
X           {
X             perror_with_name (filename);
X             errorcount = 1;
X           }
X         else
X#ifdef AMIGA
X           inf[i].dir_p = (inf[i].stat.st_type > 0);
X#else
X           inf[i].dir_p = (S_IFDIR == (inf[i].stat.st_mode & S_IFMT));
X#endif
X       }
X    }
X
X  /* See if the two named files are actually the same physical file.
X     If so, we know they are identical without actually reading them.  */
X
X#ifndef AMIGA
X  if (inf[0].stat.st_ino == inf[1].stat.st_ino
X      && inf[0].stat.st_dev == inf[1].stat.st_dev
X      && stat_result[0] == 0
X      && stat_result[1] == 0)
X    {
X      val = 0;
X      goto done;
X    }
X#endif
X
X  if (name0 == 0)
X    inf[0].dir_p = inf[1].dir_p;
X  if (name1 == 0)
X    inf[1].dir_p = inf[0].dir_p;
X
X  /* Open the files and record their descriptors.  */
X
X  for (i = 0; i <= 1; i++)
X    {
X      if (inf[i].desc == -1)
X       ;
X      else if (!strcmp (inf[i].name, "-"))
X       {
X         inf[i].desc = fileno(stdin);
X         inf[i].name = "Standard Input";
X#ifdef AMIGA
X         inf[i].stat.st_type = -1;
X#endif
X       }
X      /* Don't bother opening if stat already failed.  */
X      else if (stat_result[i] == 0 && ! inf[i].dir_p)
X       {
X         char *filename = inf[i].name;
X
X         inf[i].desc = open (filename, O_RDONLY, 0);
X         if (0 > inf[i].desc)
X           {
X             perror_with_name (filename);
X             errorcount = 1;
X           }
X       }
X    }
X
X  if (errorcount)
X    {
X
X      /* If either file should exist but fails to be opened, return 2.  */
X
X      val = 2;
X
X    }
X  else if (inf[0].dir_p && inf[1].dir_p)
X    {
X
X      /* If both are directories, compare the files in them.  */
X
X      if (depth > 0 && !recursive)
X       {
X         /* But don't compare dir contents one level down
X            unless -r was specified.  */
X         message ("Common subdirectories: %s and %s\n",
X                  inf[0].name, inf[1].name);
X         val = 0;
X       }
X      else
X       {
X         val = diff_dirs (inf[0].name, inf[1].name,
X                          compare_files, depth, 0, 0);
X       }
X
X    }
X  else if (depth == 0 && (inf[0].dir_p || inf[1].dir_p))
X    {
X
X      /* If only one is a directory, and it was specified in the command line,
X        use the file in that dir whose basename matches the other file.  */
X
X      int dir_arg = (inf[0].dir_p ? 0 : 1);
X      int fnm_arg = (inf[0].dir_p ? 1 : 0);
X      char *p = strrchr(inf[fnm_arg].name, '/');
X      char *filename = concat (inf[dir_arg].name,  "/",
X                              (p ? p+1 : inf[fnm_arg].name));
X
X#ifdef AMIGA
X      inf[dir_arg].dir_p = (getfa(filename) == 1);
X      if (!inf[dir_arg].dir_p)
X        {
X        if (stat (filename,&inf[dir_arg].stat) < 0)
X         pfatal_with_name (filename);
X        inf[dir_arg].desc = open (filename, O_RDONLY, 0);
X        if (0 > inf[dir_arg].desc)
X          {
X            perror_with_name (filename);
X            val = 2;
X          }
X/*     free (inf[dir_arg].name); */
X       inf[dir_arg].name = filename;
X       val = diff_2_files (inf, depth);
X        }
X      else
X       {
X         error ("%s is a directory but %s is not",
X          inf[dir_arg].name, inf[fnm_arg].name);
X         val = 2;
X       }
X#else
X      inf[dir_arg].desc = open (filename, O_RDONLY, 0);
X
X      if (0 > inf[dir_arg].desc)
X       {
X         perror_with_name (filename);
X         val = 2;
X       }
X      else
X       {
X         /* JF: patch from the net to check and make sure we can really free
X            this.  If it's from argv[], freeing it is a *really* bad idea */
X         if (0 != (dir_arg ? dir1 : dir0))
X           free (inf[dir_arg].name);
X         inf[dir_arg].name = filename;
X         if (fstat (inf[dir_arg].desc, &inf[dir_arg].stat) < 0)
X           pfatal_with_name (inf[dir_arg].name);
X
X         inf[dir_arg].dir_p
X           = (S_IFDIR == (inf[dir_arg].stat.st_mode & S_IFMT));
X         if (inf[dir_arg].dir_p)
X           {
X             error ("%s is a directory but %s is not",
X                    inf[dir_arg].name, inf[fnm_arg].name);
X             val = 1;
X           }
X         else
X           val = diff_2_files (inf, depth);
X       }
X#endif
X    }
X  else if (depth > 0 && (inf[0].dir_p || inf[1].dir_p))
X    {
X      /* Perhaps we have a subdirectory that exists only in one directory.
X        If so, just print a message to that effect.  */
X
X      if (inf[0].desc == -1 || inf[1].desc == -1)
X       {
X         if (entire_new_file_flag && recursive)
X           val = diff_dirs (inf[0].name, inf[1].name, compare_files, depth,
X                            inf[0].desc == -1, inf[1].desc == -1);
X         else
X           {
X             char *dir = (inf[0].desc == -1) ? dir1 : dir0;
X             message ("Only in %s: %s\n", dir, name0);
X             val = 1;
X           }
X       }
X      else
X       {
X         /* We have a subdirectory in one directory
X            and a file in the other.  */
X
X         if (inf[0].dir_p)
X           message ("%s is a directory but %s is not\n",
X                    inf[0].name, inf[1].name);
X         else
X           message ("%s is a directory but %s is not\n",
X                    inf[1].name, inf[0].name);
X         /* This is a difference.  */
X         val = 1;
X       }
X    }
X  else
X    {
X
X      /* Both exist and both are ordinary files.  */
X
X      val = diff_2_files (inf, depth);
X
X    }
X
X  /* Now the comparison has been done, if no error prevented it,
X     and VAL is the value this function will return.  */
X
X  if (inf[0].desc > 0)
X    close (inf[0].desc);
X  if (inf[1].desc > 0)
X    close (inf[1].desc);
X
X done:
X  if (val == 0 && print_file_same_flag && !inf[0].dir_p)
X    message ("Files %s and %s are identical\n",
X            inf[0].name, inf[1].name);
X
X  fflush (stdout);
X
X  if (dir0 != 0)
X    free (inf[0].name);
X  if (dir1 != 0)
X    free (inf[1].name);
X
X  return val;
X}
SHAR_EOF
echo "extracting diff/diff3.c"
sed 's/^X//' << \SHAR_EOF > diff/diff3.c
X/* Three-way file comparison program (diff3) for Project GNU
X   Copyright (C) 1988, 1989 Free Software Foundation, Inc.
X
X   This program is free software; you can redistribute it and/or modify
X   it under the terms of the GNU General Public License as published by
X   the Free Software Foundation; either version 1, or (at your option)
X   any later version.
X
X   This program is distributed in the hope that it will be useful,
X   but WITHOUT ANY WARRANTY; without even the implied warranty of
X   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
X   GNU General Public License for more details.
X
X   You should have received a copy of the GNU General Public License
X   along with this program; if not, write to the Free Software
X   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
X
X
X/* Written by Randy Smith */
X
X/*
X * Include files.
X */
X#include <stdio.h>
X#include <ctype.h>
X
X#if defined(USG) || defined(AMIGA)
X/* Define needed BSD functions in terms of sysV library.  */
X
X#define bcopy(s,d,n)   memcpy((d),(s),(n))
X#define bcmp(s1,s2,n)  memcmp((s1),(s2),(n))
X#define bzero(s,n)     memset((s),0,(n))
X#endif
X
X#ifdef USG
X#define dup2(f,t)      (close(t),fcntl((f),F_DUPFD,(t)))
X
X#define vfork  fork
X#define index  strchr
X#define rindex strrchr
X#endif
X/*
X * Internal data structures and macros for the diff3 program; includes
X * data structures for both diff3 diffs and normal diffs.
X */
X
X/*
X * Different files within a diff
X */
X#define        FILE0   0
X#define        FILE1   1
X#define        FILE2   2
X
X/*
X * Three way diffs are build out of two two-way diffs; the file which
X * the two two-way diffs share is:
X */
X#define        FILEC   FILE0
X
X/* The ranges are indexed by */
X#define        START   0
X#define        END     1
X
Xenum diff_type {
X  ERROR,                       /* Should not be used */
X  ADD,                         /* Two way diff add */
X  CHANGE,                      /* Two way diff change */
X  DELETE,                      /* Two way diff delete */
X  DIFF_ALL,                    /* All three are different */
X  DIFF_1ST,                    /* Only the first is different */
X  DIFF_2ND,                    /* Only the second */
X  DIFF_3RD                     /* Only the third */
X};
X
X/* Two-way diff */
Xstruct diff_block {
X  int ranges[2][2];            /* Ranges are inclusive */
X  char **lines[2];             /* The actual lines (may contain nulls) */
X  int *lengths[2];             /* The lengths of the lines (since nulls) */
X  struct diff_block *next;
X};
X
X/* Three-way diff */
X
Xstruct diff3_block {
X  enum diff_type correspond;   /* Type of diff */
X  int ranges[3][2];            /* Ranges are inclusive */
X  char **lines[3];             /* The actual lines (may contain nulls) */
X  int *lengths[3];             /* The lengths of the lines (since nulls) */
X  struct diff3_block *next;
X};
X
X/*
X * Access the ranges on a diff block.
X */
X#define        D_LOWLINE(diff, filenum)        \
X  ((diff)->ranges[filenum][START])
X#define        D_HIGHLINE(diff, filenum)       \
X  ((diff)->ranges[filenum][END])
X#define        D_NUMLINES(diff, filenum)       \
X  (D_HIGHLINE((diff), (filenum)) - D_LOWLINE((diff), (filenum)) + 1)
X
X/*
X * Access the line numbers in a file in a diff by absolute line number
X * (i.e. line number within the original file).  Note that these are
X * lvalues and can be used for assignment.
X */
X#define        D_LINENUM(diff, filenum, linenum)       \
X  (*((diff)->lines[filenum] + linenum - D_LOWLINE((diff), (filenum))))
X#define        D_LINELEN(diff, filenum, linenum)       \
X  (*((diff)->lengths[filenum] + linenum - D_LOWLINE((diff), (filenum))))
X
X/*
X * Access the line numbers in a file in a diff by relative line
X * numbers (i.e. line number within the diff itself).  Note that these
X * are lvalues and can be used for assignment.
X */
X#define        D_RELNUM(diff, filenum, linenum)        \
X  (*((diff)->lines[filenum] + linenum))
X#define        D_RELLEN(diff, filenum, linenum)        \
X  (*((diff)->lengths[filenum] + linenum))
X
X/*
X * And get at them directly, when that should be necessary.
X */
X#define        D_LINEARRAY(diff, filenum)      \
X  ((diff)->lines[filenum])
X#define        D_LENARRAY(diff, filenum)       \
X  ((diff)->lengths[filenum])
X
X/*
X * Next block.
X */
X#define        D_NEXT(diff)    ((diff)->next)
X
X/*
X * Access the type of a diff3 block.
X */
X#define        D3_TYPE(diff)   ((diff)->correspond)
X
X/*
X * Line mappings based on diffs.  The first maps off the top of the
X * diff, the second off of the bottom.
X */
X#define        D_HIGH_MAPLINE(diff, fromfile, tofile, lineno)  \
X  ((lineno)                                            \
X   - D_HIGHLINE ((diff), (fromfile))                   \
X   + D_HIGHLINE ((diff), (tofile)))
X
X#define        D_LOW_MAPLINE(diff, fromfile, tofile, lineno)   \
X  ((lineno)                                            \
X   - D_LOWLINE ((diff), (fromfile))                    \
X   + D_LOWLINE ((diff), (tofile)))
X
X/*
X * General memory allocation function.
X */
X#define        ALLOCATE(number, type)  \
X  (type *) xmalloc ((number) * sizeof (type))
X
X/*
X * Options variables for flags set on command line.
X *
X * EDSCRIPT: Write out an ed script instead of the standard diff3 format.
X *
X * FLAGGING: Indicates that in the case of overlapping diffs (type
X * DIFF_ALL), the lines which would normally be deleted from file 1
X * should be preserved with a special flagging mechanism.
X *
X * DONT_WRITE_OVERLAP: 1 if information for overlapping diffs should
X * not be output.
X *
X * DONT_WRITE_SIMPLE: 1 if information for non-overlapping diffs
X * should not be output.
X *
X * FINALWRITE: 1 if a :wq should be included at the end of the script
X * to write out the file being edited.
X */
X#define DIFF_PROGRAM "rcs:diff"
X
Xint edscript;
Xint flagging;
Xint dont_write_overlap;
Xint dont_write_simple;
Xint finalwrite;
Xint overlaps;
Xextern int optind;
X
Xchar *argv0;
X
X/*
X * Forward function declarations.
X */
Xstruct diff_block *process_diff ();
Xstruct diff3_block *make_3way_diff ();
Xvoid output_diff3 ();
Xvoid output_diff3_edscript ();
Xvoid usage ();
Xvoid fatal ();
Xvoid perror_with_exit ();
X
Xstruct diff3_block *using_to_diff3_block ();
Xint copy_stringlist ();
Xstruct diff3_block *create_diff3_block ();
Xint compare_line_list ();
X
Xint read_diff ();
Xenum diff_type process_diff_control ();
Xchar *scan_diff_line ();
X
Xstruct diff3_block *reverse_diff3_blocklist ();
X
Xvoid *xmalloc ();
Xvoid *xrealloc ();
X
X/*
X * No options take arguments.  "i" is my own addition; it stands for
X * "include write command", to emulate system V behavior.
X */
X#define        ARGSTRING       "eix3EX"
X
Xchar diff_program[] = DIFF_PROGRAM;
X
X/*
X * Main program.  Calls diff twice on two pairs of input files,
X * combines the two diffs, and outputs them.
X */
Xmain (argc, argv)
X     int argc;
X     char **argv;
X{
X  int c;
X  int mapping [3];
X  int shiftmap;
X  int incompat;
X  struct diff_block *thread1, *thread2;
X  struct diff3_block *diff;
X
X  edscript = flagging = dont_write_overlap
X    = dont_write_simple = finalwrite = 0;
X  incompat = shiftmap = 0;
X
X  argv0 = argv[0];
X  
X  while ((c = getopt (argc, argv, ARGSTRING)) != EOF)
X    {
X      edscript = 1;
X      switch (c)
X       {
X       case 'x':
X         dont_write_simple = 1;
X         incompat++;
X         break;
X       case '3':
X         dont_write_overlap = 1;
X         incompat++;
X         break;
X       case 'i':
X         finalwrite = 1;
X         incompat++;
X         break;
X       case 'X':
X         dont_write_simple = 1;
X         /* Falls through */
X       case 'E':
X         flagging = 1;
X         /* Falls through */
X       case 'e':
X         incompat++;
X         break;
X       case '?':
X       default:
X         usage ();
X         /* NOTREACHED */
X       }
X    }
X
X  if (incompat > 1)         /* Make sure you only have one of a */
X                               /* set of arguments */
X    usage ();
X  
X  if (argc - optind != 3)
X    usage ();
X
X  if (*argv[optind] == '-' && *(argv[optind] + 1) == '\0')
X    {
X      /* Sigh.  We've got standard input as the first arg. We can't */
X      /* call diff twice on stdin */
X      mapping [0] = 1;
X      mapping [1] = 2;
X      mapping [2] = 0;
X      shiftmap = 1;
X    }
X  else
X    {
X      /* Normal, what you'd expect */
X      mapping [0] = 0;
X      mapping [1] = 1;
X      mapping [2] = 2;
X      shiftmap = 0;
X    }
X
X  if (shiftmap)
X    {
X      thread1 = process_diff (argv[optind + 2], argv[optind]);
X      thread2 = process_diff (argv[optind + 2], argv[optind + 1]);
X    }
X  else
X    {
X      thread1 = process_diff (argv[optind], argv[optind + 1]);
X      thread2 = process_diff (argv[optind], argv[optind + 2]);
X    }
X  diff = make_3way_diff (thread1, thread2);
X  if (edscript)
X    output_diff3_edscript (stdout, diff, mapping, argv[optind],
X                          argv[optind + 1], argv[optind + 2]);
X  else
X    output_diff3 (stdout, diff, mapping);
X  exit (overlaps);
X}
X      
X/*
X * Explain, patiently and kindly, how to use this program.  Then exit.
X */
Xvoid
Xusage ()
X{
X  fprintf (stderr, "Usage:\t%s [ -exEX3 ] [ -i ] file1 file2 file3\n",
X          argv0);
X  fprintf (stderr, "\tOnly one of [exEX3] allowed\n");
X  exit (1);
X}
X
X/*
X * Routines that combine the two diffs together into one.  The
X * algorithm used follows:
X *
X *   File0 is shared in common between the two diffs.
X *   Diff01 is the diff between 0 and 1.
X *   Diff02 is the diff between 0 and 2.
X *
X *     1) Find the range for the first block in File0.
X *         a) Take the lowest of the two ranges (in File0) in the two
X *            current blocks (one from each diff) as being the low
X *            water mark.  Assign the upper end of this block as
X *            being the high water mark and move the current block up
X *            one.  Mark the block just moved over as to be used.
X *         b) Check the next block in the diff that the high water
X *            mark is *not* from.  
X *            
X *            *If* the high water mark is above
X *            the low end of the range in that block,
X *
X *                mark that block as to be used and move the current
X *                block up.  Set the high water mark to the max of
X *                the high end of this block and the current.  Repeat b.
X *
X *      2) Find the corresponding ranges in Files1 (from the blocks
X *         in diff01; line per line outside of diffs) and in File2.
X *         Create a diff3_block, reserving space as indicated by the ranges.
X *        
X *      3) Copy all of the pointers for file0 in.  At least for now,
X *         do bcmp's between corresponding strings in the two diffs.
X *        
X *      4) Copy all of the pointers for file1 and 2 in.  Get what you
X *         need from file0 (when there isn't a diff block, it's
X *         identical to file0 within the range between diff blocks).
X *        
X *      5) If the diff blocks you used came from only one of the two
X *         strings of diffs, then that file (i.e. the one other than
X *         file 0 in that diff) is the odd person out.  If you used
X *         diff blocks from both sets, check to see if files 1 and 2 match:
X *        
X *             Same number of lines?  If so, do a set of bcmp's (if a
X *         bcmp matches; copy the pointer over; it'll be easier later
X *         if you have to do any compares).  If they match, 1 & 2 are
X *         the same.  If not, all three different.
X *
X *   Then you do it again, until you run out of blocks.
X *
X */
X
X/*
X * This routine makes a three way diff (chain of diff3_block's) from two
X * two way diffs (chains of diff_block's).  It is assumed that each of
X * the two diffs passed are off of the same file (i.e. that each of the
X * diffs were made "from" the same file).  The three way diff pointer
X * returned will have numbering 0--the common file, 1--the other file
X * in diff1, and 2--the other file in diff2.
X */
Xstruct diff3_block *
Xmake_3way_diff (thread1, thread2)
X     struct diff_block *thread1, *thread2;
X{
X/*
X * This routine works on the two diffs passed to it as threads.
X * Thread number 0 is diff1, thread number 1 is diff2.  The USING
X * array is set to the base of the list of blocks to be used to
X * construct each block of the three way diff; if no blocks from a
X * particular thread are to be used, that element of the using array
X * is set to 0.  The elements LAST_USING array are set to the last
X * elements on each of the using lists.
X *
X * The HIGH_WATER_MARK is set to the highest line number in File 0
X * described in any of the diffs in either of the USING lists.  The
X * HIGH_WATER_THREAD names the thread.  Similarly the BASE_WATER_MARK
X * and BASE_WATER_THREAD describe the lowest line number in File 0
X * described in any of the diffs in either of the USING lists.  The
X * HIGH_WATER_DIFF is the diff from which the HIGH_WATER_MARK was
X * taken.
X *
X * The HIGH_WATER_DIFF should always be equal to LAST_USING
X * [HIGH_WATER_THREAD].  The OTHER_DIFF is the next diff to check for
X * higher water, and should always be equal to
X * CURRENT[HIGH_WATER_THREAD ^ 0x1].  The OTHER_THREAD is the thread
X * in which the OTHER_DIFF is, and hence should always be equal to
X * HIGH_WATER_THREAD ^ 0x1.
X *
X * The variable LAST_DIFF is kept set to the last diff block produced
X * by this routine, for line correspondence purposes between that diff
X * and the one currently being worked on.  It is initialized to
X * ZERO_DIFF before any blocks have been created.
X */
X
X  struct diff_block
X    *using[2],
X    *last_using[2],
X    *current[2];
X
X  int
X    high_water_mark,
X    base_water_mark;
X
X  int
X    high_water_thread,
X    base_water_thread,
X    other_thread;
X
X  struct diff_block
X    *high_water_diff,
X    *other_diff;
X
X  struct diff3_block
X    *result,
X    *tmpblock,
X    *result_last,
X    *last_diff;
X
X  static struct diff3_block zero_diff = {
X      ERROR,
X      { {0, 0}, {0, 0}, {0, 0} },
X      { (char **) 0, (char **) 0, (char **) 0 },
X      { (int *) 0, (int *) 0, (int *) 0 },
X      (struct diff3_block *) 0
X      };
X
X  /* Initialization */
X  result = result_last = (struct diff3_block *) 0;
X  current[0] = thread1; current[1] = thread2;
X  last_diff = &zero_diff;
X
X  /* Sniff up the threads until we reach the end */
X
X  while (current[0] || current[1])
X    {
X      using[0] = using[1] = last_using[0] = last_using[1] =
X       (struct diff_block *) 0;
X
X      /* Setup low and high water threads, diffs, and marks */
X      if (!current[0])
X       base_water_thread = 1;
X      else if (!current[1])
X       base_water_thread = 0;
X      else
X       base_water_thread =
X         (D_LOWLINE (current[0], FILE0)
X          > D_LOWLINE (current[1], FILE0));
X      high_water_thread = base_water_thread;
X      
X      high_water_diff = current[high_water_thread];
X      
X      /* low and high waters start off same diff */
X      base_water_mark = D_LOWLINE (high_water_diff, FILE0);
X
X      high_water_mark = D_HIGHLINE (high_water_diff, FILE0);
X
X      /* Make the diff you just got info from into the using class */
X      using[high_water_thread]
X       = last_using[high_water_thread]
X       = high_water_diff;
X      current[high_water_thread] = high_water_diff->next;
X      last_using[high_water_thread]->next
X       = (struct diff_block *) 0;
X
X      /* And mark the other diff */
X      other_thread = high_water_thread ^ 0x1;
X      other_diff = current[other_thread];
X
X      /* Shuffle up the ladder, checking the other diff to see if it
X         needs to be incorporated */
X      while (other_diff
X            && D_LOWLINE (other_diff, FILE0) <= high_water_mark + 1)
X       {
X
X         /* Incorporate this diff into the using list.  Note that
X            this doesn't take it off the current list */
X         if (using[other_thread])
X           last_using[other_thread]->next = other_diff;
X         else
X           using[other_thread] = other_diff;
X         last_using[other_thread] = other_diff;
X
X         /* Take it off the current list.  Note that this following
X            code assumes that other_diff enters it equal to
X            current[high_water_thread ^ 0x1] */
X         current[other_thread]
X           = current[other_thread]->next;
X         other_diff->next
X           = (struct diff_block *) 0;
X
X         /* Set the high_water stuff
X            If this comparison is equal, then this is the last pass
X            through this loop; since diff blocks within a given
X            thread cannot overlap, the high_water_mark will be
X            *below* the range_start of either of the next diffs. */
X
X         if (high_water_mark < D_HIGHLINE (other_diff, FILE0))
X           {
X             high_water_thread ^= 1;
X             high_water_diff = other_diff;
X             high_water_mark = D_HIGHLINE (other_diff, FILE0);
X           }
X
X         /* Set the other diff */
X         other_thread = high_water_thread ^ 0x1;
X         other_diff = current[other_thread];
X       }
X
X      /* The using lists contain a list of all of the blocks to be
X         included in this diff3_block.  Create it.  */
X
X      tmpblock = using_to_diff3_block (using, last_using,
X                                      base_water_thread, high_water_thread,
X                                      last_diff);
X
X      if (!tmpblock)
X       fatal ("internal: screwup in format of diff blocks");
X
X      /* Put it on the list */
X      if (result)
X       result_last->next = tmpblock;
X      else
X       result = tmpblock;
X      result_last = tmpblock;
X
X      /* Setup corresponding lines correctly */
X      last_diff = tmpblock;
X    }
X  return result;
X}
X
X/*
X * using_to_diff3_block:
X *   This routine takes two lists of blocks (from two separate diff
X * threads) and puts them together into one diff3 block.
X * It then returns a pointer to this diff3 block or 0 for failure.
X *
X * All arguments besides using are for the convenience of the routine;
X * they could be derived from the using array.
X * LAST_USING is a pair of pointers to the last blocks in the using
X * structure.
X * LOW_THREAD and HIGH_THREAD tell which threads contain the lowest
X * and highest line numbers for File0.
X * last_diff contains the last diff produced in the calling routine.
X * This is used for lines mappings which would still be identical to
X * the state that diff ended in.
X *
X * A distinction should be made in this routine between the two diffs
X * that are part of a normal two diff block, and the three diffs that
X * are part of a diff3_block.
X */
Xstruct diff3_block *
Xusing_to_diff3_block (using, last_using, low_thread, high_thread, last_diff)
X     struct diff_block
X       *using[2],
X       *last_using[2];
X     int low_thread, high_thread;
X     struct diff3_block *last_diff;
X{
X  int lowc, highc, low1, high1, low2, high2;
X  struct diff3_block *result;
X  struct diff_block *ptr;
X  int i;
X  int current0line;
X  
X  /* Find the range in file0 */
X  lowc = using[low_thread]->ranges[0][START];
X  highc = last_using[high_thread]->ranges[0][END];
X
X  /* Find the ranges in the other files.
X     If using[x] is null, that means that the file to which that diff
X     refers is equivalent to file 0 over this range */
X  
X  if (using[0])
X    {
X      low1 = D_LOW_MAPLINE (using[0], FILE0, FILE1, lowc);
X      high1 = D_HIGH_MAPLINE (last_using[0], FILE0, FILE1, highc);
X    }
X  else
X    {
X      low1 = D_HIGH_MAPLINE (last_diff, FILEC, FILE1, lowc);
X      high1 = D_HIGH_MAPLINE (last_diff, FILEC, FILE1, highc);
X    }
X
X  /*
X   * Note that in the following, we use file 1 relative to the diff,
X   * and file 2 relative to the corresponding lines struct.
X   */
X  if (using[1])
X    {
X      low2 = D_LOW_MAPLINE (using[1], FILE0, FILE1, lowc);
X      high2 = D_HIGH_MAPLINE (last_using[1], FILE0, FILE1, highc);
X    }
X  else
X    {
X      low2 = D_HIGH_MAPLINE (last_diff, FILEC, FILE2, lowc);
X      high2 = D_HIGH_MAPLINE (last_diff, FILEC, FILE2, highc);
X    }
X
X  /* Create a block with the appropriate sizes */
X  result = create_diff3_block (lowc, highc, low1, high1, low2, high2);
X
X  /* Copy over all of the information for File 0.  Return with a zero
X     if any of the compares failed. */
X  for (ptr = using[0]; ptr; ptr = D_NEXT (ptr))
X    {
X      int result_offset = D_LOWLINE (ptr, FILE0) - lowc;
X      int copy_size
X       = D_HIGHLINE (ptr, FILE0) - D_LOWLINE (ptr, FILE0) + 1;
X      
X      if (!copy_stringlist (D_LINEARRAY (ptr, FILE0),
X                           D_LENARRAY (ptr, FILE0),
X                           D_LINEARRAY (result, FILEC) + result_offset,
X                           D_LENARRAY (result, FILEC) + result_offset,
X                           copy_size))
X       return 0;
X    }
X
X  for (ptr = using[1]; ptr; ptr = D_NEXT (ptr))
X    {
X      int result_offset = D_LOWLINE (ptr, FILEC) - lowc;
X      int copy_size
X       = D_HIGHLINE (ptr, FILEC) - D_LOWLINE (ptr, FILEC) + 1;
X      
X      if (!copy_stringlist (D_LINEARRAY (ptr, FILE0),
X                           D_LENARRAY (ptr, FILE0),
X                           D_LINEARRAY (result, FILEC) + result_offset,
X                           D_LENARRAY (result, FILEC) + result_offset,
X                           copy_size))
X       return 0;
X    }
X
X  /* Copy stuff for file 1.  First deal with anything that might be
X     before the first diff. */
X
X  for (i = 0;
X       i + low1 < (using[0] ? D_LOWLINE (using[0], FILE1) : high1 + 1);
X       i++)
X    {
X      D_RELNUM (result, FILE1, i) = D_RELNUM (result, FILEC, i);
X      D_RELLEN (result, FILE1, i) = D_RELLEN (result, FILEC, i);
X    }
X  
X  for (ptr = using[0]; ptr; ptr = D_NEXT (ptr))
X    {
X      int result_offset = D_LOWLINE (ptr, FILE1) - low1;
X      int copy_size
X       = D_HIGHLINE (ptr, FILE1) - D_LOWLINE (ptr, FILE1) + 1;
X
X      if (!copy_stringlist (D_LINEARRAY (ptr, FILE1),
X                           D_LENARRAY (ptr, FILE1),
X                           D_LINEARRAY (result, FILE1) + result_offset,
X                           D_LENARRAY (result, FILE1) + result_offset,
X                           copy_size))
X       return 0;
X
X      /* Catch the lines between here and the next diff */
X      current0line = D_HIGHLINE (ptr, FILE0) + 1 - lowc;
X      for (i = D_HIGHLINE (ptr, FILE1) + 1 - low1;
X          i < (D_NEXT (ptr) ?
X               D_LOWLINE (D_NEXT (ptr), FILE1) :
X               high1 + 1) - low1;
X          i++)
X       {
X         D_RELNUM (result, FILE1, i)
X           = D_RELNUM (result, FILEC, current0line);
X         D_RELLEN (result, FILE1, i)
X           = D_RELLEN (result, FILEC, current0line++);
X       }
X    }
X
X  /* Copy stuff for file 2.  First deal with anything that might be
X     before the first diff. */
X
X  for (i = 0;
X       i + low2 < (using[1] ? D_LOWLINE (using[1], FILE1) : high2 + 1);
X       i++)
X    {
X      D_RELNUM (result, FILE2, i) = D_RELNUM (result, FILEC, i);
X      D_RELLEN (result, FILE2, i) = D_RELLEN (result, FILEC, i);
X    }
X  
X  for (ptr = using[1]; ptr; ptr = D_NEXT (ptr))
X    {
X      int result_offset = D_LOWLINE (ptr, FILE1) - low2;
X      int copy_size
X       = D_HIGHLINE (ptr, FILE1) - D_LOWLINE (ptr, FILE1) + 1;
X
X      if (!copy_stringlist (D_LINEARRAY (ptr, FILE1),
X                           D_LENARRAY (ptr, FILE1),
X                           D_LINEARRAY (result, FILE2) + result_offset,
X                           D_LENARRAY (result, FILE2) + result_offset,
X                           copy_size))
X       return 0;
X
X      /* Catch the lines between here and the next diff */
X      current0line = D_HIGHLINE (ptr, FILE0) + 1 - lowc;
X      for (i = D_HIGHLINE (ptr, FILE1) + 1 - low2;
X          i < (D_NEXT (ptr) ?
X               D_LOWLINE (D_NEXT (ptr), FILE1) :
X               high2 + 1) - low2;
X          i++)
X       {
X         D_RELNUM (result, FILE2, i)
X           = D_RELNUM (result, FILEC, current0line);
X         D_RELLEN (result, FILE2, i)
X           = D_RELLEN (result, FILEC, current0line++);
X       }
X    }
X
X  /* Set correspond */
X  if (!using[0])
X    D3_TYPE (result) = DIFF_3RD;
X  else if (!using[1])
X    D3_TYPE (result) = DIFF_2ND;
X  else
X    {
X      int nl1
X       = D_HIGHLINE (result, FILE1) - D_LOWLINE (result, FILE1) + 1;
X      int nl2
X       = D_HIGHLINE (result, FILE2) - D_LOWLINE (result, FILE2) + 1;
X
X      if (nl1 != nl2
X         || !compare_line_list (D_LINEARRAY (result, FILE1),
X                                D_LENARRAY (result, FILE1),
X                                D_LINEARRAY (result, FILE2),
X                                D_LENARRAY (result, FILE2),
X                                nl1))
X       D3_TYPE (result) = DIFF_ALL;
X      else
X       D3_TYPE (result) = DIFF_1ST;
X    }
X  
X  return result;
X}
X
X/*
X * This routine copies pointers from a list of strings to a different list
X * of strings.  If a spot in the second list is already filled, it
X * makes sure that it is filled with the same string; if not it
X * returns 0, the copy incomplete.
X * Upon successful completion of the copy, it returns 1.
X */
Xint
Xcopy_stringlist (fromptrs, fromlengths, toptrs, tolengths, copynum)
X     char *fromptrs[], *toptrs[];
X     int *fromlengths, *tolengths;
X     int copynum;
X{
X  register char
X    **f = fromptrs,
X    **t = toptrs;
X  register int
X    *fl = fromlengths,
X    *tl = tolengths;
X  
X  while (copynum--)
X    {
X      if (*t)
X       {
X         if (*fl != *tl || bcmp (*f, *t, *fl))
X            return 0;
X        }
X      else
X       { *t = *f ; *tl = *fl; }
X
X      t++; f++; tl++; fl++;
X    }
X  return 1;
X}
X
X/*
X * Create a diff3_block, with ranges as specified in the arguments.
X * Allocate the arrays for the various pointers (and zero them) based
X * on the arguments passed.  Return the block as a result.
X */
Xstruct diff3_block *
Xcreate_diff3_block (low0, high0, low1, high1, low2, high2)
X     register int low0, high0, low1, high1, low2, high2;
X{
X  struct diff3_block *result = ALLOCATE (1, struct diff3_block);
X  int numlines;
X
X  D3_TYPE (result) = ERROR;
X
X  /* Assign ranges */
X  D_LOWLINE (result, FILE0) = low0;
X  D_HIGHLINE (result, FILE0) = high0;
X  D_LOWLINE (result, FILE1) = low1;
X  D_HIGHLINE (result, FILE1) = high1;
X  D_LOWLINE (result, FILE2) = low2;
X  D_HIGHLINE (result, FILE2) = high2;
X
X  /* Allocate and zero space */
X  numlines = D_NUMLINES (result, FILE0);
X  if (numlines)
X    {
X      D_LINEARRAY (result, FILE0) = ALLOCATE (numlines, char *);
X      D_LENARRAY (result, FILE0) = ALLOCATE (numlines, int);
X      bzero (D_LINEARRAY (result, FILE0), (numlines * sizeof (char *)));
X      bzero (D_LENARRAY (result, FILE0), (numlines * sizeof (int)));
X    }
X  else
X    {
X      D_LINEARRAY (result, FILE0) = (char **) 0;
X      D_LENARRAY (result, FILE0) = (int *) 0;
X    }
X
X  numlines = D_NUMLINES (result, FILE1);
X  if (numlines)
X    {
X      D_LINEARRAY (result, FILE1) = ALLOCATE (numlines, char *);
X      D_LENARRAY (result, FILE1) = ALLOCATE (numlines, int);
X      bzero (D_LINEARRAY (result, FILE1), (numlines * sizeof (char *)));
X      bzero (D_LENARRAY (result, FILE1), (numlines * sizeof (int)));
X    }
X  else
X    {
X      D_LINEARRAY (result, FILE1) = (char **) 0;
X      D_LENARRAY (result, FILE1) = (int *) 0;
X    }
X
X  numlines = D_NUMLINES (result, FILE2);
X  if (numlines)
X    {
X      D_LINEARRAY (result, FILE2) = ALLOCATE (numlines, char *);
X      D_LENARRAY (result, FILE2) = ALLOCATE (numlines, int);
X      bzero (D_LINEARRAY (result, FILE2), (numlines * sizeof (char *)));
X      bzero (D_LENARRAY (result, FILE2), (numlines * sizeof (int)));
X    }
X  else
X    {
X      D_LINEARRAY (result, FILE2) = (char **) 0;
X      D_LENARRAY (result, FILE2) = (int *) 0;
X    }
X
X  /* Return */
X  return result;
X}
X
X/*
X * Compare two lists of lines of text.
X * Return 1 if they are equivalent, 0 if not.
X */
Xint
Xcompare_line_list (list1, lengths1, list2, lengths2, nl)
X     char *list1[], *list2[];
X     int *lengths1, *lengths2;
X     int nl;
X{
X  char
X    **l1 = list1,
X    **l2 = list2;
X  int
X    *lgths1 = lengths1,
X    *lgths2 = lengths2;
X  
X  while (nl--)
X    if (!*l1 || !*l2 || *lgths1 != *lgths2++
X       || bcmp (*l1++, *l2++, *lgths1++))
X      return 0;
X  return 1;
X}
X
X/*
X * Routines to input and parse two way diffs.
X */
X
Xextern char *environ;          /* I hope this is here */
X
X#define        DIFF_CHUNK_SIZE 10000
X
Xstruct diff_block *
Xprocess_diff (filea, fileb)
X     char *filea, *fileb;
X{
X  char *diff_contents;
X  int diff_size;
X  char *scan_diff;
X  enum diff_type dt;
X  int i;
X  struct diff_block *block_list, *block_list_end, *bptr;
X
X  diff_size = read_diff (filea, fileb, &diff_contents);
X  scan_diff = diff_contents;
X  bptr = block_list_end = block_list = (struct diff_block *) 0;
X
X  while (scan_diff - diff_contents < diff_size)
X    {
X      bptr = ALLOCATE (1, struct diff_block);
X      bptr->lines[0] = bptr->lines[1] = (char **) 0;
X      bptr->lengths[0] = bptr->lengths[1] = (int *) 0;
X      
X      dt = process_diff_control (&scan_diff, bptr);
X      if (dt == ERROR) fatal ("Bad format in diff output");
X      if (*scan_diff != '\n') fatal ("Bad format in diff output");
X      scan_diff++;
X      
X      /* Force appropriate ranges to be null, if necessary */
X      switch (dt)
X       {
X       case ADD:
X         bptr->ranges[0][0]++;
X         break;
X       case DELETE:
X         bptr->ranges[1][0]++;
X         break;
X       case CHANGE:
X         break;
X       default:
X         fatal ("internal: Bad diff type in process_diff");
X         break;
X       }
X      
X      /* Allocate space for the pointers for the lines from filea, and
X        parcel them out among these pointers */
X      if (dt != ADD)
X       {
X         bptr->lines[0] = ALLOCATE ((bptr->ranges[0][END]
X                                     - bptr->ranges[0][START] + 1),
X                                    char *);
X         bptr->lengths[0] = ALLOCATE ((bptr->ranges[0][END]
X                                       - bptr->ranges[0][START] + 1),
X                                      int);
X         for (i = 0; i <= (bptr->ranges[0][END]
X                           - bptr->ranges[0][START]); i++)
X           scan_diff = scan_diff_line (scan_diff,
X                                       &(bptr->lines[0][i]),
X                                       &(bptr->lengths[0][i]),
X                                       diff_contents + diff_size,
X                                       '<');
X       }
X      
X      /* Get past the separator for changes */
X      if (dt == CHANGE)
X       {
X         if (strncmp (scan_diff, "---\n", 4))
X           fatal ("Bad diff format: bad change separator");
X         scan_diff += 4;
X       }
X      
X      /* Allocate space for the pointers for the lines from fileb, and
X        parcel them out among these pointers */
X      if (dt != DELETE)
X       {
X         bptr->lines[1] = ALLOCATE ((bptr->ranges[1][END]
X                                     - bptr->ranges[1][START] + 1),
X                                    char *);
X         bptr->lengths[1] = ALLOCATE ((bptr->ranges[1][END]
X                                       - bptr->ranges[1][START] + 1),
X                                      int);
X         for (i = 0; i <= (bptr->ranges[1][END]
X                           - bptr->ranges[1][START]); i++)
X           scan_diff = scan_diff_line (scan_diff,
X                                       &(bptr->lines[1][i]),
X                                       &(bptr->lengths[1][i]),
X                                       diff_contents + diff_size,
X                                       '>');
X       }
X      
X      /* Place this block on the blocklist */
X      if (block_list_end)
X       block_list_end->next = bptr;
X      else
X       block_list = bptr;
X      
X      block_list_end = bptr;
X      
X    }
X
X  if (scan_diff - diff_contents != diff_size)
X    fatal ("bad diff format; incomplete last line");
X
X  return block_list;
X}
X
X/*
X * This routine will parse a normal format diff control string.  It
X * returns the type of the diff (ERROR if the format is bad).  All of
X * the other important information is filled into to the structure
X * pointed to by db, and the string pointer (whose location is passed
X * to this routine) is updated to point beyond the end of the string
X * parsed.  Note that only the ranges in the diff_block will be set by
X * this routine.
X *
X * If some specific pair of numbers has been reduced to a single
X * number, then both corresponding numbers in the diff block are set
X * to that number.  In general these numbers are interpetted as ranges
X * inclusive, unless being used by the ADD or DELETE commands.  It is
X * assumed that these will be special cased in a superior routine.  
X */
X
Xenum diff_type
Xprocess_diff_control (string, db)
X     char **string;
X     struct diff_block *db;
X{
X  char *s = *string;
X  int holdnum;
X  enum diff_type type;
X
X/* These macros are defined here because they can use variables
X   defined in this function.  Don't try this at home kids, we're
X   trained professionals!
X
X   Also note that SKIPWHITE only recognizes tabs and spaces, and
X   that READNUM can only read positive, integral numbers */
X
X#define        SKIPWHITE(s)    { while (*s == ' ' || *s == '\t') s++; }
X#define        READNUM(s, num) \
X       { if (!isdigit (*s)) return ERROR; holdnum = 0; \
X         do { holdnum = (*s++ - '0' + holdnum * 10); } \
X         while (isdigit (*s)); (num) = holdnum; }
X
X  /* Read first set of digits */
X  SKIPWHITE (s);
X  READNUM (s, db->ranges[0][START]);
X
X  /* Was that the only digit? */
X  SKIPWHITE(s);
X  if (*s == ',')
X    {
X      /* Get the next digit */
X      s++;
X      READNUM (s, db->ranges[0][END]);
X    }
X  else
X    db->ranges[0][END] = db->ranges[0][START];
X
X  /* Get the letter */
X  SKIPWHITE (s);
X  switch (*s)
X    {
X    case 'a':
X      type = ADD;
X      break;
X    case 'c':
X      type = CHANGE;
X      break;
X    case 'd':
X      type = DELETE;
X      break;
X    default:
X      return ERROR;                    /* Bad format */
X    }
X  s++;                         /* Past letter */
X  
X  /* Read second set of digits */
X  SKIPWHITE (s);
X  READNUM (s, db->ranges[1][START]);
X
X  /* Was that the only digit? */
X  SKIPWHITE(s);
X  if (*s == ',')
X    {
X      /* Get the next digit */
X      s++;
X      READNUM (s, db->ranges[1][END]);
X      SKIPWHITE (s);           /* To move to end */
X    }
X  else
X    db->ranges[1][END] = db->ranges[1][START];
X
X  *string = s;
X  return type;
X}
X
Xint
Xread_diff (filea, fileb, output_placement)
X     char *filea, *fileb;
X     char **output_placement;
X{
X  char *cmd;
X  void *malloc();
X  int pipefd;
X  FILE *pipefp, *popenl();
X  char *diff_result;
X  long current_chunk_size;
X  int bytes;
X  int total;
X
X  cmd = (char *)malloc(strlen(diff_program) + strlen(filea) + strlen(fileb) + 2);
X  if (cmd == NULL) {
X       printf("Couldn't obtain memory for diff command\n");
X       exit(1);
X       }
X
X  pipefp = popenl(diff_program, filea, fileb, NULL, "r");
X  if (pipefp == NULL) {
X       printf("Couldn't open pipe to diff program\n");
X       exit(1);
X       }
X  pipefd = fileno(pipefp);
X  current_chunk_size = DIFF_CHUNK_SIZE;
X  diff_result = (char *) xmalloc (current_chunk_size);
X  total = 0;
X  do {
X    bytes = myread (pipefd,
X                   diff_result + total,
X                   current_chunk_size - total);
X    total += bytes;
X    if (total == current_chunk_size)
X      diff_result = (char *) xrealloc (diff_result, (current_chunk_size *= 2));
X  } while (bytes);
X
X  *output_placement = diff_result;
X  pclose(pipefp);
X  return total;
X}
X
X
X/*
X * Scan a regular diff line (consisting of > or <, followed by a
X * space, followed by text (including nulls) up to a newline.
X *
X * This next routine began life as a macro and many parameters in it
X * are used as call-by-reference values.
X */
Xchar *
Xscan_diff_line (scan_ptr, set_start, set_length, limit, firstchar)
X     char *scan_ptr, **set_start;
X     int *set_length;
X     char *limit;
X     char firstchar;
X{
X  char *line_ptr = scan_ptr + 2;
X
X  if (!(scan_ptr[0] == (firstchar)
X       && scan_ptr[1] == ' '))
X    fatal ("Bad diff format; incorrect leading line chars");
X
X  *set_start = line_ptr;
X  while (*line_ptr != '\n') line_ptr++;
X  
X  if (line_ptr >= limit)
X    fatal ("Bad diff format; overflow in parse");
X
X  /* Don't include newline, but do return the beginning of the
X     next line */
X  *set_length = line_ptr - *set_start;
X
X  return line_ptr + 1;
X}
X
X/*
X * This routine outputs a three way diff passed as a list of
X * diff3_block's.
X * The argument MAPPING is indexed by external file number (in the
X * argument list) and contains the internal file number (from the
X * diff passed).  This is important because the user expects his
X * outputs in terms of the argument list number, and the diff passed
X * may have been done slightly differently (if the first argument in
X * the argument list was the standard input, for example).
X */
Xvoid
Xoutput_diff3 (outputfile, diff, mapping)
X     FILE *outputfile;
X     struct diff3_block *diff;
X     int mapping[3];
X{
X  int rev_mapping[3];
X  static int eliminate[3] = { 1, 0, 0};
X  int i;
X  int oddoneout;
X  char *cp;
X  struct diff3_block *ptr;
X  int line;
X  int dontprint;
X  static int skew_increment[3] = { 2, 3, 1 }; /* 0==>2==>1==>3 */
X
X  for (i = 0; i < 3; i++)
X    rev_mapping [mapping[i]] = i;
X
X  for (ptr = diff; ptr; ptr = D_NEXT (ptr))
X    {
X      char x[2];
X
X      switch (ptr->correspond)
X       {
X       case DIFF_ALL:
X         x[0] = '\0';
X         dontprint = 3;        /* Print them all */
X         oddoneout = 3;        /* Nobody's odder than anyone else */
X         break;
X       case DIFF_1ST:
X       case DIFF_2ND:
X       case DIFF_3RD:
X         oddoneout = rev_mapping[(int) ptr->correspond - (int) DIFF_1ST];
X          
X         x[0] = oddoneout + '1';
X         x[1] = '\0';
X         dontprint = eliminate [oddoneout];
X         break;
X       default:
X         fatal ("internal: Bad diff type passed to output");
X       }
X      fprintf (outputfile, "====%s\n", x);
X
X      /* Go 0, 2, 1 if the first and third outputs are equivalent. */
X      for (i = 0; i < 3;
X          i = (oddoneout == 1 ? skew_increment[i] : i + 1))
X       {
X         int realfile = mapping[i];
X         int
X           lowt = D_LOWLINE (ptr, realfile),
X           hight = D_HIGHLINE (ptr, realfile);
X        
X         fprintf (outputfile, "%d:", i + 1);
X         switch (lowt - hight)
X           {
X           case 1:
X             fprintf (outputfile, "%da\n", lowt - 1);
X             break;
X           case 0:
X             fprintf (outputfile, "%dc\n", lowt);
X             break;
X           default:
X             fprintf (outputfile, "%d,%dc\n", lowt, hight);
X             break;
X           }
X
X         if (i == dontprint) continue;
X
X         for (line = 0; line < hight - lowt + 1; line++)
X           {
X             fprintf (outputfile, "  ");
X             for (cp = D_RELNUM (ptr, realfile, line);
X                  cp < (D_RELNUM (ptr, realfile, line)
X                        + D_RELLEN (ptr, realfile, line));
X                  cp++)
X               putc (*cp, outputfile);
X             putc ('\n', outputfile);
X           }
X       }
X    }
X}
X
X/*
X * This routine outputs a diff3 set of blocks as an ed script.  This
X * script applies the changes between file's 2 & 3 to file 1.  It
X * takes the precise format of the ed script to be output from global
X * variables set during options processing.  Note that it does
X * destructive things to the set of diff3 blocks it is passed; it
X * reverses their order (this gets around the problems involved with
X * changing line numbers in an ed script).
X *
X * Note that this routine has the same problem of mapping as the last
X * one did; the variable MAPPING maps from file number according to
X * the argument list to file number according to the diff passed.  All
X * files listed below are in terms of the argument list.
X *
X * Also, occasionally this routine needs the real names of the files
X * on which it works.  Thus file0, file1, and file2 are the filenames
X * passed on the command line.
X *
X * See options.h for documentation on the global variables which this
X * routine pays attention to.
X */
Xvoid
Xoutput_diff3_edscript (outputfile, diff, mapping, file0, file1, file2)
X     FILE *outputfile;
X     struct diff3_block *diff;
X     int mapping[3];
X     char *file0, *file1, *file2;
X{
X  int rev_mapping[3];
X  int i;
X  int leading_dot;
X  struct diff3_block *newblock, *thisblock;
X  char *cp;
X
X  leading_dot = 0;
X
X  for (i = 0; i < 3; i++)
X    rev_mapping [mapping [i]] = i;
X
X  newblock = reverse_diff3_blocklist (diff);
X
X  for (thisblock = newblock; thisblock; thisblock = thisblock->next)
X    {
X      /* Must do mapping correctly.  */
X      enum diff_type type
X       = ((thisblock->correspond == DIFF_ALL) ?
X          DIFF_ALL :
X          ((enum diff_type)
X           (((int) DIFF_1ST)
X            + rev_mapping [(int) thisblock->correspond - (int) DIFF_1ST])));
X
X      /* If we aren't supposed to do this output block, skip it */
X      if (type == DIFF_2ND || type == DIFF_1ST
X         || (type == DIFF_3RD && dont_write_simple)
X         || (type == DIFF_ALL && dont_write_overlap))
X       continue;
X
X      if (flagging && type == DIFF_ALL)
X       /* Do special flagging */
X       {
X         overlaps++;
X         /* Put in lines from FILE2 with bracket */
X         fprintf (outputfile, "%da\n",
X                  D_HIGHLINE (thisblock, mapping [FILE0]));
X         fprintf (outputfile, "=======\n");
X         for (i = 0;
X              i < D_NUMLINES (thisblock, mapping [FILE2]);
X              i++)
X           {
X             if (D_RELNUM (thisblock, mapping[FILE2], i)[0] == '.')
X               { leading_dot = 1; fprintf(outputfile, "."); }
X             for (cp = D_RELNUM (thisblock, mapping [FILE2], i);
X                  cp < (D_RELNUM (thisblock, mapping [FILE2], i)
X                        + D_RELLEN (thisblock, mapping [FILE2], i));
X                  cp++)
X               putc (*cp, outputfile);
X             putc ('\n', outputfile);
X           }
X         fprintf (outputfile, ">>>>>>> %s\n.\n", file2);
X
X         /* Add in code to take care of leading dots, if necessary. */
X         if (leading_dot)
X           {
X             fprintf (outputfile, "%d,%ds/^\\.\\./\\./\n",
X                      D_HIGHLINE (thisblock, mapping [FILE0]) + 1,
X                      (D_HIGHLINE (thisblock, mapping [FILE0])
X                       + D_NUMLINES (thisblock, mapping [FILE2])));
X             leading_dot = 0;
X           }
X
X         /* Put in code to do initial bracket of lines from FILE0  */
X         fprintf (outputfile, "%da\n<<<<<<< %s\n.\n",
X                  D_LOWLINE (thisblock, mapping[FILE0]) - 1,
X                  file0);
X       }
X      else if (D_NUMLINES (thisblock, mapping [FILE2]) == 0)
X       /* Write out a delete */
X       {
X         if (D_NUMLINES (thisblock, mapping [FILE0]) == 1)
X           fprintf (outputfile, "%dd\n",
X                    D_LOWLINE (thisblock, mapping [FILE0]));
X         else
X           fprintf (outputfile, "%d,%dd\n",
X                    D_LOWLINE (thisblock, mapping [FILE0]),
X                    D_HIGHLINE (thisblock, mapping [FILE0]));
X       }
X      else
X       /* Write out an add or change */
X       {
X         switch (D_NUMLINES (thisblock, mapping [FILE0]))
X           {
X           case 0:
X             fprintf (outputfile, "%da\n",
X                      D_HIGHLINE (thisblock, mapping [FILE0]));
X             break;
X           case 1:
X             fprintf (outputfile, "%dc\n",
X                      D_HIGHLINE (thisblock, mapping [FILE0]));
X             break;
X           default:
X             fprintf (outputfile, "%d,%dc\n",
X                      D_LOWLINE (thisblock, mapping [FILE0]),
X                      D_HIGHLINE (thisblock, mapping [FILE0]));
X             break;
X           }
X         for (i = 0;
X              i < D_NUMLINES (thisblock, mapping [FILE2]);
X              i++)
X           {
X             if (D_RELNUM (thisblock, mapping [FILE2], i)[0] == '.')
X               { leading_dot = 1; fprintf (outputfile, "."); }
X             for (cp = D_RELNUM (thisblock, mapping [FILE2], i);
X                  cp < (D_RELNUM (thisblock, mapping [FILE2], i)
X                        + D_RELLEN (thisblock, mapping [FILE2], i));
X                  cp++)
X               putc (*cp, outputfile);
X             putc ('\n', outputfile);
X           }
X         fprintf (outputfile, ".\n");
X        
X         /* Add in code to take care of leading dots, if necessary. */
X         if (leading_dot)
X           {
X             fprintf (outputfile, "%d,%ds/^\\.\\./\\./\n",
X                      D_HIGHLINE (thisblock, mapping [FILE0]) + 1,
X                      (D_HIGHLINE (thisblock, mapping [FILE0])
X                       + D_NUMLINES (thisblock, mapping [FILE2])));
X             leading_dot = 0;
X           }
X       }
X    }
X  if (finalwrite) fprintf (outputfile, "w\nq\n");
X}
X
X/*
X * Reverse the order of the list of diff3 blocks.
X */
Xstruct diff3_block *
Xreverse_diff3_blocklist (diff)
X     struct diff3_block *diff;
X{
X  register struct diff3_block *tmp, *next, *prev;
X
X  for (tmp = diff, prev = (struct diff3_block *) 0;
X       tmp; tmp = next)
X    {
X      next = tmp->next;
X      tmp->next = prev;
X      prev = tmp;
X    }
X  
X  return prev;
X}
X
Xint
Xmyread (fd, ptr, size)
X     int fd, size;
X     char *ptr;
X{
X  int result = read (fd, ptr, size);
X  if (result < 0)
X    perror_with_exit ("Read failed");
X  return result;
X}
X
Xvoid *
Xxmalloc (size)
X     int size;
X{
X  void *result = (void *) calloc (1,size + 100);
X  if (!result)
X    fatal ("Malloc failed");
X  return result;
X}
X
Xvoid *
Xxrealloc (ptr, size)
X     void *ptr;
X     int size;
X{
X  void *result = (void *) realloc (ptr, size);
X  if (!result)
X    fatal ("Realloc failed\n");
X  return result;
X}
X
Xvoid fatal (string)
X     char *string;
X{
X  printf("%s: %s\n",argv0, string);
X  exit (1);
X}
Xvoid perror_with_exit (string)
X     char *string;
X{
X  perror (string);
X  exit (1);
X}
SHAR_EOF
echo "End of archive 2 (of 14)"
# if you want to concatenate archives, remove anything after this line
exit