diff options
author | peter <peter@FreeBSD.org> | 1998-01-26 03:09:57 +0000 |
---|---|---|
committer | peter <peter@FreeBSD.org> | 1998-01-26 03:09:57 +0000 |
commit | e6e45661e44f15cb8c5c6f063080509bd910b98d (patch) | |
tree | a9812ba7ade0fde6f62c1626b45d522ba104c314 /contrib/cvs/diff | |
parent | 571cfa0005d94d99d1341bf8ab02be04d4df5f9f (diff) | |
download | FreeBSD-src-e6e45661e44f15cb8c5c6f063080509bd910b98d.zip FreeBSD-src-e6e45661e44f15cb8c5c6f063080509bd910b98d.tar.gz |
Import cvs-1.9.23 as at 19980123. There are a number of really nice
things fixed in here, including the '-ko' vs. -A problem with
remote cvs which caused all files with -ko to be resent each time
(which is damn painful over a modem, I can tell you). It also found a
heap of stray empty directories that should have been pruned with the -P
flag to cvs update but were not for some reason.
It also has the fully integrated rcs and diff, so no more fork/exec
overheads for rcs,ci,patch,diff,etc. This means that it parses the control
data in the rcs files only once rather than twice or more.
If the 'cvs diff' vs. Index thing is going to be fixed for future patch
compatability, this is the place to do it.
Diffstat (limited to 'contrib/cvs/diff')
-rw-r--r-- | contrib/cvs/diff/ChangeLog | 202 | ||||
-rw-r--r-- | contrib/cvs/diff/Makefile.in | 104 | ||||
-rw-r--r-- | contrib/cvs/diff/analyze.c | 1087 | ||||
-rw-r--r-- | contrib/cvs/diff/cmpbuf.c | 40 | ||||
-rw-r--r-- | contrib/cvs/diff/cmpbuf.h | 20 | ||||
-rw-r--r-- | contrib/cvs/diff/context.c | 468 | ||||
-rw-r--r-- | contrib/cvs/diff/diagmeet.note | 71 | ||||
-rw-r--r-- | contrib/cvs/diff/diff.c | 1214 | ||||
-rw-r--r-- | contrib/cvs/diff/diff.h | 345 | ||||
-rw-r--r-- | contrib/cvs/diff/diff3.c | 1809 | ||||
-rw-r--r-- | contrib/cvs/diff/dir.c | 220 | ||||
-rw-r--r-- | contrib/cvs/diff/ed.c | 200 | ||||
-rw-r--r-- | contrib/cvs/diff/ifdef.c | 428 | ||||
-rw-r--r-- | contrib/cvs/diff/io.c | 714 | ||||
-rw-r--r-- | contrib/cvs/diff/normal.c | 71 | ||||
-rw-r--r-- | contrib/cvs/diff/side.c | 284 | ||||
-rw-r--r-- | contrib/cvs/diff/system.h | 270 | ||||
-rw-r--r-- | contrib/cvs/diff/util.c | 722 | ||||
-rw-r--r-- | contrib/cvs/diff/version.c | 5 |
19 files changed, 8274 insertions, 0 deletions
diff --git a/contrib/cvs/diff/ChangeLog b/contrib/cvs/diff/ChangeLog new file mode 100644 index 0000000..34aa707 --- /dev/null +++ b/contrib/cvs/diff/ChangeLog @@ -0,0 +1,202 @@ +Fri Jan 16 14:58:19 1998 Larry Jones <larry.jones@sdrc.com> + + * diff.c, diff3.c: Plug memory leaks. + +Thu Jan 15 13:36:46 1998 Jim Kingdon <kingdon@harvey.cyclic.com> + + * Makefile.in (installdirs): New rule, for when ../Makefile + recurses into this directory (bug reported by W. L. Estes). + +Tue Nov 11 10:48:19 1997 Jim Kingdon <kingdon@harvey.cyclic.com> + + * diff.c (diff_run): Change #ifdef on HAVE_SETMODE to #if to match + the other uses (fixes compilation error on unix). + + * diff.c (diff_run): Don't set stdout to binary mode. + +Mon, 10 Nov 1997 Jim Kingdon + + * diff.c (run_diff): Open outfile in binary mode if --binary. + +Thu Nov 6 12:42:12 1997 Karl Fogel <kfogel@floss.red-bean.com> + and Paul Eggert <eggert@twinsun.com> + + * analyze.c: applied Paul Eggert's patch to fix the diff3 merge + bug described in ccvs/doc/DIFFUTILS-2.7-BUG: + (shift_boundaries): new var `inhibit_hunk_merge'; use it to + control something important that I don't quite understand, but + Paul apparently does, so that's okay. + +Sat Nov 1 14:17:57 1997 Michael L.H. Brouwer <michael@thi.nl> + + * Makefile.in: Add call to ranlib to build a table of contents for + the library since some systems seem to require this. + +1997-10-28 Jim Kingdon + + * .cvsignore: Add files du jour for Visual C++, vc50.pdb and vc50.idb. + + * system.h: Define HAVE_TIME_H. + * dir.c [_WIN32]: Define CLOSEDIR_VOID. + +1997-10-18 Jim Kingdon + + * build_diff.com: Add diff3.c + +Fri Sep 26 14:24:42 1997 Tim Pierce <twp@twp.tezcat.com> + + * diff.c (diff_run): Save old value of optind before calling + getopt_long, then restore before returning. Eventually it would + be nice if diff_run were fully reentrant. + + New diff3 library for CVS. + * Makefile.in (SOURCES): Add diff3.c. + (OBJECTS): Add diff3.o. + * diff3.c: New file, copied from diffutils-2.7. See diffutils for + earlier ChangeLogs. Undefine initialize_main macro. Remove <signal.h>. + (diff3_run): Renamed from main(). Add `outfile' argument. Remove + SIGCLD handling; we do not fork. Save optind and reset to 0 + before calling getopt_long; restore after option processing done. + (read_diff): Use diff_run with a temporary output file, + instead of forking a diff subprocess and reading from a pipe. + Change DIFF_PROGRAM to "diff"; this argument is now used only for + diagnostic reporting. + (xmalloc, xrealloc): Removed. + (diff_program): Removed. + (diff_program_name): Made extern, so it may be used in other + library calls like `error'. + (initialize_main): New function. + + Namespace munging. util.c defines both fatal() and + perror_with_exit(), but these cannot be used to abort diff3: both + attempt to longjmp() to a buffer set in diff.c, used only by + diff_run. This is an awful solution, but necessary until the code + can be cleaned up. (These functions do not *have* to be renamed, + since both are declared static to diff3.c and should not clash + with libdiff.a, but it reduces potential confusion.) + * diff3.c (diff3_fatal): Renamed from fatal. + (diff3_perror_with_exit): Renamed from perror_with_exit. + + Eliminate exit calls. + (try_help): Change from `void' to `int'. Return, do not exit. + (diff3_fatal, diff3_perror_with_exit, process_diff): Change `exit' + to DIFF3_ABORT. + (diff3_run): Initialize jump buffer for nonlocal exits. Change + exit calls to returns. Change `perror_with_exit' to + `perror_with_name' and add a return. Change `fatal' to + `diff_error' and add a return. The reasoning is that we shouldn't + rely on setjmp/longjmp any more than necessary. + + Redirect stdout. + (check_output): Renamed from check_stdout. Take stream argument + instead of blindly checking stdout. Do not close stream, but + merely fflush it. + (diff3_run): Initialize outstream, and close when done. Pass this + stream (instead of stdout) to output_diff3_edscript, + output_diff3_merge, and output_diff3. + +Thu Sep 25 14:34:22 1997 Jim Kingdon <kingdon@harvey.cyclic.com> + + * util.c (begin_output, finish_output): If PR_PROGRAM is not + defined (VMS), just give a fatal error if --paginate specified. + + * Makefile.in (DISTFILES): Add ChangeLog build_diff.com + Makefile.in. + * build_diff.com: New file. + +Wed Sep 24 10:27:00 1997 Jim Kingdon <kingdon@harvey.cyclic.com> + + * Makefile.in: Also set top_srcdir. Needed to make today's other + Makefile.in change work. + + * .cvsignore: New file. + + * Makefile.in (COMPILE): Add -I options for srcdir (perhaps + unneeded) and change -I option for lib to use top_srcdir (needed + to avoid mixups with CVS's regex.h vs. the system one). + +Sun Sep 21 19:44:42 1997 Jim Kingdon <kingdon@harvey.cyclic.com> + + * Makefile.in (util.o): Change util.c to $<, needed for srcdir. + +Sat Sep 20 12:06:41 1997 Tim Pierce <twp@twp.tezcat.com> + + New diff library for CVS, based on diffutils-2.7. See diffutils + for earlier ChangeLogs. + * Makefile.in, analyze.c, cmpbuf.c, cmpbuf.h, config.hin, + context.c, diagmeet.note, diff.c, diff.h, dir.c, ed.c, ifdef.c, + io.c, normal.c, side.c, stamp-h.in, system.h, util.c, version.c: + New files. + (COMPILE): Add -I../lib, so we can get getopt.h. + + * Makefile.in: Removed anything not related to libdiff.a. + (dist-dir): New target, copied from ../lib/Makefile.in. + (DISTFILES): New variable. + (SOURCES): Renamed from `srcs'. + (OBJECTS): Renamed from `libdiff_o'. + (Makefile): Changed dependencies to reflect + new, shallow config directory structure. + (stamp-h.in, config.h.in, config.h, stamp-h): Removed. + * stamp-h.in, config.h.in: Removed. + + * system.h: Remove dup2 macro (provided by ../lib/dup2.c). + Include stdlib.h if STDC_HEADERS is defined (not just + HAVE_STDLIB_H). + +Sat Sep 20 05:32:18 1997 Tim Pierce <twp@twp.tezcat.com> + + Diff librarification. + + * diff.c (diff_run): New function, renamed from `main'. + Initialize `outfile' based on the value of the new `out' filename + argument. + (initialize_main): New function. + * system.h: Removed initialize_main macro. + * diffmain.c: New file. + * Makefile.in (diff): Added diffmain.o. + (libdiff): New target. + (AR, libdiff_o): New variables. libdiff_o does not include + xmalloc.o, fnmatch.o, getopt.o, getopt1.o, regex.o or error.o, + because these functions are already present in CVS. It will take + some work to make this more general-purpose. + + Redirect standard output. + * util.c: Redirect stdout to outfile: change all naked `printf' + and `putchar' statements to `fprintf (outfile)' and `putc (..., + outfile)' throughout. This should permit redirecting diff output + by changing `outfile' just once in `diff_run'. + (output_in_progress): New variable. + (begin_output, finish_output): Use `output_in_progress', rather than + `outfile', as a semaphore to avoid reentrancy problems. + (finish_output): Close `outfile' only if paginate_flag is set. + * diff.c (check_output): New function, was check_stdout. Take a + `file' argument, and flush it instead of closing it. + (diff_run): Change check_stdout to check_output. + (compare_files): Fflush outfile, not stdout. + + Eliminate exit statements. + * diff.h: Include setjmp.h. + (diff_abort_buf): New variable. + (DIFF_ABORT): New macro. + * diff.c (diff_run): Change all `exit' statements to `return'. + Set up diff_abort_buf, so we can abort diff without + terminating (for libdiff.a). + (try_help): Return int instead of void; do not exit. + * util.c (fatal): Use DIFF_ABORT instead of exit. + (pfatal_with_name): Use DIFF_ABORT instead of exit. + + Namespace cleanup (rudimentary). Strictly speaking, this is not + necessary to make diff into a library. However, namespace + clashes between diff and CVS must be resolved immediately, since + CVS is the first application targeted for use with difflib. + + * analyze.c, diff.c, diff.h, util.c (diff_error): Renamed from `error'. + + * version.c, diff.c, diff.h, cmp.c, diff3.c, sdiff.c + (diff_version_string): Renamed from version_string. + * diff.c, util.c, diff.h, diff3.c, error.c (diff_program_name): + Renamed from program_name. + + * util.c (xmalloc, xrealloc): Removed. + * Makefile.in (diff_o): Added error.o and xmalloc.o. + diff --git a/contrib/cvs/diff/Makefile.in b/contrib/cvs/diff/Makefile.in new file mode 100644 index 0000000..333d4d9 --- /dev/null +++ b/contrib/cvs/diff/Makefile.in @@ -0,0 +1,104 @@ +# Makefile for GNU DIFF +# Copyright (C) 1988,1989,1991,1992,1993,1994,1997 Free Software Foundation, Inc. +# +# This file is part of GNU DIFF. +# +# GNU DIFF is free software; you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation; either version 2, or (at your option) +# any later version. +# +# GNU DIFF is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. +# +# You should have received a copy of the GNU General Public License +# along with GNU DIFF; see the file COPYING. If not, write to +# the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. + +#### Start of system configuration section. #### + +srcdir = @srcdir@ +top_srcdir = @top_srcdir@ +VPATH = @srcdir@ +subdir = diff + +CC = @CC@ +AR = ar + +CPPFLAGS = @CPPFLAGS@ +DEFS = @DEFS@ +RANLIB = @RANLIB@ +CFLAGS = @CFLAGS@ + +prefix = @prefix@ +exec_prefix = @exec_prefix@ + +PR_PROGRAM = /bin/pr + +#### End of system configuration section. #### + +SHELL = /bin/sh + +# The source files for all of the programs. +SOURCES = diff.c diff3.c analyze.c cmpbuf.c cmpbuf.h io.c context.c ed.c \ + normal.c ifdef.c util.c dir.c version.c diff.h side.c system.h +OBJECTS = diff.o diff3.o analyze.o cmpbuf.o dir.o io.o util.o \ + context.o ed.o ifdef.o normal.o side.o version.o +DISTFILES = $(SOURCES) ChangeLog build_diff.com Makefile.in + +all: libdiff.a + +# $(top_srcdir)/lib is so we don't get the system-supplied headers for +# functions that we supply ourselves in lib. $(srcdir) is perhaps not +# necessary if we assume the unix compiler behavior whereby "" looks +# in the directory containing the .c file first. +# -I. is probably unnecessary (I don't think we generate any .h files). +# -I.. is for config.h. +COMPILE = $(CC) -c $(CPPFLAGS) $(DEFS) \ + -I. -I.. -I$(srcdir) -I$(top_srcdir)/lib $(CFLAGS) + +.c.o: + $(COMPILE) $< + +libdiff libdiff.a: $(OBJECTS) + $(AR) cr libdiff.a $(OBJECTS) + -$(RANLIB) libdiff.a + +$(OBJECTS): diff.h system.h +analyze.o cmpbuf.o: cmpbuf.h + +util.o: util.c + $(COMPILE) -DPR_PROGRAM=\"$(PR_PROGRAM)\" $< + +install: all + +installdirs: + @: nothing to do for installdirs +.PHONY: installdirs + +TAGS: $(SOURCES) + etags $(SOURCES) + +clean: + rm -f *.o *.a core + +mostlyclean: clean + +distclean: clean + rm -f TAGS tags Makefile + +realclean: distclean + +Makefile: Makefile.in ../config.status + cd .. && CONFIG_FILES=$(subdir)/$@ CONFIG_HEADERS= ./config.status + +dist-dir: + mkdir ${DISTDIR} + for i in ${DISTFILES}; do \ + ln $(srcdir)/$${i} ${DISTDIR}; \ + done + +# Prevent GNU make v3 from overflowing arg limit on SysV. +.NOEXPORT: diff --git a/contrib/cvs/diff/analyze.c b/contrib/cvs/diff/analyze.c new file mode 100644 index 0000000..0bda3cf --- /dev/null +++ b/contrib/cvs/diff/analyze.c @@ -0,0 +1,1087 @@ +/* Analyze file differences for GNU DIFF. + Copyright (C) 1988, 1989, 1992, 1993, 1997 Free Software Foundation, Inc. + +This file is part of GNU DIFF. + +GNU DIFF is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +GNU DIFF is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU DIFF; see the file COPYING. If not, write to +the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ + +/* The basic algorithm is described in: + "An O(ND) Difference Algorithm and its Variations", Eugene Myers, + Algorithmica Vol. 1 No. 2, 1986, pp. 251-266; + see especially section 4.2, which describes the variation used below. + Unless the --minimal option is specified, this code uses the TOO_EXPENSIVE + heuristic, by Paul Eggert, to limit the cost to O(N**1.5 log N) + at the price of producing suboptimal output for large inputs with + many differences. + + The basic algorithm was independently discovered as described in: + "Algorithms for Approximate String Matching", E. Ukkonen, + Information and Control Vol. 64, 1985, pp. 100-118. */ + +#include "diff.h" +#include "cmpbuf.h" + +extern int no_discards; + +static int *xvec, *yvec; /* Vectors being compared. */ +static int *fdiag; /* Vector, indexed by diagonal, containing + 1 + the X coordinate of the point furthest + along the given diagonal in the forward + search of the edit matrix. */ +static int *bdiag; /* Vector, indexed by diagonal, containing + the X coordinate of the point furthest + along the given diagonal in the backward + search of the edit matrix. */ +static int too_expensive; /* Edit scripts longer than this are too + expensive to compute. */ + +#define SNAKE_LIMIT 20 /* Snakes bigger than this are considered `big'. */ + +struct partition +{ + int xmid, ymid; /* Midpoints of this partition. */ + int lo_minimal; /* Nonzero if low half will be analyzed minimally. */ + int hi_minimal; /* Likewise for high half. */ +}; + +static int diag PARAMS((int, int, int, int, int, struct partition *)); +static struct change *add_change PARAMS((int, int, int, int, struct change *)); +static struct change *build_reverse_script PARAMS((struct file_data const[])); +static struct change *build_script PARAMS((struct file_data const[])); +static void briefly_report PARAMS((int, struct file_data const[])); +static void compareseq PARAMS((int, int, int, int, int)); +static void discard_confusing_lines PARAMS((struct file_data[])); +static void shift_boundaries PARAMS((struct file_data[])); + +/* Find the midpoint of the shortest edit script for a specified + portion of the two files. + + Scan from the beginnings of the files, and simultaneously from the ends, + doing a breadth-first search through the space of edit-sequence. + When the two searches meet, we have found the midpoint of the shortest + edit sequence. + + If MINIMAL is nonzero, find the minimal edit script regardless + of expense. Otherwise, if the search is too expensive, use + heuristics to stop the search and report a suboptimal answer. + + Set PART->(XMID,YMID) to the midpoint (XMID,YMID). The diagonal number + XMID - YMID equals the number of inserted lines minus the number + of deleted lines (counting only lines before the midpoint). + Return the approximate edit cost; this is the total number of + lines inserted or deleted (counting only lines before the midpoint), + unless a heuristic is used to terminate the search prematurely. + + Set PART->LEFT_MINIMAL to nonzero iff the minimal edit script for the + left half of the partition is known; similarly for PART->RIGHT_MINIMAL. + + This function assumes that the first lines of the specified portions + of the two files do not match, and likewise that the last lines do not + match. The caller must trim matching lines from the beginning and end + of the portions it is going to specify. + + If we return the "wrong" partitions, + the worst this can do is cause suboptimal diff output. + It cannot cause incorrect diff output. */ + +static int +diag (xoff, xlim, yoff, ylim, minimal, part) + int xoff, xlim, yoff, ylim, minimal; + struct partition *part; +{ + int *const fd = fdiag; /* Give the compiler a chance. */ + int *const bd = bdiag; /* Additional help for the compiler. */ + int const *const xv = xvec; /* Still more help for the compiler. */ + int const *const yv = yvec; /* And more and more . . . */ + int const dmin = xoff - ylim; /* Minimum valid diagonal. */ + int const dmax = xlim - yoff; /* Maximum valid diagonal. */ + int const fmid = xoff - yoff; /* Center diagonal of top-down search. */ + int const bmid = xlim - ylim; /* Center diagonal of bottom-up search. */ + int fmin = fmid, fmax = fmid; /* Limits of top-down search. */ + int bmin = bmid, bmax = bmid; /* Limits of bottom-up search. */ + int c; /* Cost. */ + int odd = (fmid - bmid) & 1; /* True if southeast corner is on an odd + diagonal with respect to the northwest. */ + + fd[fmid] = xoff; + bd[bmid] = xlim; + + for (c = 1;; ++c) + { + int d; /* Active diagonal. */ + int big_snake = 0; + + /* Extend the top-down search by an edit step in each diagonal. */ + fmin > dmin ? fd[--fmin - 1] = -1 : ++fmin; + fmax < dmax ? fd[++fmax + 1] = -1 : --fmax; + for (d = fmax; d >= fmin; d -= 2) + { + int x, y, oldx, tlo = fd[d - 1], thi = fd[d + 1]; + + if (tlo >= thi) + x = tlo + 1; + else + x = thi; + oldx = x; + y = x - d; + while (x < xlim && y < ylim && xv[x] == yv[y]) + ++x, ++y; + if (x - oldx > SNAKE_LIMIT) + big_snake = 1; + fd[d] = x; + if (odd && bmin <= d && d <= bmax && bd[d] <= x) + { + part->xmid = x; + part->ymid = y; + part->lo_minimal = part->hi_minimal = 1; + return 2 * c - 1; + } + } + + /* Similarly extend the bottom-up search. */ + bmin > dmin ? bd[--bmin - 1] = INT_MAX : ++bmin; + bmax < dmax ? bd[++bmax + 1] = INT_MAX : --bmax; + for (d = bmax; d >= bmin; d -= 2) + { + int x, y, oldx, tlo = bd[d - 1], thi = bd[d + 1]; + + if (tlo < thi) + x = tlo; + else + x = thi - 1; + oldx = x; + y = x - d; + while (x > xoff && y > yoff && xv[x - 1] == yv[y - 1]) + --x, --y; + if (oldx - x > SNAKE_LIMIT) + big_snake = 1; + bd[d] = x; + if (!odd && fmin <= d && d <= fmax && x <= fd[d]) + { + part->xmid = x; + part->ymid = y; + part->lo_minimal = part->hi_minimal = 1; + return 2 * c; + } + } + + if (minimal) + continue; + + /* Heuristic: check occasionally for a diagonal that has made + lots of progress compared with the edit distance. + If we have any such, find the one that has made the most + progress and return it as if it had succeeded. + + With this heuristic, for files with a constant small density + of changes, the algorithm is linear in the file size. */ + + if (c > 200 && big_snake && heuristic) + { + int best; + + best = 0; + for (d = fmax; d >= fmin; d -= 2) + { + int dd = d - fmid; + int x = fd[d]; + int y = x - d; + int v = (x - xoff) * 2 - dd; + if (v > 12 * (c + (dd < 0 ? -dd : dd))) + { + if (v > best + && xoff + SNAKE_LIMIT <= x && x < xlim + && yoff + SNAKE_LIMIT <= y && y < ylim) + { + /* We have a good enough best diagonal; + now insist that it end with a significant snake. */ + int k; + + for (k = 1; xv[x - k] == yv[y - k]; k++) + if (k == SNAKE_LIMIT) + { + best = v; + part->xmid = x; + part->ymid = y; + break; + } + } + } + } + if (best > 0) + { + part->lo_minimal = 1; + part->hi_minimal = 0; + return 2 * c - 1; + } + + best = 0; + for (d = bmax; d >= bmin; d -= 2) + { + int dd = d - bmid; + int x = bd[d]; + int y = x - d; + int v = (xlim - x) * 2 + dd; + if (v > 12 * (c + (dd < 0 ? -dd : dd))) + { + if (v > best + && xoff < x && x <= xlim - SNAKE_LIMIT + && yoff < y && y <= ylim - SNAKE_LIMIT) + { + /* We have a good enough best diagonal; + now insist that it end with a significant snake. */ + int k; + + for (k = 0; xv[x + k] == yv[y + k]; k++) + if (k == SNAKE_LIMIT - 1) + { + best = v; + part->xmid = x; + part->ymid = y; + break; + } + } + } + } + if (best > 0) + { + part->lo_minimal = 0; + part->hi_minimal = 1; + return 2 * c - 1; + } + } + + /* Heuristic: if we've gone well beyond the call of duty, + give up and report halfway between our best results so far. */ + if (c >= too_expensive) + { + int fxybest, fxbest; + int bxybest, bxbest; + + fxbest = bxbest = 0; /* Pacify `gcc -Wall'. */ + + /* Find forward diagonal that maximizes X + Y. */ + fxybest = -1; + for (d = fmax; d >= fmin; d -= 2) + { + int x = min (fd[d], xlim); + int y = x - d; + if (ylim < y) + x = ylim + d, y = ylim; + if (fxybest < x + y) + { + fxybest = x + y; + fxbest = x; + } + } + + /* Find backward diagonal that minimizes X + Y. */ + bxybest = INT_MAX; + for (d = bmax; d >= bmin; d -= 2) + { + int x = max (xoff, bd[d]); + int y = x - d; + if (y < yoff) + x = yoff + d, y = yoff; + if (x + y < bxybest) + { + bxybest = x + y; + bxbest = x; + } + } + + /* Use the better of the two diagonals. */ + if ((xlim + ylim) - bxybest < fxybest - (xoff + yoff)) + { + part->xmid = fxbest; + part->ymid = fxybest - fxbest; + part->lo_minimal = 1; + part->hi_minimal = 0; + } + else + { + part->xmid = bxbest; + part->ymid = bxybest - bxbest; + part->lo_minimal = 0; + part->hi_minimal = 1; + } + return 2 * c - 1; + } + } +} + +/* Compare in detail contiguous subsequences of the two files + which are known, as a whole, to match each other. + + The results are recorded in the vectors files[N].changed_flag, by + storing a 1 in the element for each line that is an insertion or deletion. + + The subsequence of file 0 is [XOFF, XLIM) and likewise for file 1. + + Note that XLIM, YLIM are exclusive bounds. + All line numbers are origin-0 and discarded lines are not counted. + + If MINIMAL is nonzero, find a minimal difference no matter how + expensive it is. */ + +static void +compareseq (xoff, xlim, yoff, ylim, minimal) + int xoff, xlim, yoff, ylim, minimal; +{ + int * const xv = xvec; /* Help the compiler. */ + int * const yv = yvec; + + /* Slide down the bottom initial diagonal. */ + while (xoff < xlim && yoff < ylim && xv[xoff] == yv[yoff]) + ++xoff, ++yoff; + /* Slide up the top initial diagonal. */ + while (xlim > xoff && ylim > yoff && xv[xlim - 1] == yv[ylim - 1]) + --xlim, --ylim; + + /* Handle simple cases. */ + if (xoff == xlim) + while (yoff < ylim) + files[1].changed_flag[files[1].realindexes[yoff++]] = 1; + else if (yoff == ylim) + while (xoff < xlim) + files[0].changed_flag[files[0].realindexes[xoff++]] = 1; + else + { + int c; + struct partition part; + + /* Find a point of correspondence in the middle of the files. */ + + c = diag (xoff, xlim, yoff, ylim, minimal, &part); + + if (c == 1) + { + /* This should be impossible, because it implies that + one of the two subsequences is empty, + and that case was handled above without calling `diag'. + Let's verify that this is true. */ + abort (); +#if 0 + /* The two subsequences differ by a single insert or delete; + record it and we are done. */ + if (part.xmid - part.ymid < xoff - yoff) + files[1].changed_flag[files[1].realindexes[part.ymid - 1]] = 1; + else + files[0].changed_flag[files[0].realindexes[part.xmid]] = 1; +#endif + } + else + { + /* Use the partitions to split this problem into subproblems. */ + compareseq (xoff, part.xmid, yoff, part.ymid, part.lo_minimal); + compareseq (part.xmid, xlim, part.ymid, ylim, part.hi_minimal); + } + } +} + +/* Discard lines from one file that have no matches in the other file. + + A line which is discarded will not be considered by the actual + comparison algorithm; it will be as if that line were not in the file. + The file's `realindexes' table maps virtual line numbers + (which don't count the discarded lines) into real line numbers; + this is how the actual comparison algorithm produces results + that are comprehensible when the discarded lines are counted. + + When we discard a line, we also mark it as a deletion or insertion + so that it will be printed in the output. */ + +static void +discard_confusing_lines (filevec) + struct file_data filevec[]; +{ + unsigned int f, i; + char *discarded[2]; + int *equiv_count[2]; + int *p; + + /* Allocate our results. */ + p = (int *) xmalloc ((filevec[0].buffered_lines + filevec[1].buffered_lines) + * (2 * sizeof (int))); + for (f = 0; f < 2; f++) + { + filevec[f].undiscarded = p; p += filevec[f].buffered_lines; + filevec[f].realindexes = p; p += filevec[f].buffered_lines; + } + + /* Set up equiv_count[F][I] as the number of lines in file F + that fall in equivalence class I. */ + + p = (int *) xmalloc (filevec[0].equiv_max * (2 * sizeof (int))); + equiv_count[0] = p; + equiv_count[1] = p + filevec[0].equiv_max; + bzero (p, filevec[0].equiv_max * (2 * sizeof (int))); + + for (i = 0; i < filevec[0].buffered_lines; ++i) + ++equiv_count[0][filevec[0].equivs[i]]; + for (i = 0; i < filevec[1].buffered_lines; ++i) + ++equiv_count[1][filevec[1].equivs[i]]; + + /* Set up tables of which lines are going to be discarded. */ + + discarded[0] = xmalloc (sizeof (char) + * (filevec[0].buffered_lines + + filevec[1].buffered_lines)); + discarded[1] = discarded[0] + filevec[0].buffered_lines; + bzero (discarded[0], sizeof (char) * (filevec[0].buffered_lines + + filevec[1].buffered_lines)); + + /* Mark to be discarded each line that matches no line of the other file. + If a line matches many lines, mark it as provisionally discardable. */ + + for (f = 0; f < 2; f++) + { + unsigned int end = filevec[f].buffered_lines; + char *discards = discarded[f]; + int *counts = equiv_count[1 - f]; + int *equivs = filevec[f].equivs; + unsigned int many = 5; + unsigned int tem = end / 64; + + /* Multiply MANY by approximate square root of number of lines. + That is the threshold for provisionally discardable lines. */ + while ((tem = tem >> 2) > 0) + many *= 2; + + for (i = 0; i < end; i++) + { + int nmatch; + if (equivs[i] == 0) + continue; + nmatch = counts[equivs[i]]; + if (nmatch == 0) + discards[i] = 1; + else if (nmatch > many) + discards[i] = 2; + } + } + + /* Don't really discard the provisional lines except when they occur + in a run of discardables, with nonprovisionals at the beginning + and end. */ + + for (f = 0; f < 2; f++) + { + unsigned int end = filevec[f].buffered_lines; + register char *discards = discarded[f]; + + for (i = 0; i < end; i++) + { + /* Cancel provisional discards not in middle of run of discards. */ + if (discards[i] == 2) + discards[i] = 0; + else if (discards[i] != 0) + { + /* We have found a nonprovisional discard. */ + register int j; + unsigned int length; + unsigned int provisional = 0; + + /* Find end of this run of discardable lines. + Count how many are provisionally discardable. */ + for (j = i; j < end; j++) + { + if (discards[j] == 0) + break; + if (discards[j] == 2) + ++provisional; + } + + /* Cancel provisional discards at end, and shrink the run. */ + while (j > i && discards[j - 1] == 2) + discards[--j] = 0, --provisional; + + /* Now we have the length of a run of discardable lines + whose first and last are not provisional. */ + length = j - i; + + /* If 1/4 of the lines in the run are provisional, + cancel discarding of all provisional lines in the run. */ + if (provisional * 4 > length) + { + while (j > i) + if (discards[--j] == 2) + discards[j] = 0; + } + else + { + register unsigned int consec; + unsigned int minimum = 1; + unsigned int tem = length / 4; + + /* MINIMUM is approximate square root of LENGTH/4. + A subrun of two or more provisionals can stand + when LENGTH is at least 16. + A subrun of 4 or more can stand when LENGTH >= 64. */ + while ((tem = tem >> 2) > 0) + minimum *= 2; + minimum++; + + /* Cancel any subrun of MINIMUM or more provisionals + within the larger run. */ + for (j = 0, consec = 0; j < length; j++) + if (discards[i + j] != 2) + consec = 0; + else if (minimum == ++consec) + /* Back up to start of subrun, to cancel it all. */ + j -= consec; + else if (minimum < consec) + discards[i + j] = 0; + + /* Scan from beginning of run + until we find 3 or more nonprovisionals in a row + or until the first nonprovisional at least 8 lines in. + Until that point, cancel any provisionals. */ + for (j = 0, consec = 0; j < length; j++) + { + if (j >= 8 && discards[i + j] == 1) + break; + if (discards[i + j] == 2) + consec = 0, discards[i + j] = 0; + else if (discards[i + j] == 0) + consec = 0; + else + consec++; + if (consec == 3) + break; + } + + /* I advances to the last line of the run. */ + i += length - 1; + + /* Same thing, from end. */ + for (j = 0, consec = 0; j < length; j++) + { + if (j >= 8 && discards[i - j] == 1) + break; + if (discards[i - j] == 2) + consec = 0, discards[i - j] = 0; + else if (discards[i - j] == 0) + consec = 0; + else + consec++; + if (consec == 3) + break; + } + } + } + } + } + + /* Actually discard the lines. */ + for (f = 0; f < 2; f++) + { + char *discards = discarded[f]; + unsigned int end = filevec[f].buffered_lines; + unsigned int j = 0; + for (i = 0; i < end; ++i) + if (no_discards || discards[i] == 0) + { + filevec[f].undiscarded[j] = filevec[f].equivs[i]; + filevec[f].realindexes[j++] = i; + } + else + filevec[f].changed_flag[i] = 1; + filevec[f].nondiscarded_lines = j; + } + + free (discarded[0]); + free (equiv_count[0]); +} + +/* Adjust inserts/deletes of identical lines to join changes + as much as possible. + + We do something when a run of changed lines include a + line at one end and have an excluded, identical line at the other. + We are free to choose which identical line is included. + `compareseq' usually chooses the one at the beginning, + but usually it is cleaner to consider the following identical line + to be the "change". */ + +int inhibit; + +static void +shift_boundaries (filevec) + struct file_data filevec[]; +{ + int f; + int inhibit_hunk_merge = horizon_lines != context; + + for (f = 0; f < 2; f++) + { + char *changed = filevec[f].changed_flag; + char const *other_changed = filevec[1-f].changed_flag; + int const *equivs = filevec[f].equivs; + int i = 0; + int j = 0; + int i_end = filevec[f].buffered_lines; + + while (1) + { + int runlength, start, corresponding; + + /* Scan forwards to find beginning of another run of changes. + Also keep track of the corresponding point in the other file. */ + + while (i < i_end && changed[i] == 0) + { + while (other_changed[j++]) + continue; + i++; + } + + if (i == i_end) + break; + + start = i; + + /* Find the end of this run of changes. */ + + while (changed[++i]) + continue; + while (other_changed[j]) + j++; + + do + { + /* Record the length of this run of changes, so that + we can later determine whether the run has grown. */ + runlength = i - start; + + if (! inhibit_hunk_merge) + { + /* Move the changed region back, so long as the + previous unchanged line matches the last changed one. + This merges with previous changed regions. */ + + while (start && equivs[start - 1] == equivs[i - 1]) + { + changed[--start] = 1; + changed[--i] = 0; + while (changed[start - 1]) + start--; + while (other_changed[--j]) + continue; + } + } + + /* Set CORRESPONDING to the end of the changed run, at the last + point where it corresponds to a changed run in the other file. + CORRESPONDING == I_END means no such point has been found. */ + corresponding = other_changed[j - 1] ? i : i_end; + + /* Shift the changed region forward, so long as the + first changed line matches the following unchanged one, + but if INHIBIT_HUNK_MERGE is 1 do not shift if + this would merge with another changed region. + Do this second, so that if there are no merges, + the changed region is moved forward as far as possible. */ + + while (i != i_end && equivs[start] == equivs[i] + && ! (inhibit_hunk_merge & other_changed[j + 1])) + { + changed[start++] = 0; + changed[i++] = 1; + while (changed[i]) + i++; + while (other_changed[++j]) + corresponding = i; + } + } + while (runlength != i - start); + + /* If possible, move the fully-merged run of changes + back to a corresponding run in the other file. */ + + while (corresponding < i) + { + changed[--start] = 1; + changed[--i] = 0; + while (other_changed[--j]) + continue; + } + } + } +} + +/* Cons an additional entry onto the front of an edit script OLD. + LINE0 and LINE1 are the first affected lines in the two files (origin 0). + DELETED is the number of lines deleted here from file 0. + INSERTED is the number of lines inserted here in file 1. + + If DELETED is 0 then LINE0 is the number of the line before + which the insertion was done; vice versa for INSERTED and LINE1. */ + +static struct change * +add_change (line0, line1, deleted, inserted, old) + int line0, line1, deleted, inserted; + struct change *old; +{ + struct change *new = (struct change *) xmalloc (sizeof (struct change)); + + new->line0 = line0; + new->line1 = line1; + new->inserted = inserted; + new->deleted = deleted; + new->link = old; + return new; +} + +/* Scan the tables of which lines are inserted and deleted, + producing an edit script in reverse order. */ + +static struct change * +build_reverse_script (filevec) + struct file_data const filevec[]; +{ + struct change *script = 0; + char *changed0 = filevec[0].changed_flag; + char *changed1 = filevec[1].changed_flag; + int len0 = filevec[0].buffered_lines; + int len1 = filevec[1].buffered_lines; + + /* Note that changedN[len0] does exist, and contains 0. */ + + int i0 = 0, i1 = 0; + + while (i0 < len0 || i1 < len1) + { + if (changed0[i0] || changed1[i1]) + { + int line0 = i0, line1 = i1; + + /* Find # lines changed here in each file. */ + while (changed0[i0]) ++i0; + while (changed1[i1]) ++i1; + + /* Record this change. */ + script = add_change (line0, line1, i0 - line0, i1 - line1, script); + } + + /* We have reached lines in the two files that match each other. */ + i0++, i1++; + } + + return script; +} + +/* Scan the tables of which lines are inserted and deleted, + producing an edit script in forward order. */ + +static struct change * +build_script (filevec) + struct file_data const filevec[]; +{ + struct change *script = 0; + char *changed0 = filevec[0].changed_flag; + char *changed1 = filevec[1].changed_flag; + int i0 = filevec[0].buffered_lines, i1 = filevec[1].buffered_lines; + + /* Note that changedN[-1] does exist, and contains 0. */ + + while (i0 >= 0 || i1 >= 0) + { + if (changed0[i0 - 1] || changed1[i1 - 1]) + { + int line0 = i0, line1 = i1; + + /* Find # lines changed here in each file. */ + while (changed0[i0 - 1]) --i0; + while (changed1[i1 - 1]) --i1; + + /* Record this change. */ + script = add_change (i0, i1, line0 - i0, line1 - i1, script); + } + + /* We have reached lines in the two files that match each other. */ + i0--, i1--; + } + + return script; +} + +/* If CHANGES, briefly report that two files differed. */ +static void +briefly_report (changes, filevec) + int changes; + struct file_data const filevec[]; +{ + if (changes) + message (no_details_flag ? "Files %s and %s differ\n" + : "Binary files %s and %s differ\n", + filevec[0].name, filevec[1].name); +} + +/* Report the differences of two files. DEPTH is the current directory + depth. */ +int +diff_2_files (filevec, depth) + struct file_data filevec[]; + int depth; +{ + int diags; + int i; + struct change *e, *p; + struct change *script; + int changes; + + + /* If we have detected that either file is binary, + compare the two files as binary. This can happen + only when the first chunk is read. + Also, --brief without any --ignore-* options means + we can speed things up by treating the files as binary. */ + + if (read_files (filevec, no_details_flag & ~ignore_some_changes)) + { + /* Files with different lengths must be different. */ + if (filevec[0].stat.st_size != filevec[1].stat.st_size + && (filevec[0].desc < 0 || S_ISREG (filevec[0].stat.st_mode)) + && (filevec[1].desc < 0 || S_ISREG (filevec[1].stat.st_mode))) + changes = 1; + + /* Standard input equals itself. */ + else if (filevec[0].desc == filevec[1].desc) + changes = 0; + + else + /* Scan both files, a buffer at a time, looking for a difference. */ + { + /* Allocate same-sized buffers for both files. */ + size_t buffer_size = buffer_lcm (STAT_BLOCKSIZE (filevec[0].stat), + STAT_BLOCKSIZE (filevec[1].stat)); + for (i = 0; i < 2; i++) + filevec[i].buffer = xrealloc (filevec[i].buffer, buffer_size); + + for (;; filevec[0].buffered_chars = filevec[1].buffered_chars = 0) + { + /* Read a buffer's worth from both files. */ + for (i = 0; i < 2; i++) + if (0 <= filevec[i].desc) + while (filevec[i].buffered_chars != buffer_size) + { + int r = read (filevec[i].desc, + filevec[i].buffer + + filevec[i].buffered_chars, + buffer_size - filevec[i].buffered_chars); + if (r == 0) + break; + if (r < 0) + pfatal_with_name (filevec[i].name); + filevec[i].buffered_chars += r; + } + + /* If the buffers differ, the files differ. */ + if (filevec[0].buffered_chars != filevec[1].buffered_chars + || (filevec[0].buffered_chars != 0 + && memcmp (filevec[0].buffer, + filevec[1].buffer, + filevec[0].buffered_chars) != 0)) + { + changes = 1; + break; + } + + /* If we reach end of file, the files are the same. */ + if (filevec[0].buffered_chars != buffer_size) + { + changes = 0; + break; + } + } + } + + briefly_report (changes, filevec); + } + else + { + /* Allocate vectors for the results of comparison: + a flag for each line of each file, saying whether that line + is an insertion or deletion. + Allocate an extra element, always zero, at each end of each vector. */ + + size_t s = filevec[0].buffered_lines + filevec[1].buffered_lines + 4; + filevec[0].changed_flag = xmalloc (s); + bzero (filevec[0].changed_flag, s); + filevec[0].changed_flag++; + filevec[1].changed_flag = filevec[0].changed_flag + + filevec[0].buffered_lines + 2; + + /* Some lines are obviously insertions or deletions + because they don't match anything. Detect them now, and + avoid even thinking about them in the main comparison algorithm. */ + + discard_confusing_lines (filevec); + + /* Now do the main comparison algorithm, considering just the + undiscarded lines. */ + + xvec = filevec[0].undiscarded; + yvec = filevec[1].undiscarded; + diags = filevec[0].nondiscarded_lines + filevec[1].nondiscarded_lines + 3; + fdiag = (int *) xmalloc (diags * (2 * sizeof (int))); + bdiag = fdiag + diags; + fdiag += filevec[1].nondiscarded_lines + 1; + bdiag += filevec[1].nondiscarded_lines + 1; + + /* Set TOO_EXPENSIVE to be approximate square root of input size, + bounded below by 256. */ + too_expensive = 1; + for (i = filevec[0].nondiscarded_lines + filevec[1].nondiscarded_lines; + i != 0; i >>= 2) + too_expensive <<= 1; + too_expensive = max (256, too_expensive); + + files[0] = filevec[0]; + files[1] = filevec[1]; + + compareseq (0, filevec[0].nondiscarded_lines, + 0, filevec[1].nondiscarded_lines, no_discards); + + free (fdiag - (filevec[1].nondiscarded_lines + 1)); + + /* Modify the results slightly to make them prettier + in cases where that can validly be done. */ + + shift_boundaries (filevec); + + /* Get the results of comparison in the form of a chain + of `struct change's -- an edit script. */ + + if (output_style == OUTPUT_ED) + script = build_reverse_script (filevec); + else + script = build_script (filevec); + + /* Set CHANGES if we had any diffs. + If some changes are ignored, we must scan the script to decide. */ + if (ignore_blank_lines_flag || ignore_regexp_list) + { + struct change *next = script; + changes = 0; + + while (next && changes == 0) + { + struct change *this, *end; + int first0, last0, first1, last1, deletes, inserts; + + /* Find a set of changes that belong together. */ + this = next; + end = find_change (next); + + /* Disconnect them from the rest of the changes, making them + a hunk, and remember the rest for next iteration. */ + next = end->link; + end->link = 0; + + /* Determine whether this hunk is really a difference. */ + analyze_hunk (this, &first0, &last0, &first1, &last1, + &deletes, &inserts); + + /* Reconnect the script so it will all be freed properly. */ + end->link = next; + + if (deletes || inserts) + changes = 1; + } + } + else + changes = (script != 0); + + if (no_details_flag) + briefly_report (changes, filevec); + else + { + if (changes || ! no_diff_means_no_output) + { + /* Record info for starting up output, + to be used if and when we have some output to print. */ + setup_output (files[0].name, files[1].name, depth); + + switch (output_style) + { + case OUTPUT_CONTEXT: + print_context_script (script, 0); + break; + + case OUTPUT_UNIFIED: + print_context_script (script, 1); + break; + + case OUTPUT_ED: + print_ed_script (script); + break; + + case OUTPUT_FORWARD_ED: + pr_forward_ed_script (script); + break; + + case OUTPUT_RCS: + print_rcs_script (script); + break; + + case OUTPUT_NORMAL: + print_normal_script (script); + break; + + case OUTPUT_IFDEF: + print_ifdef_script (script); + break; + + case OUTPUT_SDIFF: + print_sdiff_script (script); + } + + finish_output (); + } + } + + free (filevec[0].undiscarded); + + free (filevec[0].changed_flag - 1); + + for (i = 1; i >= 0; --i) + free (filevec[i].equivs); + + for (i = 0; i < 2; ++i) + free (filevec[i].linbuf + filevec[i].linbuf_base); + + for (e = script; e; e = p) + { + p = e->link; + free (e); + } + + if (! ROBUST_OUTPUT_STYLE (output_style)) + for (i = 0; i < 2; ++i) + if (filevec[i].missing_newline) + { + diff_error ("No newline at end of file %s", filevec[i].name, ""); + changes = 2; + } + } + + if (filevec[0].buffer != filevec[1].buffer) + free (filevec[0].buffer); + free (filevec[1].buffer); + + return changes; +} diff --git a/contrib/cvs/diff/cmpbuf.c b/contrib/cvs/diff/cmpbuf.c new file mode 100644 index 0000000..e95a8f9 --- /dev/null +++ b/contrib/cvs/diff/cmpbuf.c @@ -0,0 +1,40 @@ +/* Buffer primitives for comparison operations. + Copyright (C) 1993 Free Software Foundation, Inc. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2, or (at your option) + any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ + +#include "system.h" +#include "cmpbuf.h" + +/* Least common multiple of two buffer sizes A and B. */ + +size_t +buffer_lcm (a, b) + size_t a, b; +{ + size_t m, n, r; + + /* Yield reasonable values if buffer sizes are zero. */ + if (!a) + return b ? b : 8 * 1024; + if (!b) + return a; + + /* n = gcd (a, b) */ + for (m = a, n = b; (r = m % n) != 0; m = n, n = r) + continue; + + return a/n * b; +} diff --git a/contrib/cvs/diff/cmpbuf.h b/contrib/cvs/diff/cmpbuf.h new file mode 100644 index 0000000..e3852b7 --- /dev/null +++ b/contrib/cvs/diff/cmpbuf.h @@ -0,0 +1,20 @@ +/* Buffer primitives for comparison operations. + Copyright (C) 1993 Free Software Foundation, Inc. + +This file is part of GNU DIFF. + +GNU DIFF is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +GNU DIFF is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU DIFF; see the file COPYING. If not, write to +the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ + +size_t buffer_lcm PARAMS((size_t, size_t)); diff --git a/contrib/cvs/diff/context.c b/contrib/cvs/diff/context.c new file mode 100644 index 0000000..14f950c --- /dev/null +++ b/contrib/cvs/diff/context.c @@ -0,0 +1,468 @@ +/* Context-format output routines for GNU DIFF. + Copyright (C) 1988,1989,1991,1992,1993,1994 Free Software Foundation, Inc. + +This file is part of GNU DIFF. + +GNU DIFF is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +GNU DIFF is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU DIFF; see the file COPYING. If not, write to +the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ + +#include "diff.h" + +static struct change *find_hunk PARAMS((struct change *)); +static void find_function PARAMS((struct file_data const *, int, char const **, size_t *)); +static void mark_ignorable PARAMS((struct change *)); +static void pr_context_hunk PARAMS((struct change *)); +static void pr_unidiff_hunk PARAMS((struct change *)); +static void print_context_label PARAMS ((char const *, struct file_data *, char const *)); +static void print_context_number_range PARAMS((struct file_data const *, int, int)); +static void print_unidiff_number_range PARAMS((struct file_data const *, int, int)); + +/* Last place find_function started searching from. */ +static int find_function_last_search; + +/* The value find_function returned when it started searching there. */ +static int find_function_last_match; + +/* Print a label for a context diff, with a file name and date or a label. */ + +static void +print_context_label (mark, inf, label) + char const *mark; + struct file_data *inf; + char const *label; +{ + if (label) + fprintf (outfile, "%s %s\n", mark, label); + else + { + char const *ct = ctime (&inf->stat.st_mtime); + if (!ct) + ct = "?\n"; + /* See Posix.2 section 4.17.6.1.4 for this format. */ + fprintf (outfile, "%s %s\t%s", mark, inf->name, ct); + } +} + +/* Print a header for a context diff, with the file names and dates. */ + +void +print_context_header (inf, unidiff_flag) + struct file_data inf[]; + int unidiff_flag; +{ + if (unidiff_flag) + { + print_context_label ("---", &inf[0], file_label[0]); + print_context_label ("+++", &inf[1], file_label[1]); + } + else + { + print_context_label ("***", &inf[0], file_label[0]); + print_context_label ("---", &inf[1], file_label[1]); + } +} + +/* Print an edit script in context format. */ + +void +print_context_script (script, unidiff_flag) + struct change *script; + int unidiff_flag; +{ + if (ignore_blank_lines_flag || ignore_regexp_list) + mark_ignorable (script); + else + { + struct change *e; + for (e = script; e; e = e->link) + e->ignore = 0; + } + + find_function_last_search = - files[0].prefix_lines; + find_function_last_match = find_function_last_search - 1; + + if (unidiff_flag) + print_script (script, find_hunk, pr_unidiff_hunk); + else + print_script (script, find_hunk, pr_context_hunk); +} + +/* Print a pair of line numbers with a comma, translated for file FILE. + If the second number is not greater, use the first in place of it. + + Args A and B are internal line numbers. + We print the translated (real) line numbers. */ + +static void +print_context_number_range (file, a, b) + struct file_data const *file; + int a, b; +{ + int trans_a, trans_b; + translate_range (file, a, b, &trans_a, &trans_b); + + /* Note: we can have B < A in the case of a range of no lines. + In this case, we should print the line number before the range, + which is B. */ + if (trans_b > trans_a) + fprintf (outfile, "%d,%d", trans_a, trans_b); + else + fprintf (outfile, "%d", trans_b); +} + +/* Print a portion of an edit script in context format. + HUNK is the beginning of the portion to be printed. + The end is marked by a `link' that has been nulled out. + + Prints out lines from both files, and precedes each + line with the appropriate flag-character. */ + +static void +pr_context_hunk (hunk) + struct change *hunk; +{ + int first0, last0, first1, last1, show_from, show_to, i; + struct change *next; + char const *prefix; + char const *function; + size_t function_length; + FILE *out; + + /* Determine range of line numbers involved in each file. */ + + analyze_hunk (hunk, &first0, &last0, &first1, &last1, &show_from, &show_to); + + if (!show_from && !show_to) + return; + + /* Include a context's width before and after. */ + + i = - files[0].prefix_lines; + first0 = max (first0 - context, i); + first1 = max (first1 - context, i); + last0 = min (last0 + context, files[0].valid_lines - 1); + last1 = min (last1 + context, files[1].valid_lines - 1); + + /* If desired, find the preceding function definition line in file 0. */ + function = 0; + if (function_regexp_list) + find_function (&files[0], first0, &function, &function_length); + + begin_output (); + out = outfile; + + /* If we looked for and found a function this is part of, + include its name in the header of the diff section. */ + fprintf (out, "***************"); + + if (function) + { + fprintf (out, " "); + fwrite (function, 1, min (function_length - 1, 40), out); + } + + fprintf (out, "\n*** "); + print_context_number_range (&files[0], first0, last0); + fprintf (out, " ****\n"); + + if (show_from) + { + next = hunk; + + for (i = first0; i <= last0; i++) + { + /* Skip past changes that apply (in file 0) + only to lines before line I. */ + + while (next && next->line0 + next->deleted <= i) + next = next->link; + + /* Compute the marking for line I. */ + + prefix = " "; + if (next && next->line0 <= i) + /* The change NEXT covers this line. + If lines were inserted here in file 1, this is "changed". + Otherwise it is "deleted". */ + prefix = (next->inserted > 0 ? "!" : "-"); + + print_1_line (prefix, &files[0].linbuf[i]); + } + } + + fprintf (out, "--- "); + print_context_number_range (&files[1], first1, last1); + fprintf (out, " ----\n"); + + if (show_to) + { + next = hunk; + + for (i = first1; i <= last1; i++) + { + /* Skip past changes that apply (in file 1) + only to lines before line I. */ + + while (next && next->line1 + next->inserted <= i) + next = next->link; + + /* Compute the marking for line I. */ + + prefix = " "; + if (next && next->line1 <= i) + /* The change NEXT covers this line. + If lines were deleted here in file 0, this is "changed". + Otherwise it is "inserted". */ + prefix = (next->deleted > 0 ? "!" : "+"); + + print_1_line (prefix, &files[1].linbuf[i]); + } + } +} + +/* Print a pair of line numbers with a comma, translated for file FILE. + If the second number is smaller, use the first in place of it. + If the numbers are equal, print just one number. + + Args A and B are internal line numbers. + We print the translated (real) line numbers. */ + +static void +print_unidiff_number_range (file, a, b) + struct file_data const *file; + int a, b; +{ + int trans_a, trans_b; + translate_range (file, a, b, &trans_a, &trans_b); + + /* Note: we can have B < A in the case of a range of no lines. + In this case, we should print the line number before the range, + which is B. */ + if (trans_b <= trans_a) + fprintf (outfile, trans_b == trans_a ? "%d" : "%d,0", trans_b); + else + fprintf (outfile, "%d,%d", trans_a, trans_b - trans_a + 1); +} + +/* Print a portion of an edit script in unidiff format. + HUNK is the beginning of the portion to be printed. + The end is marked by a `link' that has been nulled out. + + Prints out lines from both files, and precedes each + line with the appropriate flag-character. */ + +static void +pr_unidiff_hunk (hunk) + struct change *hunk; +{ + int first0, last0, first1, last1, show_from, show_to, i, j, k; + struct change *next; + char const *function; + size_t function_length; + FILE *out; + + /* Determine range of line numbers involved in each file. */ + + analyze_hunk (hunk, &first0, &last0, &first1, &last1, &show_from, &show_to); + + if (!show_from && !show_to) + return; + + /* Include a context's width before and after. */ + + i = - files[0].prefix_lines; + first0 = max (first0 - context, i); + first1 = max (first1 - context, i); + last0 = min (last0 + context, files[0].valid_lines - 1); + last1 = min (last1 + context, files[1].valid_lines - 1); + + /* If desired, find the preceding function definition line in file 0. */ + function = 0; + if (function_regexp_list) + find_function (&files[0], first0, &function, &function_length); + + begin_output (); + out = outfile; + + fprintf (out, "@@ -"); + print_unidiff_number_range (&files[0], first0, last0); + fprintf (out, " +"); + print_unidiff_number_range (&files[1], first1, last1); + fprintf (out, " @@"); + + /* If we looked for and found a function this is part of, + include its name in the header of the diff section. */ + + if (function) + { + putc (' ', out); + fwrite (function, 1, min (function_length - 1, 40), out); + } + putc ('\n', out); + + next = hunk; + i = first0; + j = first1; + + while (i <= last0 || j <= last1) + { + + /* If the line isn't a difference, output the context from file 0. */ + + if (!next || i < next->line0) + { + putc (tab_align_flag ? '\t' : ' ', out); + print_1_line (0, &files[0].linbuf[i++]); + j++; + } + else + { + /* For each difference, first output the deleted part. */ + + k = next->deleted; + while (k--) + { + putc ('-', out); + if (tab_align_flag) + putc ('\t', out); + print_1_line (0, &files[0].linbuf[i++]); + } + + /* Then output the inserted part. */ + + k = next->inserted; + while (k--) + { + putc ('+', out); + if (tab_align_flag) + putc ('\t', out); + print_1_line (0, &files[1].linbuf[j++]); + } + + /* We're done with this hunk, so on to the next! */ + + next = next->link; + } + } +} + +/* Scan a (forward-ordered) edit script for the first place that more than + 2*CONTEXT unchanged lines appear, and return a pointer + to the `struct change' for the last change before those lines. */ + +static struct change * +find_hunk (start) + struct change *start; +{ + struct change *prev; + int top0, top1; + int thresh; + + do + { + /* Compute number of first line in each file beyond this changed. */ + top0 = start->line0 + start->deleted; + top1 = start->line1 + start->inserted; + prev = start; + start = start->link; + /* Threshold distance is 2*CONTEXT between two non-ignorable changes, + but only CONTEXT if one is ignorable. */ + thresh = ((prev->ignore || (start && start->ignore)) + ? context + : 2 * context + 1); + /* It is not supposed to matter which file we check in the end-test. + If it would matter, crash. */ + if (start && start->line0 - top0 != start->line1 - top1) + abort (); + } while (start + /* Keep going if less than THRESH lines + elapse before the affected line. */ + && start->line0 < top0 + thresh); + + return prev; +} + +/* Set the `ignore' flag properly in each change in SCRIPT. + It should be 1 if all the lines inserted or deleted in that change + are ignorable lines. */ + +static void +mark_ignorable (script) + struct change *script; +{ + while (script) + { + struct change *next = script->link; + int first0, last0, first1, last1, deletes, inserts; + + /* Turn this change into a hunk: detach it from the others. */ + script->link = 0; + + /* Determine whether this change is ignorable. */ + analyze_hunk (script, &first0, &last0, &first1, &last1, &deletes, &inserts); + /* Reconnect the chain as before. */ + script->link = next; + + /* If the change is ignorable, mark it. */ + script->ignore = (!deletes && !inserts); + + /* Advance to the following change. */ + script = next; + } +} + +/* Find the last function-header line in FILE prior to line number LINENUM. + This is a line containing a match for the regexp in `function_regexp'. + Store the address of the line text into LINEP and the length of the + line into LENP. + Do not store anything if no function-header is found. */ + +static void +find_function (file, linenum, linep, lenp) + struct file_data const *file; + int linenum; + char const **linep; + size_t *lenp; +{ + int i = linenum; + int last = find_function_last_search; + find_function_last_search = i; + + while (--i >= last) + { + /* See if this line is what we want. */ + struct regexp_list *r; + char const *line = file->linbuf[i]; + size_t len = file->linbuf[i + 1] - line; + + for (r = function_regexp_list; r; r = r->next) + if (0 <= re_search (&r->buf, line, len, 0, len, 0)) + { + *linep = line; + *lenp = len; + find_function_last_match = i; + return; + } + } + /* If we search back to where we started searching the previous time, + find the line we found last time. */ + if (find_function_last_match >= - file->prefix_lines) + { + i = find_function_last_match; + *linep = file->linbuf[i]; + *lenp = file->linbuf[i + 1] - *linep; + return; + } + return; +} diff --git a/contrib/cvs/diff/diagmeet.note b/contrib/cvs/diff/diagmeet.note new file mode 100644 index 0000000..8f7242c --- /dev/null +++ b/contrib/cvs/diff/diagmeet.note @@ -0,0 +1,71 @@ +Here is a comparison matrix which shows a case in which +it is possible for the forward and backward scan in `diag' +to meet along a nonzero length of diagonal simultaneous +(so that bdiag[d] and fdiag[d] are not equal) +even though there is no snake on that diagonal at the meeting point. + + + 85 1 1 1 159 1 1 17 + 1 2 3 4 +60 + 1 2 +1 + 2 2 3 4 +71 + 3 3 4 5 +85 + 4 3 4 5 +17 + 5 4 5 +1 + 6 4 5 6 +183 + 7 5 6 7 +10 + 8 6 7 +1 + 9 6 7 8 +12 + 7 8 9 10 +13 + 10 8 9 10 +14 + 10 9 10 +17 + 10 10 +1 + 10 9 10 +1 + 8 10 10 10 +183 + 8 7 9 9 9 +10 + 7 6 8 9 8 8 +1 + 6 5 7 7 +1 + 5 6 6 +1 + 5 5 5 +50 + 5 4 4 4 +1 + 4 3 3 +85 + 5 4 3 2 2 +1 + 2 1 +17 + 5 4 3 2 1 1 +1 + 1 0 + 85 1 1 1 159 1 1 17 + + + + + + + + + diff --git a/contrib/cvs/diff/diff.c b/contrib/cvs/diff/diff.c new file mode 100644 index 0000000..c0e37d7 --- /dev/null +++ b/contrib/cvs/diff/diff.c @@ -0,0 +1,1214 @@ +/* GNU DIFF entry routine. + Copyright (C) 1988, 1989, 1992, 1993, 1994, 1997 Free Software Foundation, Inc. + +This file is part of GNU DIFF. + +GNU DIFF is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +GNU DIFF is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU DIFF; see the file COPYING. If not, write to +the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ + +/* GNU DIFF was written by Mike Haertel, David Hayes, + Richard Stallman, Len Tower, and Paul Eggert. */ + +#define GDIFF_MAIN +#include "diff.h" +#include <signal.h> +#include "getopt.h" +#include "fnmatch.h" + +#ifndef DEFAULT_WIDTH +#define DEFAULT_WIDTH 130 +#endif + +#ifndef GUTTER_WIDTH_MINIMUM +#define GUTTER_WIDTH_MINIMUM 3 +#endif + +/* diff.c has a real initialize_main function. */ +#ifdef initialize_main +#undef initialize_main +#endif + +static char const *filetype PARAMS((struct stat const *)); +static char *option_list PARAMS((char **, int)); +static int add_exclude_file PARAMS((char const *)); +static int ck_atoi PARAMS((char const *, int *)); +static int compare_files PARAMS((char const *, char const *, char const *, char const *, int)); +static int specify_format PARAMS((char **, char *)); +static void add_exclude PARAMS((char const *)); +static void add_regexp PARAMS((struct regexp_list **, char const *)); +static void specify_style PARAMS((enum output_style)); +static int try_help PARAMS((char const *)); +static void check_output PARAMS((FILE *)); +static void usage PARAMS((void)); +static void initialize_main PARAMS((int *, char ***)); + +/* Nonzero for -r: if comparing two directories, + compare their common subdirectories recursively. */ + +static int recursive; + +/* For debugging: don't do discard_confusing_lines. */ + +int no_discards; + +#if HAVE_SETMODE +/* I/O mode: nonzero only if using binary input/output. */ +static int binary_I_O; +#endif + +/* Return a string containing the command options with which diff was invoked. + Spaces appear between what were separate ARGV-elements. + There is a space at the beginning but none at the end. + If there were no options, the result is an empty string. + + Arguments: OPTIONVEC, a vector containing separate ARGV-elements, and COUNT, + the length of that vector. */ + +static char * +option_list (optionvec, count) + char **optionvec; /* Was `vector', but that collides on Alliant. */ + int count; +{ + int i; + size_t length = 0; + char *result; + + for (i = 0; i < count; i++) + length += strlen (optionvec[i]) + 1; + + result = xmalloc (length + 1); + result[0] = 0; + + for (i = 0; i < count; i++) + { + strcat (result, " "); + strcat (result, optionvec[i]); + } + + return result; +} + +/* Convert STR to a positive integer, storing the result in *OUT. + If STR is not a valid integer, return -1 (otherwise 0). */ +static int +ck_atoi (str, out) + char const *str; + int *out; +{ + char const *p; + for (p = str; *p; p++) + if (*p < '0' || *p > '9') + return -1; + + *out = atoi (optarg); + return 0; +} + +/* Keep track of excluded file name patterns. */ + +static char const **exclude; +static int exclude_alloc, exclude_count; + +int +excluded_filename (f) + char const *f; +{ + int i; + for (i = 0; i < exclude_count; i++) + if (fnmatch (exclude[i], f, 0) == 0) + return 1; + return 0; +} + +static void +add_exclude (pattern) + char const *pattern; +{ + if (exclude_alloc <= exclude_count) + exclude = (char const **) + (exclude_alloc == 0 + ? xmalloc ((exclude_alloc = 64) * sizeof (*exclude)) + : xrealloc (exclude, (exclude_alloc *= 2) * sizeof (*exclude))); + + exclude[exclude_count++] = pattern; +} + +static int +add_exclude_file (name) + char const *name; +{ + struct file_data f; + char *p, *q, *lim; + + f.name = optarg; + f.desc = (strcmp (optarg, "-") == 0 + ? STDIN_FILENO + : open (optarg, O_RDONLY, 0)); + if (f.desc < 0 || fstat (f.desc, &f.stat) != 0) + return -1; + + sip (&f, 1); + slurp (&f); + + for (p = f.buffer, lim = p + f.buffered_chars; p < lim; p = q) + { + q = (char *) memchr (p, '\n', lim - p); + if (!q) + q = lim; + *q++ = 0; + add_exclude (p); + } + + return close (f.desc); +} + +/* The numbers 129- that appear in the fourth element of some entries + tell the big switch in `diff_run' how to process those options. */ + +static struct option const longopts[] = +{ + {"ignore-blank-lines", 0, 0, 'B'}, + {"context", 2, 0, 'C'}, + {"ifdef", 1, 0, 'D'}, + {"show-function-line", 1, 0, 'F'}, + {"speed-large-files", 0, 0, 'H'}, + {"ignore-matching-lines", 1, 0, 'I'}, + {"label", 1, 0, 'L'}, + {"file-label", 1, 0, 'L'}, /* An alias, no longer recommended */ + {"new-file", 0, 0, 'N'}, + {"entire-new-file", 0, 0, 'N'}, /* An alias, no longer recommended */ + {"unidirectional-new-file", 0, 0, 'P'}, + {"starting-file", 1, 0, 'S'}, + {"initial-tab", 0, 0, 'T'}, + {"width", 1, 0, 'W'}, + {"text", 0, 0, 'a'}, + {"ascii", 0, 0, 'a'}, /* An alias, no longer recommended */ + {"ignore-space-change", 0, 0, 'b'}, + {"minimal", 0, 0, 'd'}, + {"ed", 0, 0, 'e'}, + {"forward-ed", 0, 0, 'f'}, + {"ignore-case", 0, 0, 'i'}, + {"paginate", 0, 0, 'l'}, + {"print", 0, 0, 'l'}, /* An alias, no longer recommended */ + {"rcs", 0, 0, 'n'}, + {"show-c-function", 0, 0, 'p'}, + {"brief", 0, 0, 'q'}, + {"recursive", 0, 0, 'r'}, + {"report-identical-files", 0, 0, 's'}, + {"expand-tabs", 0, 0, 't'}, + {"version", 0, 0, 'v'}, + {"ignore-all-space", 0, 0, 'w'}, + {"exclude", 1, 0, 'x'}, + {"exclude-from", 1, 0, 'X'}, + {"side-by-side", 0, 0, 'y'}, + {"unified", 2, 0, 'U'}, + {"left-column", 0, 0, 129}, + {"suppress-common-lines", 0, 0, 130}, + {"sdiff-merge-assist", 0, 0, 131}, + {"old-line-format", 1, 0, 132}, + {"new-line-format", 1, 0, 133}, + {"unchanged-line-format", 1, 0, 134}, + {"line-format", 1, 0, 135}, + {"old-group-format", 1, 0, 136}, + {"new-group-format", 1, 0, 137}, + {"unchanged-group-format", 1, 0, 138}, + {"changed-group-format", 1, 0, 139}, + {"horizon-lines", 1, 0, 140}, + {"help", 0, 0, 141}, + {"binary", 0, 0, 142}, + {0, 0, 0, 0} +}; + +int +diff_run (argc, argv, out) + int argc; + char *argv[]; + char *out; +{ + int val; + int c; + int prev = -1; + int width = DEFAULT_WIDTH; + int show_c_function = 0; + int optind_old; + + /* Do our initializations. */ + initialize_main (&argc, &argv); + + /* Decode the options. */ + + optind_old = optind; + optind = 0; + while ((c = getopt_long (argc, argv, + "0123456789abBcC:dD:efF:hHiI:lL:nNpPqrsS:tTuU:vwW:x:X:y", + longopts, 0)) != EOF) + { + switch (c) + { + /* All digits combine in decimal to specify the context-size. */ + case '1': + case '2': + case '3': + case '4': + case '5': + case '6': + case '7': + case '8': + case '9': + case '0': + if (context == -1) + context = 0; + /* If a context length has already been specified, + more digits allowed only if they follow right after the others. + Reject two separate runs of digits, or digits after -C. */ + else if (prev < '0' || prev > '9') + fatal ("context length specified twice"); + + context = context * 10 + c - '0'; + break; + + case 'a': + /* Treat all files as text files; never treat as binary. */ + always_text_flag = 1; + break; + + case 'b': + /* Ignore changes in amount of white space. */ + ignore_space_change_flag = 1; + ignore_some_changes = 1; + ignore_some_line_changes = 1; + break; + + case 'B': + /* Ignore changes affecting only blank lines. */ + ignore_blank_lines_flag = 1; + ignore_some_changes = 1; + break; + + case 'C': /* +context[=lines] */ + case 'U': /* +unified[=lines] */ + if (optarg) + { + if (context >= 0) + fatal ("context length specified twice"); + + if (ck_atoi (optarg, &context)) + fatal ("invalid context length argument"); + } + + /* Falls through. */ + case 'c': + /* Make context-style output. */ + specify_style (c == 'U' ? OUTPUT_UNIFIED : OUTPUT_CONTEXT); + break; + + case 'd': + /* Don't discard lines. This makes things slower (sometimes much + slower) but will find a guaranteed minimal set of changes. */ + no_discards = 1; + break; + + case 'D': + /* Make merged #ifdef output. */ + specify_style (OUTPUT_IFDEF); + { + int i, err = 0; + static char const C_ifdef_group_formats[] = + "#ifndef %s\n%%<#endif /* not %s */\n%c#ifdef %s\n%%>#endif /* %s */\n%c%%=%c#ifndef %s\n%%<#else /* %s */\n%%>#endif /* %s */\n"; + char *b = xmalloc (sizeof (C_ifdef_group_formats) + + 7 * strlen(optarg) - 14 /* 7*"%s" */ + - 8 /* 5*"%%" + 3*"%c" */); + sprintf (b, C_ifdef_group_formats, + optarg, optarg, 0, + optarg, optarg, 0, 0, + optarg, optarg, optarg); + for (i = 0; i < 4; i++) + { + err |= specify_format (&group_format[i], b); + b += strlen (b) + 1; + } + if (err) + diff_error ("conflicting #ifdef formats", 0, 0); + } + break; + + case 'e': + /* Make output that is a valid `ed' script. */ + specify_style (OUTPUT_ED); + break; + + case 'f': + /* Make output that looks vaguely like an `ed' script + but has changes in the order they appear in the file. */ + specify_style (OUTPUT_FORWARD_ED); + break; + + case 'F': + /* Show, for each set of changes, the previous line that + matches the specified regexp. Currently affects only + context-style output. */ + add_regexp (&function_regexp_list, optarg); + break; + + case 'h': + /* Split the files into chunks of around 1500 lines + for faster processing. Usually does not change the result. + + This currently has no effect. */ + break; + + case 'H': + /* Turn on heuristics that speed processing of large files + with a small density of changes. */ + heuristic = 1; + break; + + case 'i': + /* Ignore changes in case. */ + ignore_case_flag = 1; + ignore_some_changes = 1; + ignore_some_line_changes = 1; + break; + + case 'I': + /* Ignore changes affecting only lines that match the + specified regexp. */ + add_regexp (&ignore_regexp_list, optarg); + ignore_some_changes = 1; + break; + + case 'l': + /* Pass the output through `pr' to paginate it. */ + paginate_flag = 1; +#if !defined(SIGCHLD) && defined(SIGCLD) +#define SIGCHLD SIGCLD +#endif +#ifdef SIGCHLD + /* Pagination requires forking and waiting, and + System V fork+wait does not work if SIGCHLD is ignored. */ + signal (SIGCHLD, SIG_DFL); +#endif + break; + + case 'L': + /* Specify file labels for `-c' output headers. */ + if (!file_label[0]) + file_label[0] = optarg; + else if (!file_label[1]) + file_label[1] = optarg; + else + fatal ("too many file label options"); + break; + + case 'n': + /* Output RCS-style diffs, like `-f' except that each command + specifies the number of lines affected. */ + specify_style (OUTPUT_RCS); + break; + + case 'N': + /* When comparing directories, if a file appears only in one + directory, treat it as present but empty in the other. */ + entire_new_file_flag = 1; + break; + + case 'p': + /* Make context-style output and show name of last C function. */ + show_c_function = 1; + add_regexp (&function_regexp_list, "^[_a-zA-Z$]"); + break; + + case 'P': + /* When comparing directories, if a file appears only in + the second directory of the two, + treat it as present but empty in the other. */ + unidirectional_new_file_flag = 1; + break; + + case 'q': + no_details_flag = 1; + break; + + case 'r': + /* When comparing directories, + recursively compare any subdirectories found. */ + recursive = 1; + break; + + case 's': + /* Print a message if the files are the same. */ + print_file_same_flag = 1; + break; + + case 'S': + /* When comparing directories, start with the specified + file name. This is used for resuming an aborted comparison. */ + dir_start_file = optarg; + break; + + case 't': + /* Expand tabs to spaces in the output so that it preserves + the alignment of the input files. */ + tab_expand_flag = 1; + break; + + case 'T': + /* Use a tab in the output, rather than a space, before the + text of an input line, so as to keep the proper alignment + in the input line without changing the characters in it. */ + tab_align_flag = 1; + break; + + case 'u': + /* Output the context diff in unidiff format. */ + specify_style (OUTPUT_UNIFIED); + break; + + case 'v': + printf ("diff - GNU diffutils version %s\n", diff_version_string); + return 0; + + case 'w': + /* Ignore horizontal white space when comparing lines. */ + ignore_all_space_flag = 1; + ignore_some_changes = 1; + ignore_some_line_changes = 1; + break; + + case 'x': + add_exclude (optarg); + break; + + case 'X': + if (add_exclude_file (optarg) != 0) + pfatal_with_name (optarg); + break; + + case 'y': + /* Use side-by-side (sdiff-style) columnar output. */ + specify_style (OUTPUT_SDIFF); + break; + + case 'W': + /* Set the line width for OUTPUT_SDIFF. */ + if (ck_atoi (optarg, &width) || width <= 0) + fatal ("column width must be a positive integer"); + break; + + case 129: + sdiff_left_only = 1; + break; + + case 130: + sdiff_skip_common_lines = 1; + break; + + case 131: + /* sdiff-style columns output. */ + specify_style (OUTPUT_SDIFF); + sdiff_help_sdiff = 1; + break; + + case 132: + case 133: + case 134: + specify_style (OUTPUT_IFDEF); + if (specify_format (&line_format[c - 132], optarg) != 0) + diff_error ("conflicting line format", 0, 0); + break; + + case 135: + specify_style (OUTPUT_IFDEF); + { + int i, err = 0; + for (i = 0; i < sizeof (line_format) / sizeof (*line_format); i++) + err |= specify_format (&line_format[i], optarg); + if (err) + diff_error ("conflicting line format", 0, 0); + } + break; + + case 136: + case 137: + case 138: + case 139: + specify_style (OUTPUT_IFDEF); + if (specify_format (&group_format[c - 136], optarg) != 0) + diff_error ("conflicting group format", 0, 0); + break; + + case 140: + if (ck_atoi (optarg, &horizon_lines) || horizon_lines < 0) + fatal ("horizon must be a nonnegative integer"); + break; + + case 141: + usage (); + check_output (stdout); + return 0; + + case 142: + /* Use binary I/O when reading and writing data. + On Posix hosts, this has no effect. */ +#if HAVE_SETMODE + binary_I_O = 1; +# if 0 + /* Because this code is leftover from pre-library days, + there is no way to set stdout back to the default mode + when we are done. As it turns out, I think the only + parts of CVS that pass out == NULL, and thus cause diff + to write to stdout, are "cvs diff" and "cvs rdiff". So + I'm not going to worry about this too much yet. */ + setmode (STDOUT_FILENO, O_BINARY); +# else + if (out == NULL) + error (0, 0, "warning: did not set stdout to binary mode"); +# endif +#endif + break; + + default: + return try_help (0); + } + prev = c; + } + + if (argc - optind != 2) + return try_help (argc - optind < 2 ? "missing operand" : "extra operand"); + + { + /* + * We maximize first the half line width, and then the gutter width, + * according to the following constraints: + * 1. Two half lines plus a gutter must fit in a line. + * 2. If the half line width is nonzero: + * a. The gutter width is at least GUTTER_WIDTH_MINIMUM. + * b. If tabs are not expanded to spaces, + * a half line plus a gutter is an integral number of tabs, + * so that tabs in the right column line up. + */ + int t = tab_expand_flag ? 1 : TAB_WIDTH; + int off = (width + t + GUTTER_WIDTH_MINIMUM) / (2*t) * t; + sdiff_half_width = max (0, min (off - GUTTER_WIDTH_MINIMUM, width - off)), + sdiff_column2_offset = sdiff_half_width ? off : width; + } + + if (show_c_function && output_style != OUTPUT_UNIFIED) + specify_style (OUTPUT_CONTEXT); + + if (output_style != OUTPUT_CONTEXT && output_style != OUTPUT_UNIFIED) + context = 0; + else if (context == -1) + /* Default amount of context for -c. */ + context = 3; + + if (output_style == OUTPUT_IFDEF) + { + /* Format arrays are char *, not char const *, + because integer formats are temporarily modified. + But it is safe to assign a constant like "%=" to a format array, + since "%=" does not format any integers. */ + int i; + for (i = 0; i < sizeof (line_format) / sizeof (*line_format); i++) + if (!line_format[i]) + line_format[i] = "%l\n"; + if (!group_format[OLD]) + group_format[OLD] + = group_format[UNCHANGED] ? group_format[UNCHANGED] : "%<"; + if (!group_format[NEW]) + group_format[NEW] + = group_format[UNCHANGED] ? group_format[UNCHANGED] : "%>"; + if (!group_format[UNCHANGED]) + group_format[UNCHANGED] = "%="; + if (!group_format[CHANGED]) + group_format[CHANGED] = concat (group_format[OLD], + group_format[NEW], ""); + } + + no_diff_means_no_output = + (output_style == OUTPUT_IFDEF ? + (!*group_format[UNCHANGED] + || (strcmp (group_format[UNCHANGED], "%=") == 0 + && !*line_format[UNCHANGED])) + : output_style == OUTPUT_SDIFF ? sdiff_skip_common_lines : 1); + + switch_string = option_list (argv + 1, optind - 1); + + if (out == NULL) + outfile = stdout; + else + { +#if HAVE_SETMODE + /* A diff which is full of ^Z and such isn't going to work + very well in text mode. */ + if (binary_I_O) + outfile = fopen (out, "wb"); + else +#endif + outfile = fopen (out, "w"); + if (outfile == NULL) + { + perror_with_name ("could not open output file"); + return 2; + } + } + + /* Set the jump buffer, so that diff may abort execution without + terminating the process. */ + if ((val = setjmp (diff_abort_buf)) != 0) + { + optind = optind_old; + if (outfile != stdout) + fclose (outfile); + return val; + } + + val = compare_files (0, argv[optind], 0, argv[optind + 1], 0); + + /* Print any messages that were saved up for last. */ + print_message_queue (); + + free (switch_string); + + optind = optind_old; + check_output (outfile); + if (outfile != stdout) + if (fclose (outfile) != 0) + perror ("close error on output file"); + return val; +} + +/* Add the compiled form of regexp PATTERN to REGLIST. */ + +static void +add_regexp (reglist, pattern) + struct regexp_list **reglist; + char const *pattern; +{ + struct regexp_list *r; + char const *m; + + r = (struct regexp_list *) xmalloc (sizeof (*r)); + bzero (r, sizeof (*r)); + r->buf.fastmap = xmalloc (256); + m = re_compile_pattern (pattern, strlen (pattern), &r->buf); + if (m != 0) + diff_error ("%s: %s", pattern, m); + + /* Add to the start of the list, since it's easier than the end. */ + r->next = *reglist; + *reglist = r; +} + +static int +try_help (reason) + char const *reason; +{ + if (reason) + diff_error ("%s", reason, 0); + diff_error ("Try `%s --help' for more information.", diff_program_name, 0); + return 2; +} + +static void +check_output (file) + FILE *file; +{ + if (ferror (file) || fflush (file) != 0) + fatal ("write error"); +} + +static char const * const option_help[] = { +"-i --ignore-case Consider upper- and lower-case to be the same.", +"-w --ignore-all-space Ignore all white space.", +"-b --ignore-space-change Ignore changes in the amount of white space.", +"-B --ignore-blank-lines Ignore changes whose lines are all blank.", +"-I RE --ignore-matching-lines=RE Ignore changes whose lines all match RE.", +#if HAVE_SETMODE +"--binary Read and write data in binary mode.", +#endif +"-a --text Treat all files as text.\n", +"-c -C NUM --context[=NUM] Output NUM (default 2) lines of copied context.", +"-u -U NUM --unified[=NUM] Output NUM (default 2) lines of unified context.", +" -NUM Use NUM context lines.", +" -L LABEL --label LABEL Use LABEL instead of file name.", +" -p --show-c-function Show which C function each change is in.", +" -F RE --show-function-line=RE Show the most recent line matching RE.", +"-q --brief Output only whether files differ.", +"-e --ed Output an ed script.", +"-n --rcs Output an RCS format diff.", +"-y --side-by-side Output in two columns.", +" -w NUM --width=NUM Output at most NUM (default 130) characters per line.", +" --left-column Output only the left column of common lines.", +" --suppress-common-lines Do not output common lines.", +"-DNAME --ifdef=NAME Output merged file to show `#ifdef NAME' diffs.", +"--GTYPE-group-format=GFMT Similar, but format GTYPE input groups with GFMT.", +"--line-format=LFMT Similar, but format all input lines with LFMT.", +"--LTYPE-line-format=LFMT Similar, but format LTYPE input lines with LFMT.", +" LTYPE is `old', `new', or `unchanged'. GTYPE is LTYPE or `changed'.", +" GFMT may contain:", +" %< lines from FILE1", +" %> lines from FILE2", +" %= lines common to FILE1 and FILE2", +" %[-][WIDTH][.[PREC]]{doxX}LETTER printf-style spec for LETTER", +" LETTERs are as follows for new group, lower case for old group:", +" F first line number", +" L last line number", +" N number of lines = L-F+1", +" E F-1", +" M L+1", +" LFMT may contain:", +" %L contents of line", +" %l contents of line, excluding any trailing newline", +" %[-][WIDTH][.[PREC]]{doxX}n printf-style spec for input line number", +" Either GFMT or LFMT may contain:", +" %% %", +" %c'C' the single character C", +" %c'\\OOO' the character with octal code OOO\n", +"-l --paginate Pass the output through `pr' to paginate it.", +"-t --expand-tabs Expand tabs to spaces in output.", +"-T --initial-tab Make tabs line up by prepending a tab.\n", +"-r --recursive Recursively compare any subdirectories found.", +"-N --new-file Treat absent files as empty.", +"-P --unidirectional-new-file Treat absent first files as empty.", +"-s --report-identical-files Report when two files are the same.", +"-x PAT --exclude=PAT Exclude files that match PAT.", +"-X FILE --exclude-from=FILE Exclude files that match any pattern in FILE.", +"-S FILE --starting-file=FILE Start with FILE when comparing directories.\n", +"--horizon-lines=NUM Keep NUM lines of the common prefix and suffix.", +"-d --minimal Try hard to find a smaller set of changes.", +"-H --speed-large-files Assume large files and many scattered small changes.\n", +"-v --version Output version info.", +"--help Output this help.", +0 +}; + +static void +usage () +{ + char const * const *p; + + printf ("Usage: %s [OPTION]... FILE1 FILE2\n\n", diff_program_name); + for (p = option_help; *p; p++) + printf (" %s\n", *p); + printf ("\nIf FILE1 or FILE2 is `-', read standard input.\n"); +} + +static int +specify_format (var, value) + char **var; + char *value; +{ + int err = *var ? strcmp (*var, value) : 0; + *var = value; + return err; +} + +static void +specify_style (style) + enum output_style style; +{ + if (output_style != OUTPUT_NORMAL + && output_style != style) + diff_error ("conflicting specifications of output style", 0, 0); + output_style = style; +} + +static char const * +filetype (st) + struct stat const *st; +{ + /* See Posix.2 section 4.17.6.1.1 and Table 5-1 for these formats. + To keep diagnostics grammatical, the returned string must start + with a consonant. */ + + if (S_ISREG (st->st_mode)) + { + if (st->st_size == 0) + return "regular empty file"; + /* Posix.2 section 5.14.2 seems to suggest that we must read the file + and guess whether it's C, Fortran, etc., but this is somewhat useless + and doesn't reflect historical practice. We're allowed to guess + wrong, so we don't bother to read the file. */ + return "regular file"; + } + if (S_ISDIR (st->st_mode)) return "directory"; + + /* other Posix.1 file types */ +#ifdef S_ISBLK + if (S_ISBLK (st->st_mode)) return "block special file"; +#endif +#ifdef S_ISCHR + if (S_ISCHR (st->st_mode)) return "character special file"; +#endif +#ifdef S_ISFIFO + if (S_ISFIFO (st->st_mode)) return "fifo"; +#endif + + /* other Posix.1b file types */ +#ifdef S_TYPEISMQ + if (S_TYPEISMQ (st)) return "message queue"; +#endif +#ifdef S_TYPEISSEM + if (S_TYPEISSEM (st)) return "semaphore"; +#endif +#ifdef S_TYPEISSHM + if (S_TYPEISSHM (st)) return "shared memory object"; +#endif + + /* other popular file types */ + /* S_ISLNK is impossible with `fstat' and `stat'. */ +#ifdef S_ISSOCK + if (S_ISSOCK (st->st_mode)) return "socket"; +#endif + + return "weird file"; +} + +/* Compare two files (or dirs) with specified names + DIR0/NAME0 and DIR1/NAME1, at level DEPTH in directory recursion. + (if DIR0 is 0, then the name is just NAME0, etc.) + This is self-contained; it opens the files and closes them. + + Value is 0 if files are the same, 1 if different, + 2 if there is a problem opening them. */ + +static int +compare_files (dir0, name0, dir1, name1, depth) + char const *dir0, *dir1; + char const *name0, *name1; + int depth; +{ + struct file_data inf[2]; + register int i; + int val; + int same_files; + int failed = 0; + char *free0 = 0, *free1 = 0; + + /* If this is directory comparison, perhaps we have a file + that exists only in one of the directories. + If so, just print a message to that effect. */ + + if (! ((name0 != 0 && name1 != 0) + || (unidirectional_new_file_flag && name1 != 0) + || entire_new_file_flag)) + { + char const *name = name0 == 0 ? name1 : name0; + char const *dir = name0 == 0 ? dir1 : dir0; + message ("Only in %s: %s\n", dir, name); + /* Return 1 so that diff_dirs will return 1 ("some files differ"). */ + return 1; + } + + bzero (inf, sizeof (inf)); + + /* Mark any nonexistent file with -1 in the desc field. */ + /* Mark unopened files (e.g. directories) with -2. */ + + inf[0].desc = name0 == 0 ? -1 : -2; + inf[1].desc = name1 == 0 ? -1 : -2; + + /* Now record the full name of each file, including nonexistent ones. */ + + if (name0 == 0) + name0 = name1; + if (name1 == 0) + name1 = name0; + + inf[0].name = dir0 == 0 ? name0 : (free0 = dir_file_pathname (dir0, name0)); + inf[1].name = dir1 == 0 ? name1 : (free1 = dir_file_pathname (dir1, name1)); + + /* Stat the files. Record whether they are directories. */ + + for (i = 0; i <= 1; i++) + { + if (inf[i].desc != -1) + { + int stat_result; + + if (i && filename_cmp (inf[i].name, inf[0].name) == 0) + { + inf[i].stat = inf[0].stat; + stat_result = 0; + } + else if (strcmp (inf[i].name, "-") == 0) + { + inf[i].desc = STDIN_FILENO; + stat_result = fstat (STDIN_FILENO, &inf[i].stat); + if (stat_result == 0 && S_ISREG (inf[i].stat.st_mode)) + { + off_t pos = lseek (STDIN_FILENO, (off_t) 0, SEEK_CUR); + if (pos == -1) + stat_result = -1; + else + { + if (pos <= inf[i].stat.st_size) + inf[i].stat.st_size -= pos; + else + inf[i].stat.st_size = 0; + /* Posix.2 4.17.6.1.4 requires current time for stdin. */ + time (&inf[i].stat.st_mtime); + } + } + } + else + stat_result = stat (inf[i].name, &inf[i].stat); + + if (stat_result != 0) + { + perror_with_name (inf[i].name); + failed = 1; + } + else + { + inf[i].dir_p = S_ISDIR (inf[i].stat.st_mode) && inf[i].desc != 0; + if (inf[1 - i].desc == -1) + { + inf[1 - i].dir_p = inf[i].dir_p; + inf[1 - i].stat.st_mode = inf[i].stat.st_mode; + } + } + } + } + + if (! failed && depth == 0 && inf[0].dir_p != inf[1].dir_p) + { + /* If one is a directory, and it was specified in the command line, + use the file in that dir with the other file's basename. */ + + int fnm_arg = inf[0].dir_p; + int dir_arg = 1 - fnm_arg; + char const *fnm = inf[fnm_arg].name; + char const *dir = inf[dir_arg].name; + char const *p = filename_lastdirchar (fnm); + char const *filename = inf[dir_arg].name + = dir_file_pathname (dir, p ? p + 1 : fnm); + + if (strcmp (fnm, "-") == 0) + fatal ("can't compare - to a directory"); + + if (stat (filename, &inf[dir_arg].stat) != 0) + { + perror_with_name (filename); + failed = 1; + } + else + inf[dir_arg].dir_p = S_ISDIR (inf[dir_arg].stat.st_mode); + } + + if (failed) + { + + /* If either file should exist but does not, return 2. */ + + val = 2; + + } + else if ((same_files = inf[0].desc != -1 && inf[1].desc != -1 + && 0 < same_file (&inf[0].stat, &inf[1].stat)) + && no_diff_means_no_output) + { + /* The two named files are actually the same physical file. + We know they are identical without actually reading them. */ + + val = 0; + } + else if (inf[0].dir_p & inf[1].dir_p) + { + if (output_style == OUTPUT_IFDEF) + fatal ("-D option not supported with directories"); + + /* If both are directories, compare the files in them. */ + + if (depth > 0 && !recursive) + { + /* But don't compare dir contents one level down + unless -r was specified. */ + message ("Common subdirectories: %s and %s\n", + inf[0].name, inf[1].name); + val = 0; + } + else + { + val = diff_dirs (inf, compare_files, depth); + } + + } + else if ((inf[0].dir_p | inf[1].dir_p) + || (depth > 0 + && (! S_ISREG (inf[0].stat.st_mode) + || ! S_ISREG (inf[1].stat.st_mode)))) + { + /* Perhaps we have a subdirectory that exists only in one directory. + If so, just print a message to that effect. */ + + if (inf[0].desc == -1 || inf[1].desc == -1) + { + if ((inf[0].dir_p | inf[1].dir_p) + && recursive + && (entire_new_file_flag + || (unidirectional_new_file_flag && inf[0].desc == -1))) + val = diff_dirs (inf, compare_files, depth); + else + { + char const *dir = (inf[0].desc == -1) ? dir1 : dir0; + /* See Posix.2 section 4.17.6.1.1 for this format. */ + message ("Only in %s: %s\n", dir, name0); + val = 1; + } + } + else + { + /* We have two files that are not to be compared. */ + + /* See Posix.2 section 4.17.6.1.1 for this format. */ + message5 ("File %s is a %s while file %s is a %s\n", + inf[0].name, filetype (&inf[0].stat), + inf[1].name, filetype (&inf[1].stat)); + + /* This is a difference. */ + val = 1; + } + } + else if ((no_details_flag & ~ignore_some_changes) + && inf[0].stat.st_size != inf[1].stat.st_size + && (inf[0].desc == -1 || S_ISREG (inf[0].stat.st_mode)) + && (inf[1].desc == -1 || S_ISREG (inf[1].stat.st_mode))) + { + message ("Files %s and %s differ\n", inf[0].name, inf[1].name); + val = 1; + } + else + { + /* Both exist and neither is a directory. */ + + /* Open the files and record their descriptors. */ + + if (inf[0].desc == -2) + if ((inf[0].desc = open (inf[0].name, O_RDONLY, 0)) < 0) + { + perror_with_name (inf[0].name); + failed = 1; + } + if (inf[1].desc == -2) + if (same_files) + inf[1].desc = inf[0].desc; + else if ((inf[1].desc = open (inf[1].name, O_RDONLY, 0)) < 0) + { + perror_with_name (inf[1].name); + failed = 1; + } + +#if HAVE_SETMODE + if (binary_I_O) + for (i = 0; i <= 1; i++) + if (0 <= inf[i].desc) + setmode (inf[i].desc, O_BINARY); +#endif + + /* Compare the files, if no error was found. */ + + val = failed ? 2 : diff_2_files (inf, depth); + + /* Close the file descriptors. */ + + if (inf[0].desc >= 0 && close (inf[0].desc) != 0) + { + perror_with_name (inf[0].name); + val = 2; + } + if (inf[1].desc >= 0 && inf[0].desc != inf[1].desc + && close (inf[1].desc) != 0) + { + perror_with_name (inf[1].name); + val = 2; + } + } + + /* Now the comparison has been done, if no error prevented it, + and VAL is the value this function will return. */ + + if (val == 0 && !inf[0].dir_p) + { + if (print_file_same_flag) + message ("Files %s and %s are identical\n", + inf[0].name, inf[1].name); + } + else + fflush (outfile); + + if (free0) + free (free0); + if (free1) + free (free1); + + return val; +} + +/* Initialize status variables and flag variables used in libdiff, + to permit repeated calls to diff_run. */ + +static void +initialize_main (argcp, argvp) + int *argcp; + char ***argvp; +{ + /* These variables really must be reset each time diff_run is called. */ + output_style = OUTPUT_NORMAL; + context = -1; + file_label[0] = NULL; + file_label[1] = NULL; + diff_program_name = (*argvp)[0]; + outfile = NULL; + + /* Reset these also, just for safety's sake. (If one invocation turns + on ignore_case_flag, it must be turned off before diff_run is called + again. But it is possible to make many diffs before encountering + such a problem. */ + recursive = 0; + no_discards = 0; +#if HAVE_SETMODE + binary_I_O = 0; +#endif + no_diff_means_no_output = 0; + always_text_flag = 0; + horizon_lines = 0; + ignore_space_change_flag = 0; + ignore_all_space_flag = 0; + ignore_blank_lines_flag = 0; + ignore_some_line_changes = 0; + ignore_some_changes = 0; + ignore_case_flag = 0; + function_regexp_list = NULL; + ignore_regexp_list = NULL; + no_details_flag = 0; + print_file_same_flag = 0; + tab_align_flag = 0; + tab_expand_flag = 0; + dir_start_file = NULL; + entire_new_file_flag = 0; + unidirectional_new_file_flag = 0; + paginate_flag = 0; + bzero (group_format, sizeof (group_format)); + bzero (line_format, sizeof (line_format)); + sdiff_help_sdiff = 0; + sdiff_left_only = 0; + sdiff_skip_common_lines = 0; + sdiff_half_width = 0; + sdiff_column2_offset = 0; + switch_string = NULL; + heuristic = 0; + bzero (files, sizeof (files)); +} diff --git a/contrib/cvs/diff/diff.h b/contrib/cvs/diff/diff.h new file mode 100644 index 0000000..fba26a7 --- /dev/null +++ b/contrib/cvs/diff/diff.h @@ -0,0 +1,345 @@ +/* Shared definitions for GNU DIFF + Copyright (C) 1988, 89, 91, 92, 93, 97 Free Software Foundation, Inc. + +This file is part of GNU DIFF. + +GNU DIFF is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +GNU DIFF is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU DIFF; see the file COPYING. If not, write to +the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ + +#include "system.h" +#include <stdio.h> +#include <setjmp.h> +#include "regex.h" + +#define TAB_WIDTH 8 + +/* Variables for command line options */ + +#ifndef GDIFF_MAIN +#define EXTERN extern +#else +#define EXTERN +#endif + +enum output_style { + /* Default output style. */ + OUTPUT_NORMAL, + /* Output the differences with lines of context before and after (-c). */ + OUTPUT_CONTEXT, + /* Output the differences in a unified context diff format (-u). */ + OUTPUT_UNIFIED, + /* Output the differences as commands suitable for `ed' (-e). */ + OUTPUT_ED, + /* Output the diff as a forward ed script (-f). */ + OUTPUT_FORWARD_ED, + /* Like -f, but output a count of changed lines in each "command" (-n). */ + OUTPUT_RCS, + /* Output merged #ifdef'd file (-D). */ + OUTPUT_IFDEF, + /* Output sdiff style (-y). */ + OUTPUT_SDIFF +}; + +/* True for output styles that are robust, + i.e. can handle a file that ends in a non-newline. */ +#define ROBUST_OUTPUT_STYLE(S) ((S) != OUTPUT_ED && (S) != OUTPUT_FORWARD_ED) + +EXTERN enum output_style output_style; + +/* Nonzero if output cannot be generated for identical files. */ +EXTERN int no_diff_means_no_output; + +/* Number of lines of context to show in each set of diffs. + This is zero when context is not to be shown. */ +EXTERN int context; + +/* Consider all files as text files (-a). + Don't interpret codes over 0177 as implying a "binary file". */ +EXTERN int always_text_flag; + +/* Number of lines to keep in identical prefix and suffix. */ +EXTERN int horizon_lines; + +/* Ignore changes in horizontal white space (-b). */ +EXTERN int ignore_space_change_flag; + +/* Ignore all horizontal white space (-w). */ +EXTERN int ignore_all_space_flag; + +/* Ignore changes that affect only blank lines (-B). */ +EXTERN int ignore_blank_lines_flag; + +/* 1 if lines may match even if their contents do not match exactly. + This depends on various options. */ +EXTERN int ignore_some_line_changes; + +/* 1 if files may match even if their contents are not byte-for-byte identical. + This depends on various options. */ +EXTERN int ignore_some_changes; + +/* Ignore differences in case of letters (-i). */ +EXTERN int ignore_case_flag; + +/* File labels for `-c' output headers (-L). */ +EXTERN char *file_label[2]; + +struct regexp_list +{ + struct re_pattern_buffer buf; + struct regexp_list *next; +}; + +/* Regexp to identify function-header lines (-F). */ +EXTERN struct regexp_list *function_regexp_list; + +/* Ignore changes that affect only lines matching this regexp (-I). */ +EXTERN struct regexp_list *ignore_regexp_list; + +/* Say only whether files differ, not how (-q). */ +EXTERN int no_details_flag; + +/* Report files compared that match (-s). + Normally nothing is output when that happens. */ +EXTERN int print_file_same_flag; + +/* Output the differences with exactly 8 columns added to each line + so that any tabs in the text line up properly (-T). */ +EXTERN int tab_align_flag; + +/* Expand tabs in the output so the text lines up properly + despite the characters added to the front of each line (-t). */ +EXTERN int tab_expand_flag; + +/* In directory comparison, specify file to start with (-S). + All file names less than this name are ignored. */ +EXTERN char *dir_start_file; + +/* If a file is new (appears in only one dir) + include its entire contents (-N). + Then `patch' would create the file with appropriate contents. */ +EXTERN int entire_new_file_flag; + +/* If a file is new (appears in only the second dir) + include its entire contents (-P). + Then `patch' would create the file with appropriate contents. */ +EXTERN int unidirectional_new_file_flag; + +/* Pipe each file's output through pr (-l). */ +EXTERN int paginate_flag; + +enum line_class { + /* Lines taken from just the first file. */ + OLD, + /* Lines taken from just the second file. */ + NEW, + /* Lines common to both files. */ + UNCHANGED, + /* A hunk containing both old and new lines (line groups only). */ + CHANGED +}; + +/* Line group formats for old, new, unchanged, and changed groups. */ +EXTERN char *group_format[CHANGED + 1]; + +/* Line formats for old, new, and unchanged lines. */ +EXTERN char *line_format[UNCHANGED + 1]; + +/* If using OUTPUT_SDIFF print extra information to help the sdiff filter. */ +EXTERN int sdiff_help_sdiff; + +/* Tell OUTPUT_SDIFF to show only the left version of common lines. */ +EXTERN int sdiff_left_only; + +/* Tell OUTPUT_SDIFF to not show common lines. */ +EXTERN int sdiff_skip_common_lines; + +/* The half line width and column 2 offset for OUTPUT_SDIFF. */ +EXTERN unsigned sdiff_half_width; +EXTERN unsigned sdiff_column2_offset; + +/* String containing all the command options diff received, + with spaces between and at the beginning but none at the end. + If there were no options given, this string is empty. */ +EXTERN char * switch_string; + +/* Nonzero means use heuristics for better speed. */ +EXTERN int heuristic; + +/* Name of program the user invoked (for error messages). */ +EXTERN char *diff_program_name; + +/* Jump buffer for nonlocal exits. */ +EXTERN jmp_buf diff_abort_buf; +#define DIFF_ABORT(retval) longjmp(diff_abort_buf, retval) + +/* The result of comparison is an "edit script": a chain of `struct change'. + Each `struct change' represents one place where some lines are deleted + and some are inserted. + + LINE0 and LINE1 are the first affected lines in the two files (origin 0). + DELETED is the number of lines deleted here from file 0. + INSERTED is the number of lines inserted here in file 1. + + If DELETED is 0 then LINE0 is the number of the line before + which the insertion was done; vice versa for INSERTED and LINE1. */ + +struct change +{ + struct change *link; /* Previous or next edit command */ + int inserted; /* # lines of file 1 changed here. */ + int deleted; /* # lines of file 0 changed here. */ + int line0; /* Line number of 1st deleted line. */ + int line1; /* Line number of 1st inserted line. */ + char ignore; /* Flag used in context.c */ +}; + +/* Structures that describe the input files. */ + +/* Data on one input file being compared. */ + +struct file_data { + int desc; /* File descriptor */ + char const *name; /* File name */ + struct stat stat; /* File status from fstat() */ + int dir_p; /* nonzero if file is a directory */ + + /* Buffer in which text of file is read. */ + char * buffer; + /* Allocated size of buffer. */ + size_t bufsize; + /* Number of valid characters now in the buffer. */ + size_t buffered_chars; + + /* Array of pointers to lines in the file. */ + char const **linbuf; + + /* linbuf_base <= buffered_lines <= valid_lines <= alloc_lines. + linebuf[linbuf_base ... buffered_lines - 1] are possibly differing. + linebuf[linbuf_base ... valid_lines - 1] contain valid data. + linebuf[linbuf_base ... alloc_lines - 1] are allocated. */ + int linbuf_base, buffered_lines, valid_lines, alloc_lines; + + /* Pointer to end of prefix of this file to ignore when hashing. */ + char const *prefix_end; + + /* Count of lines in the prefix. + There are this many lines in the file before linbuf[0]. */ + int prefix_lines; + + /* Pointer to start of suffix of this file to ignore when hashing. */ + char const *suffix_begin; + + /* Vector, indexed by line number, containing an equivalence code for + each line. It is this vector that is actually compared with that + of another file to generate differences. */ + int *equivs; + + /* Vector, like the previous one except that + the elements for discarded lines have been squeezed out. */ + int *undiscarded; + + /* Vector mapping virtual line numbers (not counting discarded lines) + to real ones (counting those lines). Both are origin-0. */ + int *realindexes; + + /* Total number of nondiscarded lines. */ + int nondiscarded_lines; + + /* Vector, indexed by real origin-0 line number, + containing 1 for a line that is an insertion or a deletion. + The results of comparison are stored here. */ + char *changed_flag; + + /* 1 if file ends in a line with no final newline. */ + int missing_newline; + + /* 1 more than the maximum equivalence value used for this or its + sibling file. */ + int equiv_max; +}; + +/* Describe the two files currently being compared. */ + +EXTERN struct file_data files[2]; + +/* Stdio stream to output diffs to. */ + +EXTERN FILE *outfile; + +/* Declare various functions. */ + +/* analyze.c */ +int diff_2_files PARAMS((struct file_data[], int)); + +/* context.c */ +void print_context_header PARAMS((struct file_data[], int)); +void print_context_script PARAMS((struct change *, int)); + +/* diff.c */ +int excluded_filename PARAMS((char const *)); + +/* dir.c */ +int diff_dirs PARAMS((struct file_data const[], int (*) PARAMS((char const *, char const *, char const *, char const *, int)), int)); + +/* ed.c */ +void print_ed_script PARAMS((struct change *)); +void pr_forward_ed_script PARAMS((struct change *)); + +/* ifdef.c */ +void print_ifdef_script PARAMS((struct change *)); + +/* io.c */ +int read_files PARAMS((struct file_data[], int)); +int sip PARAMS((struct file_data *, int)); +void slurp PARAMS((struct file_data *)); + +/* normal.c */ +void print_normal_script PARAMS((struct change *)); + +/* rcs.c */ +void print_rcs_script PARAMS((struct change *)); + +/* side.c */ +void print_sdiff_script PARAMS((struct change *)); + +/* util.c */ +VOID *xmalloc PARAMS((size_t)); +VOID *xrealloc PARAMS((VOID *, size_t)); +char *concat PARAMS((char const *, char const *, char const *)); +char *dir_file_pathname PARAMS((char const *, char const *)); +int change_letter PARAMS((int, int)); +int line_cmp PARAMS((char const *, char const *)); +int translate_line_number PARAMS((struct file_data const *, int)); +struct change *find_change PARAMS((struct change *)); +struct change *find_reverse_change PARAMS((struct change *)); +void analyze_hunk PARAMS((struct change *, int *, int *, int *, int *, int *, int *)); +void begin_output PARAMS((void)); +void debug_script PARAMS((struct change *)); +void diff_error PARAMS((char const *, char const *, char const *)); +void fatal PARAMS((char const *)); +void finish_output PARAMS((void)); +void message PARAMS((char const *, char const *, char const *)); +void message5 PARAMS((char const *, char const *, char const *, char const *, char const *)); +void output_1_line PARAMS((char const *, char const *, char const *, char const *)); +void perror_with_name PARAMS((char const *)); +void pfatal_with_name PARAMS((char const *)); +void print_1_line PARAMS((char const *, char const * const *)); +void print_message_queue PARAMS((void)); +void print_number_range PARAMS((int, struct file_data *, int, int)); +void print_script PARAMS((struct change *, struct change * (*) PARAMS((struct change *)), void (*) PARAMS((struct change *)))); +void setup_output PARAMS((char const *, char const *, int)); +void translate_range PARAMS((struct file_data const *, int, int, int *, int *)); + +/* version.c */ +extern char const diff_version_string[]; diff --git a/contrib/cvs/diff/diff3.c b/contrib/cvs/diff/diff3.c new file mode 100644 index 0000000..533214c --- /dev/null +++ b/contrib/cvs/diff/diff3.c @@ -0,0 +1,1809 @@ +/* Three way file comparison program (diff3) for Project GNU. + Copyright (C) 1988, 1989, 1992, 1993, 1994, 1997 Free Software Foundation, Inc. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2, or (at your option) + any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ + +/* Written by Randy Smith */ +/* Librarification by Tim Pierce */ + +#include "system.h" +#include <stdio.h> +#include <setjmp.h> +#include "getopt.h" + +/* diff3.c has a real initialize_main function. */ +#ifdef initialize_main +#undef initialize_main +#endif + +extern char const diff_version_string[]; + +/* + * Internal data structures and macros for the diff3 program; includes + * data structures for both diff3 diffs and normal diffs. + */ + +/* Different files within a three way diff. */ +#define FILE0 0 +#define FILE1 1 +#define FILE2 2 + +/* + * A three way diff is built from two two-way diffs; the file which + * the two two-way diffs share is: + */ +#define FILEC FILE2 + +/* + * Different files within a two way diff. + * FC is the common file, FO the other file. + */ +#define FO 0 +#define FC 1 + +/* The ranges are indexed by */ +#define START 0 +#define END 1 + +enum diff_type { + ERROR, /* Should not be used */ + ADD, /* Two way diff add */ + CHANGE, /* Two way diff change */ + DELETE, /* Two way diff delete */ + DIFF_ALL, /* All three are different */ + DIFF_1ST, /* Only the first is different */ + DIFF_2ND, /* Only the second */ + DIFF_3RD /* Only the third */ +}; + +/* Two way diff */ +struct diff_block { + int ranges[2][2]; /* Ranges are inclusive */ + char **lines[2]; /* The actual lines (may contain nulls) */ + size_t *lengths[2]; /* Line lengths (including newlines, if any) */ + struct diff_block *next; +}; + +/* Three way diff */ + +struct diff3_block { + enum diff_type correspond; /* Type of diff */ + int ranges[3][2]; /* Ranges are inclusive */ + char **lines[3]; /* The actual lines (may contain nulls) */ + size_t *lengths[3]; /* Line lengths (including newlines, if any) */ + struct diff3_block *next; +}; + +/* + * Access the ranges on a diff block. + */ +#define D_LOWLINE(diff, filenum) \ + ((diff)->ranges[filenum][START]) +#define D_HIGHLINE(diff, filenum) \ + ((diff)->ranges[filenum][END]) +#define D_NUMLINES(diff, filenum) \ + (D_HIGHLINE (diff, filenum) - D_LOWLINE (diff, filenum) + 1) + +/* + * Access the line numbers in a file in a diff by relative line + * numbers (i.e. line number within the diff itself). Note that these + * are lvalues and can be used for assignment. + */ +#define D_RELNUM(diff, filenum, linenum) \ + ((diff)->lines[filenum][linenum]) +#define D_RELLEN(diff, filenum, linenum) \ + ((diff)->lengths[filenum][linenum]) + +/* + * And get at them directly, when that should be necessary. + */ +#define D_LINEARRAY(diff, filenum) \ + ((diff)->lines[filenum]) +#define D_LENARRAY(diff, filenum) \ + ((diff)->lengths[filenum]) + +/* + * Next block. + */ +#define D_NEXT(diff) ((diff)->next) + +/* + * Access the type of a diff3 block. + */ +#define D3_TYPE(diff) ((diff)->correspond) + +/* + * Line mappings based on diffs. The first maps off the top of the + * diff, the second off of the bottom. + */ +#define D_HIGH_MAPLINE(diff, fromfile, tofile, lineno) \ + ((lineno) \ + - D_HIGHLINE ((diff), (fromfile)) \ + + D_HIGHLINE ((diff), (tofile))) + +#define D_LOW_MAPLINE(diff, fromfile, tofile, lineno) \ + ((lineno) \ + - D_LOWLINE ((diff), (fromfile)) \ + + D_LOWLINE ((diff), (tofile))) + +/* + * General memory allocation function. + */ +#define ALLOCATE(number, type) \ + (type *) xmalloc ((number) * sizeof (type)) + +/* Options variables for flags set on command line. */ + +/* If nonzero, treat all files as text files, never as binary. */ +static int always_text; + +/* If nonzero, write out an ed script instead of the standard diff3 format. */ +static int edscript; + +/* If nonzero, in the case of overlapping diffs (type DIFF_ALL), + preserve the lines which would normally be deleted from + file 1 with a special flagging mechanism. */ +static int flagging; + +/* Number of lines to keep in identical prefix and suffix. */ +static int horizon_lines = 10; + +/* Use a tab to align output lines (-T). */ +static int tab_align_flag; + +/* If nonzero, do not output information for overlapping diffs. */ +static int simple_only; + +/* If nonzero, do not output information for non-overlapping diffs. */ +static int overlap_only; + +/* If nonzero, show information for DIFF_2ND diffs. */ +static int show_2nd; + +/* If nonzero, include `:wq' at the end of the script + to write out the file being edited. */ +static int finalwrite; + +/* If nonzero, output a merged file. */ +static int merge; + +extern char *diff_program_name; + +static char *read_diff PARAMS((char const *, char const *, char **)); +static char *scan_diff_line PARAMS((char *, char **, size_t *, char *, int)); +static enum diff_type process_diff_control PARAMS((char **, struct diff_block *)); +static int compare_line_list PARAMS((char * const[], size_t const[], char * const[], size_t const[], int)); +static int copy_stringlist PARAMS((char * const[], size_t const[], char *[], size_t[], int)); +static int dotlines PARAMS((FILE *, struct diff3_block *, int)); +static int output_diff3_edscript PARAMS((FILE *, struct diff3_block *, int const[3], int const[3], char const *, char const *, char const *)); +static int output_diff3_merge PARAMS((FILE *, FILE *, struct diff3_block *, int const[3], int const[3], char const *, char const *, char const *)); +static size_t myread PARAMS((int, char *, size_t)); +static struct diff3_block *create_diff3_block PARAMS((int, int, int, int, int, int)); +static struct diff3_block *make_3way_diff PARAMS((struct diff_block *, struct diff_block *)); +static struct diff3_block *reverse_diff3_blocklist PARAMS((struct diff3_block *)); +static struct diff3_block *using_to_diff3_block PARAMS((struct diff_block *[2], struct diff_block *[2], int, int, struct diff3_block const *)); +static struct diff_block *process_diff PARAMS((char const *, char const *, struct diff_block **, char **)); +static void check_output PARAMS((FILE *)); +static void diff3_fatal PARAMS((char const *)); +static void output_diff3 PARAMS((FILE *, struct diff3_block *, int const[3], int const[3])); +static void diff3_perror_with_exit PARAMS((char const *)); +static int try_help PARAMS((char const *)); +static void undotlines PARAMS((FILE *, int, int, int)); +static void usage PARAMS((void)); +static void initialize_main PARAMS((int *, char ***)); +static void free_diff_blocks PARAMS((struct diff_block *)); +static void free_diff3_blocks PARAMS((struct diff3_block *)); + +/* Functions provided in libdiff.a or other external sources. */ +int diff_run PARAMS((int, char **, char *)); +VOID *xmalloc PARAMS((size_t)); +VOID *xrealloc PARAMS((VOID *, size_t)); +void perror_with_name PARAMS((char const *)); +void diff_error PARAMS((char const *, char const *, char const *)); + +/* Permit non-local exits from diff3. */ +static jmp_buf diff3_abort_buf; +#define DIFF3_ABORT(retval) longjmp(diff3_abort_buf, retval) + +static struct option const longopts[] = +{ + {"text", 0, 0, 'a'}, + {"show-all", 0, 0, 'A'}, + {"ed", 0, 0, 'e'}, + {"show-overlap", 0, 0, 'E'}, + {"label", 1, 0, 'L'}, + {"merge", 0, 0, 'm'}, + {"initial-tab", 0, 0, 'T'}, + {"overlap-only", 0, 0, 'x'}, + {"easy-only", 0, 0, '3'}, + {"version", 0, 0, 'v'}, + {"help", 0, 0, 129}, + {0, 0, 0, 0} +}; + +/* + * Main program. Calls diff twice on two pairs of input files, + * combines the two diffs, and outputs them. + */ +int +diff3_run (argc, argv, outfile) + int argc; + char **argv; + char *outfile; +{ + int c, i; + int mapping[3]; + int rev_mapping[3]; + int incompat = 0; + int conflicts_found; + int status; + struct diff_block *thread0, *thread1, *last_block; + char *content0, *content1; + struct diff3_block *diff3; + int tag_count = 0; + char *tag_strings[3]; + char *commonname; + char **file; + struct stat statb; + int optind_old; + FILE *outstream; + + initialize_main (&argc, &argv); + + optind_old = optind; + optind = 0; + while ((c = getopt_long (argc, argv, "aeimvx3AEL:TX", longopts, 0)) != EOF) + { + switch (c) + { + case 'a': + always_text = 1; + break; + case 'A': + show_2nd = 1; + flagging = 1; + incompat++; + break; + case 'x': + overlap_only = 1; + incompat++; + break; + case '3': + simple_only = 1; + incompat++; + break; + case 'i': + finalwrite = 1; + break; + case 'm': + merge = 1; + break; + case 'X': + overlap_only = 1; + /* Falls through */ + case 'E': + flagging = 1; + /* Falls through */ + case 'e': + incompat++; + break; + case 'T': + tab_align_flag = 1; + break; + case 'v': + printf ("diff3 - GNU diffutils version %s\n", diff_version_string); + return 0; + case 129: + usage (); + check_output (stdout); + return 0; + case 'L': + /* Handle up to three -L options. */ + if (tag_count < 3) + { + tag_strings[tag_count++] = optarg; + break; + } + return try_help ("Too many labels were given. The limit is 3."); + default: + return try_help (0); + } + } + + edscript = incompat & ~merge; /* -AeExX3 without -m implies ed script. */ + show_2nd |= ~incompat & merge; /* -m without -AeExX3 implies -A. */ + flagging |= ~incompat & merge; + + if (incompat > 1 /* Ensure at most one of -AeExX3. */ + || finalwrite & merge /* -i -m would rewrite input file. */ + || (tag_count && ! flagging)) /* -L requires one of -AEX. */ + return try_help ("incompatible options"); + + if (argc - optind != 3) + return try_help (argc - optind < 3 ? "missing operand" : "extra operand"); + + file = &argv[optind]; + + optind = optind_old; + + for (i = tag_count; i < 3; i++) + tag_strings[i] = file[i]; + + /* Always compare file1 to file2, even if file2 is "-". + This is needed for -mAeExX3. Using the file0 as + the common file would produce wrong results, because if the + file0-file1 diffs didn't line up with the file0-file2 diffs + (which is entirely possible since we don't use diff's -n option), + diff3 might report phantom changes from file1 to file2. */ + + if (strcmp (file[2], "-") == 0) + { + /* Sigh. We've got standard input as the last arg. We can't + call diff twice on stdin. Use the middle arg as the common + file instead. */ + if (strcmp (file[0], "-") == 0 || strcmp (file[1], "-") == 0) + { + diff_error ("%s", "`-' specified for more than one input file", 0); + return 2; + } + mapping[0] = 0; + mapping[1] = 2; + mapping[2] = 1; + } + else + { + /* Normal, what you'd expect */ + mapping[0] = 0; + mapping[1] = 1; + mapping[2] = 2; + } + + for (i = 0; i < 3; i++) + rev_mapping[mapping[i]] = i; + + for (i = 0; i < 3; i++) + if (strcmp (file[i], "-") != 0) + { + if (stat (file[i], &statb) < 0) + { + perror_with_name (file[i]); + return 2; + } + else if (S_ISDIR(statb.st_mode)) + { + fprintf (stderr, "%s: %s: Is a directory\n", + diff_program_name, file[i]); + return 2; + } + } + + if (outfile == NULL) + outstream = stdout; + else + { + outstream = fopen (outfile, "w"); + if (outstream == NULL) + { + perror_with_name ("could not open output file"); + return 2; + } + } + + /* Set the jump buffer, so that diff may abort execution without + terminating the process. */ + status = setjmp (diff3_abort_buf); + if (status != 0) + return status; + + commonname = file[rev_mapping[FILEC]]; + thread1 = process_diff (file[rev_mapping[FILE1]], commonname, &last_block, + &content1); + if (thread1) + for (i = 0; i < 2; i++) + { + horizon_lines = max (horizon_lines, D_NUMLINES (thread1, i)); + horizon_lines = max (horizon_lines, D_NUMLINES (last_block, i)); + } + thread0 = process_diff (file[rev_mapping[FILE0]], commonname, &last_block, + &content0); + diff3 = make_3way_diff (thread0, thread1); + if (edscript) + conflicts_found + = output_diff3_edscript (outstream, diff3, mapping, rev_mapping, + tag_strings[0], tag_strings[1], tag_strings[2]); + else if (merge) + { + if (! freopen (file[rev_mapping[FILE0]], "r", stdin)) + diff3_perror_with_exit (file[rev_mapping[FILE0]]); + conflicts_found + = output_diff3_merge (stdin, outstream, diff3, mapping, rev_mapping, + tag_strings[0], tag_strings[1], tag_strings[2]); + if (ferror (stdin)) + diff3_fatal ("read error"); + } + else + { + output_diff3 (outstream, diff3, mapping, rev_mapping); + conflicts_found = 0; + } + + free(content0); + free(content1); + free_diff_blocks(thread0); + free_diff_blocks(thread1); + free_diff3_blocks(diff3); + + check_output (outstream); + if (outstream != stdout) + if (fclose (outstream) != 0) + perror ("close error on output file"); + return conflicts_found; +} + +static int +try_help (reason) + char const *reason; +{ + if (reason) + fprintf (stderr, "%s: %s\n", diff_program_name, reason); + fprintf (stderr, "%s: Try `%s --help' for more information.\n", + diff_program_name, diff_program_name); + return 2; +} + +static void +check_output (stream) + FILE *stream; +{ + if (ferror (stream) || fflush (stream) != 0) + diff3_fatal ("write error"); +} + +/* + * Explain, patiently and kindly, how to use this program. + */ +static void +usage () +{ + printf ("Usage: %s [OPTION]... MYFILE OLDFILE YOURFILE\n\n", diff_program_name); + + printf ("%s", "\ + -e --ed Output unmerged changes from OLDFILE to YOURFILE into MYFILE.\n\ + -E --show-overlap Output unmerged changes, bracketing conflicts.\n\ + -A --show-all Output all changes, bracketing conflicts.\n\ + -x --overlap-only Output overlapping changes.\n\ + -X Output overlapping changes, bracketing them.\n\ + -3 --easy-only Output unmerged nonoverlapping changes.\n\n"); + printf ("%s", "\ + -m --merge Output merged file instead of ed script (default -A).\n\ + -L LABEL --label=LABEL Use LABEL instead of file name.\n\ + -i Append `w' and `q' commands to ed scripts.\n\ + -a --text Treat all files as text.\n\ + -T --initial-tab Make tabs line up by prepending a tab.\n\n"); + printf ("%s", "\ + -v --version Output version info.\n\ + --help Output this help.\n\n"); + printf ("If a FILE is `-', read standard input.\n"); +} + +/* + * Routines that combine the two diffs together into one. The + * algorithm used follows: + * + * File2 is shared in common between the two diffs. + * Diff02 is the diff between 0 and 2. + * Diff12 is the diff between 1 and 2. + * + * 1) Find the range for the first block in File2. + * a) Take the lowest of the two ranges (in File2) in the two + * current blocks (one from each diff) as being the low + * water mark. Assign the upper end of this block as + * being the high water mark and move the current block up + * one. Mark the block just moved over as to be used. + * b) Check the next block in the diff that the high water + * mark is *not* from. + * + * *If* the high water mark is above + * the low end of the range in that block, + * + * mark that block as to be used and move the current + * block up. Set the high water mark to the max of + * the high end of this block and the current. Repeat b. + * + * 2) Find the corresponding ranges in File0 (from the blocks + * in diff02; line per line outside of diffs) and in File1. + * Create a diff3_block, reserving space as indicated by the ranges. + * + * 3) Copy all of the pointers for file2 in. At least for now, + * do memcmp's between corresponding strings in the two diffs. + * + * 4) Copy all of the pointers for file0 and 1 in. Get what you + * need from file2 (when there isn't a diff block, it's + * identical to file2 within the range between diff blocks). + * + * 5) If the diff blocks you used came from only one of the two + * strings of diffs, then that file (i.e. the one other than + * the common file in that diff) is the odd person out. If you used + * diff blocks from both sets, check to see if files 0 and 1 match: + * + * Same number of lines? If so, do a set of memcmp's (if a + * memcmp matches; copy the pointer over; it'll be easier later + * if you have to do any compares). If they match, 0 & 1 are + * the same. If not, all three different. + * + * Then you do it again, until you run out of blocks. + * + */ + +/* + * This routine makes a three way diff (chain of diff3_block's) from two + * two way diffs (chains of diff_block's). It is assumed that each of + * the two diffs passed are onto the same file (i.e. that each of the + * diffs were made "to" the same file). The three way diff pointer + * returned will have numbering FILE0--the other file in diff02, + * FILE1--the other file in diff12, and FILEC--the common file. + */ +static struct diff3_block * +make_3way_diff (thread0, thread1) + struct diff_block *thread0, *thread1; +{ +/* + * This routine works on the two diffs passed to it as threads. + * Thread number 0 is diff02, thread number 1 is diff12. The USING + * array is set to the base of the list of blocks to be used to + * construct each block of the three way diff; if no blocks from a + * particular thread are to be used, that element of the using array + * is set to 0. The elements LAST_USING array are set to the last + * elements on each of the using lists. + * + * The HIGH_WATER_MARK is set to the highest line number in the common file + * described in any of the diffs in either of the USING lists. The + * HIGH_WATER_THREAD names the thread. Similarly the BASE_WATER_MARK + * and BASE_WATER_THREAD describe the lowest line number in the common file + * described in any of the diffs in either of the USING lists. The + * HIGH_WATER_DIFF is the diff from which the HIGH_WATER_MARK was + * taken. + * + * The HIGH_WATER_DIFF should always be equal to LAST_USING + * [HIGH_WATER_THREAD]. The OTHER_DIFF is the next diff to check for + * higher water, and should always be equal to + * CURRENT[HIGH_WATER_THREAD ^ 0x1]. The OTHER_THREAD is the thread + * in which the OTHER_DIFF is, and hence should always be equal to + * HIGH_WATER_THREAD ^ 0x1. + * + * The variable LAST_DIFF is kept set to the last diff block produced + * by this routine, for line correspondence purposes between that diff + * and the one currently being worked on. It is initialized to + * ZERO_DIFF before any blocks have been created. + */ + + struct diff_block + *using[2], + *last_using[2], + *current[2]; + + int + high_water_mark; + + int + high_water_thread, + base_water_thread, + other_thread; + + struct diff_block + *high_water_diff, + *other_diff; + + struct diff3_block + *result, + *tmpblock, + **result_end; + + struct diff3_block const *last_diff3; + + static struct diff3_block const zero_diff3; + + /* Initialization */ + result = 0; + result_end = &result; + current[0] = thread0; current[1] = thread1; + last_diff3 = &zero_diff3; + + /* Sniff up the threads until we reach the end */ + + while (current[0] || current[1]) + { + using[0] = using[1] = last_using[0] = last_using[1] = 0; + + /* Setup low and high water threads, diffs, and marks. */ + if (!current[0]) + base_water_thread = 1; + else if (!current[1]) + base_water_thread = 0; + else + base_water_thread = + (D_LOWLINE (current[0], FC) > D_LOWLINE (current[1], FC)); + + high_water_thread = base_water_thread; + + high_water_diff = current[high_water_thread]; + +#if 0 + /* low and high waters start off same diff */ + base_water_mark = D_LOWLINE (high_water_diff, FC); +#endif + + high_water_mark = D_HIGHLINE (high_water_diff, FC); + + /* Make the diff you just got info from into the using class */ + using[high_water_thread] + = last_using[high_water_thread] + = high_water_diff; + current[high_water_thread] = high_water_diff->next; + last_using[high_water_thread]->next = 0; + + /* And mark the other diff */ + other_thread = high_water_thread ^ 0x1; + other_diff = current[other_thread]; + + /* Shuffle up the ladder, checking the other diff to see if it + needs to be incorporated. */ + while (other_diff + && D_LOWLINE (other_diff, FC) <= high_water_mark + 1) + { + + /* Incorporate this diff into the using list. Note that + this doesn't take it off the current list */ + if (using[other_thread]) + last_using[other_thread]->next = other_diff; + else + using[other_thread] = other_diff; + last_using[other_thread] = other_diff; + + /* Take it off the current list. Note that this following + code assumes that other_diff enters it equal to + current[high_water_thread ^ 0x1] */ + current[other_thread] = current[other_thread]->next; + other_diff->next = 0; + + /* Set the high_water stuff + If this comparison is equal, then this is the last pass + through this loop; since diff blocks within a given + thread cannot overlap, the high_water_mark will be + *below* the range_start of either of the next diffs. */ + + if (high_water_mark < D_HIGHLINE (other_diff, FC)) + { + high_water_thread ^= 1; + high_water_diff = other_diff; + high_water_mark = D_HIGHLINE (other_diff, FC); + } + + /* Set the other diff */ + other_thread = high_water_thread ^ 0x1; + other_diff = current[other_thread]; + } + + /* The using lists contain a list of all of the blocks to be + included in this diff3_block. Create it. */ + + tmpblock = using_to_diff3_block (using, last_using, + base_water_thread, high_water_thread, + last_diff3); + + if (!tmpblock) + diff3_fatal ("internal error: screwup in format of diff blocks"); + + /* Put it on the list. */ + *result_end = tmpblock; + result_end = &tmpblock->next; + + /* Set up corresponding lines correctly. */ + last_diff3 = tmpblock; + } + return result; +} + +/* + * using_to_diff3_block: + * This routine takes two lists of blocks (from two separate diff + * threads) and puts them together into one diff3 block. + * It then returns a pointer to this diff3 block or 0 for failure. + * + * All arguments besides using are for the convenience of the routine; + * they could be derived from the using array. + * LAST_USING is a pair of pointers to the last blocks in the using + * structure. + * LOW_THREAD and HIGH_THREAD tell which threads contain the lowest + * and highest line numbers for File0. + * last_diff3 contains the last diff produced in the calling routine. + * This is used for lines mappings which would still be identical to + * the state that diff ended in. + * + * A distinction should be made in this routine between the two diffs + * that are part of a normal two diff block, and the three diffs that + * are part of a diff3_block. + */ +static struct diff3_block * +using_to_diff3_block (using, last_using, low_thread, high_thread, last_diff3) + struct diff_block + *using[2], + *last_using[2]; + int low_thread, high_thread; + struct diff3_block const *last_diff3; +{ + int low[2], high[2]; + struct diff3_block *result; + struct diff_block *ptr; + int d, i; + + /* Find the range in the common file. */ + int lowc = D_LOWLINE (using[low_thread], FC); + int highc = D_HIGHLINE (last_using[high_thread], FC); + + /* Find the ranges in the other files. + If using[d] is null, that means that the file to which that diff + refers is equivalent to the common file over this range. */ + + for (d = 0; d < 2; d++) + if (using[d]) + { + low[d] = D_LOW_MAPLINE (using[d], FC, FO, lowc); + high[d] = D_HIGH_MAPLINE (last_using[d], FC, FO, highc); + } + else + { + low[d] = D_HIGH_MAPLINE (last_diff3, FILEC, FILE0 + d, lowc); + high[d] = D_HIGH_MAPLINE (last_diff3, FILEC, FILE0 + d, highc); + } + + /* Create a block with the appropriate sizes */ + result = create_diff3_block (low[0], high[0], low[1], high[1], lowc, highc); + + /* Copy information for the common file. + Return with a zero if any of the compares failed. */ + + for (d = 0; d < 2; d++) + for (ptr = using[d]; ptr; ptr = D_NEXT (ptr)) + { + int result_offset = D_LOWLINE (ptr, FC) - lowc; + + if (!copy_stringlist (D_LINEARRAY (ptr, FC), + D_LENARRAY (ptr, FC), + D_LINEARRAY (result, FILEC) + result_offset, + D_LENARRAY (result, FILEC) + result_offset, + D_NUMLINES (ptr, FC))) + return 0; + } + + /* Copy information for file d. First deal with anything that might be + before the first diff. */ + + for (d = 0; d < 2; d++) + { + struct diff_block *u = using[d]; + int lo = low[d], hi = high[d]; + + for (i = 0; + i + lo < (u ? D_LOWLINE (u, FO) : hi + 1); + i++) + { + D_RELNUM (result, FILE0 + d, i) = D_RELNUM (result, FILEC, i); + D_RELLEN (result, FILE0 + d, i) = D_RELLEN (result, FILEC, i); + } + + for (ptr = u; ptr; ptr = D_NEXT (ptr)) + { + int result_offset = D_LOWLINE (ptr, FO) - lo; + int linec; + + if (!copy_stringlist (D_LINEARRAY (ptr, FO), + D_LENARRAY (ptr, FO), + D_LINEARRAY (result, FILE0 + d) + result_offset, + D_LENARRAY (result, FILE0 + d) + result_offset, + D_NUMLINES (ptr, FO))) + return 0; + + /* Catch the lines between here and the next diff */ + linec = D_HIGHLINE (ptr, FC) + 1 - lowc; + for (i = D_HIGHLINE (ptr, FO) + 1 - lo; + i < (D_NEXT (ptr) ? D_LOWLINE (D_NEXT (ptr), FO) : hi + 1) - lo; + i++) + { + D_RELNUM (result, FILE0 + d, i) = D_RELNUM (result, FILEC, linec); + D_RELLEN (result, FILE0 + d, i) = D_RELLEN (result, FILEC, linec); + linec++; + } + } + } + + /* Set correspond */ + if (!using[0]) + D3_TYPE (result) = DIFF_2ND; + else if (!using[1]) + D3_TYPE (result) = DIFF_1ST; + else + { + int nl0 = D_NUMLINES (result, FILE0); + int nl1 = D_NUMLINES (result, FILE1); + + if (nl0 != nl1 + || !compare_line_list (D_LINEARRAY (result, FILE0), + D_LENARRAY (result, FILE0), + D_LINEARRAY (result, FILE1), + D_LENARRAY (result, FILE1), + nl0)) + D3_TYPE (result) = DIFF_ALL; + else + D3_TYPE (result) = DIFF_3RD; + } + + return result; +} + +/* + * This routine copies pointers from a list of strings to a different list + * of strings. If a spot in the second list is already filled, it + * makes sure that it is filled with the same string; if not it + * returns 0, the copy incomplete. + * Upon successful completion of the copy, it returns 1. + */ +static int +copy_stringlist (fromptrs, fromlengths, toptrs, tolengths, copynum) + char * const fromptrs[]; + char *toptrs[]; + size_t const fromlengths[]; + size_t tolengths[]; + int copynum; +{ + register char * const *f = fromptrs; + register char **t = toptrs; + register size_t const *fl = fromlengths; + register size_t *tl = tolengths; + + while (copynum--) + { + if (*t) + { if (*fl != *tl || memcmp (*f, *t, *fl)) return 0; } + else + { *t = *f ; *tl = *fl; } + + t++; f++; tl++; fl++; + } + return 1; +} + +/* + * Create a diff3_block, with ranges as specified in the arguments. + * Allocate the arrays for the various pointers (and zero them) based + * on the arguments passed. Return the block as a result. + */ +static struct diff3_block * +create_diff3_block (low0, high0, low1, high1, low2, high2) + register int low0, high0, low1, high1, low2, high2; +{ + struct diff3_block *result = ALLOCATE (1, struct diff3_block); + int numlines; + + D3_TYPE (result) = ERROR; + D_NEXT (result) = 0; + + /* Assign ranges */ + D_LOWLINE (result, FILE0) = low0; + D_HIGHLINE (result, FILE0) = high0; + D_LOWLINE (result, FILE1) = low1; + D_HIGHLINE (result, FILE1) = high1; + D_LOWLINE (result, FILE2) = low2; + D_HIGHLINE (result, FILE2) = high2; + + /* Allocate and zero space */ + numlines = D_NUMLINES (result, FILE0); + if (numlines) + { + D_LINEARRAY (result, FILE0) = ALLOCATE (numlines, char *); + D_LENARRAY (result, FILE0) = ALLOCATE (numlines, size_t); + bzero (D_LINEARRAY (result, FILE0), (numlines * sizeof (char *))); + bzero (D_LENARRAY (result, FILE0), (numlines * sizeof (size_t))); + } + else + { + D_LINEARRAY (result, FILE0) = 0; + D_LENARRAY (result, FILE0) = 0; + } + + numlines = D_NUMLINES (result, FILE1); + if (numlines) + { + D_LINEARRAY (result, FILE1) = ALLOCATE (numlines, char *); + D_LENARRAY (result, FILE1) = ALLOCATE (numlines, size_t); + bzero (D_LINEARRAY (result, FILE1), (numlines * sizeof (char *))); + bzero (D_LENARRAY (result, FILE1), (numlines * sizeof (size_t))); + } + else + { + D_LINEARRAY (result, FILE1) = 0; + D_LENARRAY (result, FILE1) = 0; + } + + numlines = D_NUMLINES (result, FILE2); + if (numlines) + { + D_LINEARRAY (result, FILE2) = ALLOCATE (numlines, char *); + D_LENARRAY (result, FILE2) = ALLOCATE (numlines, size_t); + bzero (D_LINEARRAY (result, FILE2), (numlines * sizeof (char *))); + bzero (D_LENARRAY (result, FILE2), (numlines * sizeof (size_t))); + } + else + { + D_LINEARRAY (result, FILE2) = 0; + D_LENARRAY (result, FILE2) = 0; + } + + /* Return */ + return result; +} + +/* + * Compare two lists of lines of text. + * Return 1 if they are equivalent, 0 if not. + */ +static int +compare_line_list (list1, lengths1, list2, lengths2, nl) + char * const list1[], * const list2[]; + size_t const lengths1[], lengths2[]; + int nl; +{ + char + * const *l1 = list1, + * const *l2 = list2; + size_t const + *lgths1 = lengths1, + *lgths2 = lengths2; + + while (nl--) + if (!*l1 || !*l2 || *lgths1 != *lgths2++ + || memcmp (*l1++, *l2++, *lgths1++)) + return 0; + return 1; +} + +/* + * Routines to input and parse two way diffs. + */ + +extern char **environ; + +static struct diff_block * +process_diff (filea, fileb, last_block, diff_contents) + char const *filea, *fileb; + struct diff_block **last_block; + char **diff_contents; +{ + char *diff_limit; + char *scan_diff; + enum diff_type dt; + int i; + struct diff_block *block_list, **block_list_end, *bptr; + + diff_limit = read_diff (filea, fileb, diff_contents); + scan_diff = *diff_contents; + block_list_end = &block_list; + bptr = 0; /* Pacify `gcc -W'. */ + + while (scan_diff < diff_limit) + { + bptr = ALLOCATE (1, struct diff_block); + bptr->lines[0] = bptr->lines[1] = 0; + bptr->lengths[0] = bptr->lengths[1] = 0; + + dt = process_diff_control (&scan_diff, bptr); + if (dt == ERROR || *scan_diff != '\n') + { + fprintf (stderr, "%s: diff error: ", diff_program_name); + do + { + putc (*scan_diff, stderr); + } + while (*scan_diff++ != '\n'); + DIFF3_ABORT (2); + } + scan_diff++; + + /* Force appropriate ranges to be null, if necessary */ + switch (dt) + { + case ADD: + bptr->ranges[0][0]++; + break; + case DELETE: + bptr->ranges[1][0]++; + break; + case CHANGE: + break; + default: + diff3_fatal ("internal error: invalid diff type in process_diff"); + break; + } + + /* Allocate space for the pointers for the lines from filea, and + parcel them out among these pointers */ + if (dt != ADD) + { + int numlines = D_NUMLINES (bptr, 0); + bptr->lines[0] = ALLOCATE (numlines, char *); + bptr->lengths[0] = ALLOCATE (numlines, size_t); + for (i = 0; i < numlines; i++) + scan_diff = scan_diff_line (scan_diff, + &(bptr->lines[0][i]), + &(bptr->lengths[0][i]), + diff_limit, + '<'); + } + + /* Get past the separator for changes */ + if (dt == CHANGE) + { + if (strncmp (scan_diff, "---\n", 4)) + diff3_fatal ("invalid diff format; invalid change separator"); + scan_diff += 4; + } + + /* Allocate space for the pointers for the lines from fileb, and + parcel them out among these pointers */ + if (dt != DELETE) + { + int numlines = D_NUMLINES (bptr, 1); + bptr->lines[1] = ALLOCATE (numlines, char *); + bptr->lengths[1] = ALLOCATE (numlines, size_t); + for (i = 0; i < numlines; i++) + scan_diff = scan_diff_line (scan_diff, + &(bptr->lines[1][i]), + &(bptr->lengths[1][i]), + diff_limit, + '>'); + } + + /* Place this block on the blocklist. */ + *block_list_end = bptr; + block_list_end = &bptr->next; + } + + *block_list_end = 0; + *last_block = bptr; + return block_list; +} + +/* + * This routine will parse a normal format diff control string. It + * returns the type of the diff (ERROR if the format is bad). All of + * the other important information is filled into to the structure + * pointed to by db, and the string pointer (whose location is passed + * to this routine) is updated to point beyond the end of the string + * parsed. Note that only the ranges in the diff_block will be set by + * this routine. + * + * If some specific pair of numbers has been reduced to a single + * number, then both corresponding numbers in the diff block are set + * to that number. In general these numbers are interpetted as ranges + * inclusive, unless being used by the ADD or DELETE commands. It is + * assumed that these will be special cased in a superior routine. + */ + +static enum diff_type +process_diff_control (string, db) + char **string; + struct diff_block *db; +{ + char *s = *string; + int holdnum; + enum diff_type type; + +/* These macros are defined here because they can use variables + defined in this function. Don't try this at home kids, we're + trained professionals! + + Also note that SKIPWHITE only recognizes tabs and spaces, and + that READNUM can only read positive, integral numbers */ + +#define SKIPWHITE(s) { while (*s == ' ' || *s == '\t') s++; } +#define READNUM(s, num) \ + { unsigned char c = *s; if (!ISDIGIT (c)) return ERROR; holdnum = 0; \ + do { holdnum = (c - '0' + holdnum * 10); } \ + while (ISDIGIT (c = *++s)); (num) = holdnum; } + + /* Read first set of digits */ + SKIPWHITE (s); + READNUM (s, db->ranges[0][START]); + + /* Was that the only digit? */ + SKIPWHITE (s); + if (*s == ',') + { + /* Get the next digit */ + s++; + READNUM (s, db->ranges[0][END]); + } + else + db->ranges[0][END] = db->ranges[0][START]; + + /* Get the letter */ + SKIPWHITE (s); + switch (*s) + { + case 'a': + type = ADD; + break; + case 'c': + type = CHANGE; + break; + case 'd': + type = DELETE; + break; + default: + return ERROR; /* Bad format */ + } + s++; /* Past letter */ + + /* Read second set of digits */ + SKIPWHITE (s); + READNUM (s, db->ranges[1][START]); + + /* Was that the only digit? */ + SKIPWHITE (s); + if (*s == ',') + { + /* Get the next digit */ + s++; + READNUM (s, db->ranges[1][END]); + SKIPWHITE (s); /* To move to end */ + } + else + db->ranges[1][END] = db->ranges[1][START]; + + *string = s; + return type; +} + +static char * +read_diff (filea, fileb, output_placement) + char const *filea, *fileb; + char **output_placement; +{ + char *diff_result; + size_t bytes, current_chunk_size, total; + int fd, wstatus; + struct stat pipestat; + + /* 302 / 1000 is log10(2.0) rounded up. Subtract 1 for the sign bit; + add 1 for integer division truncation; add 1 more for a minus sign. */ +#define INT_STRLEN_BOUND(type) ((sizeof(type)*CHAR_BIT - 1) * 302 / 1000 + 2) + + char const *argv[7]; + char horizon_arg[17 + INT_STRLEN_BOUND (int)]; + char const **ap; + char *diffout; + + ap = argv; + *ap++ = "diff"; + if (always_text) + *ap++ = "-a"; + sprintf (horizon_arg, "--horizon-lines=%d", horizon_lines); + *ap++ = horizon_arg; + *ap++ = "--"; + *ap++ = filea; + *ap++ = fileb; + *ap = 0; + + diffout = tmpnam(NULL); + wstatus = diff_run (ap - argv, (char **) argv, diffout); + if (wstatus == 2) + diff3_fatal ("subsidiary diff failed"); + + if (-1 == (fd = open (diffout, O_RDONLY))) + diff3_fatal ("could not open temporary diff file"); + + current_chunk_size = 8 * 1024; + if (fstat (fd, &pipestat) == 0) + current_chunk_size = max (current_chunk_size, STAT_BLOCKSIZE (pipestat)); + + diff_result = xmalloc (current_chunk_size); + total = 0; + do { + bytes = myread (fd, + diff_result + total, + current_chunk_size - total); + total += bytes; + if (total == current_chunk_size) + { + if (current_chunk_size < 2 * current_chunk_size) + current_chunk_size = 2 * current_chunk_size; + else if (current_chunk_size < (size_t) -1) + current_chunk_size = (size_t) -1; + else + diff3_fatal ("files are too large to fit into memory"); + diff_result = xrealloc (diff_result, (current_chunk_size *= 2)); + } + } while (bytes); + + if (total != 0 && diff_result[total-1] != '\n') + diff3_fatal ("invalid diff format; incomplete last line"); + + *output_placement = diff_result; + + if (close (fd) != 0) + diff3_perror_with_exit ("pipe close"); + unlink (diffout); + + return diff_result + total; +} + + +/* + * Scan a regular diff line (consisting of > or <, followed by a + * space, followed by text (including nulls) up to a newline. + * + * This next routine began life as a macro and many parameters in it + * are used as call-by-reference values. + */ +static char * +scan_diff_line (scan_ptr, set_start, set_length, limit, leadingchar) + char *scan_ptr, **set_start; + size_t *set_length; + char *limit; + int leadingchar; +{ + char *line_ptr; + + if (!(scan_ptr[0] == leadingchar + && scan_ptr[1] == ' ')) + diff3_fatal ("invalid diff format; incorrect leading line chars"); + + *set_start = line_ptr = scan_ptr + 2; + while (*line_ptr++ != '\n') + ; + + /* Include newline if the original line ended in a newline, + or if an edit script is being generated. + Copy any missing newline message to stderr if an edit script is being + generated, because edit scripts cannot handle missing newlines. + Return the beginning of the next line. */ + *set_length = line_ptr - *set_start; + if (line_ptr < limit && *line_ptr == '\\') + { + if (edscript) + fprintf (stderr, "%s:", diff_program_name); + else + --*set_length; + line_ptr++; + do + { + if (edscript) + putc (*line_ptr, stderr); + } + while (*line_ptr++ != '\n'); + } + + return line_ptr; +} + +/* + * This routine outputs a three way diff passed as a list of + * diff3_block's. + * The argument MAPPING is indexed by external file number (in the + * argument list) and contains the internal file number (from the + * diff passed). This is important because the user expects his + * outputs in terms of the argument list number, and the diff passed + * may have been done slightly differently (if the last argument + * was "-", for example). + * REV_MAPPING is the inverse of MAPPING. + */ +static void +output_diff3 (outputfile, diff, mapping, rev_mapping) + FILE *outputfile; + struct diff3_block *diff; + int const mapping[3], rev_mapping[3]; +{ + int i; + int oddoneout; + char *cp; + struct diff3_block *ptr; + int line; + size_t length; + int dontprint; + static int skew_increment[3] = { 2, 3, 1 }; /* 0==>2==>1==>3 */ + char const *line_prefix = tab_align_flag ? "\t" : " "; + + for (ptr = diff; ptr; ptr = D_NEXT (ptr)) + { + char x[2]; + + switch (ptr->correspond) + { + case DIFF_ALL: + x[0] = '\0'; + dontprint = 3; /* Print them all */ + oddoneout = 3; /* Nobody's odder than anyone else */ + break; + case DIFF_1ST: + case DIFF_2ND: + case DIFF_3RD: + oddoneout = rev_mapping[(int) ptr->correspond - (int) DIFF_1ST]; + + x[0] = oddoneout + '1'; + x[1] = '\0'; + dontprint = oddoneout==0; + break; + default: + diff3_fatal ("internal error: invalid diff type passed to output"); + } + fprintf (outputfile, "====%s\n", x); + + /* Go 0, 2, 1 if the first and third outputs are equivalent. */ + for (i = 0; i < 3; + i = (oddoneout == 1 ? skew_increment[i] : i + 1)) + { + int realfile = mapping[i]; + int + lowt = D_LOWLINE (ptr, realfile), + hight = D_HIGHLINE (ptr, realfile); + + fprintf (outputfile, "%d:", i + 1); + switch (lowt - hight) + { + case 1: + fprintf (outputfile, "%da\n", lowt - 1); + break; + case 0: + fprintf (outputfile, "%dc\n", lowt); + break; + default: + fprintf (outputfile, "%d,%dc\n", lowt, hight); + break; + } + + if (i == dontprint) continue; + + if (lowt <= hight) + { + line = 0; + do + { + fprintf (outputfile, line_prefix); + cp = D_RELNUM (ptr, realfile, line); + length = D_RELLEN (ptr, realfile, line); + fwrite (cp, sizeof (char), length, outputfile); + } + while (++line < hight - lowt + 1); + if (cp[length - 1] != '\n') + fprintf (outputfile, "\n\\ No newline at end of file\n"); + } + } + } +} + + +/* + * Output to OUTPUTFILE the lines of B taken from FILENUM. + * Double any initial '.'s; yield nonzero if any initial '.'s were doubled. + */ +static int +dotlines (outputfile, b, filenum) + FILE *outputfile; + struct diff3_block *b; + int filenum; +{ + int i; + int leading_dot = 0; + + for (i = 0; + i < D_NUMLINES (b, filenum); + i++) + { + char *line = D_RELNUM (b, filenum, i); + if (line[0] == '.') + { + leading_dot = 1; + fprintf (outputfile, "."); + } + fwrite (line, sizeof (char), + D_RELLEN (b, filenum, i), outputfile); + } + + return leading_dot; +} + +/* + * Output to OUTPUTFILE a '.' line. If LEADING_DOT is nonzero, + * also output a command that removes initial '.'s + * starting with line START and continuing for NUM lines. + */ +static void +undotlines (outputfile, leading_dot, start, num) + FILE *outputfile; + int leading_dot, start, num; +{ + fprintf (outputfile, ".\n"); + if (leading_dot) + if (num == 1) + fprintf (outputfile, "%ds/^\\.//\n", start); + else + fprintf (outputfile, "%d,%ds/^\\.//\n", start, start + num - 1); +} + +/* + * This routine outputs a diff3 set of blocks as an ed script. This + * script applies the changes between file's 2 & 3 to file 1. It + * takes the precise format of the ed script to be output from global + * variables set during options processing. Note that it does + * destructive things to the set of diff3 blocks it is passed; it + * reverses their order (this gets around the problems involved with + * changing line numbers in an ed script). + * + * Note that this routine has the same problem of mapping as the last + * one did; the variable MAPPING maps from file number according to + * the argument list to file number according to the diff passed. All + * files listed below are in terms of the argument list. + * REV_MAPPING is the inverse of MAPPING. + * + * The arguments FILE0, FILE1 and FILE2 are the strings to print + * as the names of the three files. These may be the actual names, + * or may be the arguments specified with -L. + * + * Returns 1 if conflicts were found. + */ + +static int +output_diff3_edscript (outputfile, diff, mapping, rev_mapping, + file0, file1, file2) + FILE *outputfile; + struct diff3_block *diff; + int const mapping[3], rev_mapping[3]; + char const *file0, *file1, *file2; +{ + int leading_dot; + int conflicts_found = 0, conflict; + struct diff3_block *b; + + for (b = reverse_diff3_blocklist (diff); b; b = b->next) + { + /* Must do mapping correctly. */ + enum diff_type type + = ((b->correspond == DIFF_ALL) ? + DIFF_ALL : + ((enum diff_type) + (((int) DIFF_1ST) + + rev_mapping[(int) b->correspond - (int) DIFF_1ST]))); + + /* If we aren't supposed to do this output block, skip it. */ + switch (type) + { + default: continue; + case DIFF_2ND: if (!show_2nd) continue; conflict = 1; break; + case DIFF_3RD: if (overlap_only) continue; conflict = 0; break; + case DIFF_ALL: if (simple_only) continue; conflict = flagging; break; + } + + if (conflict) + { + conflicts_found = 1; + + + /* Mark end of conflict. */ + + fprintf (outputfile, "%da\n", D_HIGHLINE (b, mapping[FILE0])); + leading_dot = 0; + if (type == DIFF_ALL) + { + if (show_2nd) + { + /* Append lines from FILE1. */ + fprintf (outputfile, "||||||| %s\n", file1); + leading_dot = dotlines (outputfile, b, mapping[FILE1]); + } + /* Append lines from FILE2. */ + fprintf (outputfile, "=======\n"); + leading_dot |= dotlines (outputfile, b, mapping[FILE2]); + } + fprintf (outputfile, ">>>>>>> %s\n", file2); + undotlines (outputfile, leading_dot, + D_HIGHLINE (b, mapping[FILE0]) + 2, + (D_NUMLINES (b, mapping[FILE1]) + + D_NUMLINES (b, mapping[FILE2]) + 1)); + + + /* Mark start of conflict. */ + + fprintf (outputfile, "%da\n<<<<<<< %s\n", + D_LOWLINE (b, mapping[FILE0]) - 1, + type == DIFF_ALL ? file0 : file1); + leading_dot = 0; + if (type == DIFF_2ND) + { + /* Prepend lines from FILE1. */ + leading_dot = dotlines (outputfile, b, mapping[FILE1]); + fprintf (outputfile, "=======\n"); + } + undotlines (outputfile, leading_dot, + D_LOWLINE (b, mapping[FILE0]) + 1, + D_NUMLINES (b, mapping[FILE1])); + } + else if (D_NUMLINES (b, mapping[FILE2]) == 0) + /* Write out a delete */ + { + if (D_NUMLINES (b, mapping[FILE0]) == 1) + fprintf (outputfile, "%dd\n", + D_LOWLINE (b, mapping[FILE0])); + else + fprintf (outputfile, "%d,%dd\n", + D_LOWLINE (b, mapping[FILE0]), + D_HIGHLINE (b, mapping[FILE0])); + } + else + /* Write out an add or change */ + { + switch (D_NUMLINES (b, mapping[FILE0])) + { + case 0: + fprintf (outputfile, "%da\n", + D_HIGHLINE (b, mapping[FILE0])); + break; + case 1: + fprintf (outputfile, "%dc\n", + D_HIGHLINE (b, mapping[FILE0])); + break; + default: + fprintf (outputfile, "%d,%dc\n", + D_LOWLINE (b, mapping[FILE0]), + D_HIGHLINE (b, mapping[FILE0])); + break; + } + + undotlines (outputfile, dotlines (outputfile, b, mapping[FILE2]), + D_LOWLINE (b, mapping[FILE0]), + D_NUMLINES (b, mapping[FILE2])); + } + } + if (finalwrite) fprintf (outputfile, "w\nq\n"); + return conflicts_found; +} + +/* + * Read from INFILE and output to OUTPUTFILE a set of diff3_ blocks DIFF + * as a merged file. This acts like 'ed file0 <[output_diff3_edscript]', + * except that it works even for binary data or incomplete lines. + * + * As before, MAPPING maps from arg list file number to diff file number, + * REV_MAPPING is its inverse, + * and FILE0, FILE1, and FILE2 are the names of the files. + * + * Returns 1 if conflicts were found. + */ + +static int +output_diff3_merge (infile, outputfile, diff, mapping, rev_mapping, + file0, file1, file2) + FILE *infile, *outputfile; + struct diff3_block *diff; + int const mapping[3], rev_mapping[3]; + char const *file0, *file1, *file2; +{ + int c, i; + int conflicts_found = 0, conflict; + struct diff3_block *b; + int linesread = 0; + + for (b = diff; b; b = b->next) + { + /* Must do mapping correctly. */ + enum diff_type type + = ((b->correspond == DIFF_ALL) ? + DIFF_ALL : + ((enum diff_type) + (((int) DIFF_1ST) + + rev_mapping[(int) b->correspond - (int) DIFF_1ST]))); + char const *format_2nd = "<<<<<<< %s\n"; + + /* If we aren't supposed to do this output block, skip it. */ + switch (type) + { + default: continue; + case DIFF_2ND: if (!show_2nd) continue; conflict = 1; break; + case DIFF_3RD: if (overlap_only) continue; conflict = 0; break; + case DIFF_ALL: if (simple_only) continue; conflict = flagging; + format_2nd = "||||||| %s\n"; + break; + } + + /* Copy I lines from file 0. */ + i = D_LOWLINE (b, FILE0) - linesread - 1; + linesread += i; + while (0 <= --i) + do + { + c = getc (infile); + if (c == EOF) + if (ferror (infile)) + diff3_perror_with_exit ("input file"); + else if (feof (infile)) + diff3_fatal ("input file shrank"); + putc (c, outputfile); + } + while (c != '\n'); + + if (conflict) + { + conflicts_found = 1; + + if (type == DIFF_ALL) + { + /* Put in lines from FILE0 with bracket. */ + fprintf (outputfile, "<<<<<<< %s\n", file0); + for (i = 0; + i < D_NUMLINES (b, mapping[FILE0]); + i++) + fwrite (D_RELNUM (b, mapping[FILE0], i), sizeof (char), + D_RELLEN (b, mapping[FILE0], i), outputfile); + } + + if (show_2nd) + { + /* Put in lines from FILE1 with bracket. */ + fprintf (outputfile, format_2nd, file1); + for (i = 0; + i < D_NUMLINES (b, mapping[FILE1]); + i++) + fwrite (D_RELNUM (b, mapping[FILE1], i), sizeof (char), + D_RELLEN (b, mapping[FILE1], i), outputfile); + } + + fprintf (outputfile, "=======\n"); + } + + /* Put in lines from FILE2. */ + for (i = 0; + i < D_NUMLINES (b, mapping[FILE2]); + i++) + fwrite (D_RELNUM (b, mapping[FILE2], i), sizeof (char), + D_RELLEN (b, mapping[FILE2], i), outputfile); + + if (conflict) + fprintf (outputfile, ">>>>>>> %s\n", file2); + + /* Skip I lines in file 0. */ + i = D_NUMLINES (b, FILE0); + linesread += i; + while (0 <= --i) + while ((c = getc (infile)) != '\n') + if (c == EOF) + if (ferror (infile)) + diff3_perror_with_exit ("input file"); + else if (feof (infile)) + { + if (i || b->next) + diff3_fatal ("input file shrank"); + return conflicts_found; + } + } + /* Copy rest of common file. */ + while ((c = getc (infile)) != EOF || !(ferror (infile) | feof (infile))) + putc (c, outputfile); + return conflicts_found; +} + +/* + * Reverse the order of the list of diff3 blocks. + */ +static struct diff3_block * +reverse_diff3_blocklist (diff) + struct diff3_block *diff; +{ + register struct diff3_block *tmp, *next, *prev; + + for (tmp = diff, prev = 0; tmp; tmp = next) + { + next = tmp->next; + tmp->next = prev; + prev = tmp; + } + + return prev; +} + +static size_t +myread (fd, ptr, size) + int fd; + char *ptr; + size_t size; +{ + size_t result = read (fd, ptr, size); + if (result == -1) + diff3_perror_with_exit ("read failed"); + return result; +} + +static void +diff3_fatal (string) + char const *string; +{ + fprintf (stderr, "%s: %s\n", diff_program_name, string); + DIFF3_ABORT (2); +} + +static void +diff3_perror_with_exit (string) + char const *string; +{ + int e = errno; + fprintf (stderr, "%s: ", diff_program_name); + errno = e; + perror (string); + DIFF3_ABORT (2); +} + +static void +initialize_main (argcp, argvp) + int *argcp; + char ***argvp; +{ + always_text = 0; + edscript = 0; + flagging = 0; + horizon_lines = 10; + tab_align_flag = 0; + simple_only = 0; + overlap_only = 0; + show_2nd = 0; + finalwrite = 0; + merge = 0; + diff_program_name = (*argvp)[0]; +} + +static void +free_diff_blocks(p) + struct diff_block *p; +{ + register struct diff_block *next; + + while (p) + { + next = p->next; + if (p->lines[0]) free(p->lines[0]); + if (p->lines[1]) free(p->lines[1]); + if (p->lengths[0]) free(p->lengths[0]); + if (p->lengths[1]) free(p->lengths[1]); + free(p); + p = next; + } +} + +static void +free_diff3_blocks(p) + struct diff3_block *p; +{ + register struct diff3_block *next; + + while (p) + { + next = p->next; + if (p->lines[0]) free(p->lines[0]); + if (p->lines[1]) free(p->lines[1]); + if (p->lines[2]) free(p->lines[2]); + if (p->lengths[0]) free(p->lengths[0]); + if (p->lengths[1]) free(p->lengths[1]); + if (p->lengths[2]) free(p->lengths[2]); + free(p); + p = next; + } +} diff --git a/contrib/cvs/diff/dir.c b/contrib/cvs/diff/dir.c new file mode 100644 index 0000000..6eef9a6 --- /dev/null +++ b/contrib/cvs/diff/dir.c @@ -0,0 +1,220 @@ +/* Read, sort and compare two directories. Used for GNU DIFF. + Copyright (C) 1988, 1989, 1992, 1993, 1994 Free Software Foundation, Inc. + +This file is part of GNU DIFF. + +GNU DIFF is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +GNU DIFF is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU DIFF; see the file COPYING. If not, write to +the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ + +#include "diff.h" + +/* Read the directory named by DIR and store into DIRDATA a sorted vector + of filenames for its contents. DIR->desc == -1 means this directory is + known to be nonexistent, so set DIRDATA to an empty vector. + Return -1 (setting errno) if error, 0 otherwise. */ + +struct dirdata +{ + char const **names; /* Sorted names of files in dir, 0-terminated. */ + char *data; /* Allocated storage for file names. */ +}; + +static int compare_names PARAMS((void const *, void const *)); +static int dir_sort PARAMS((struct file_data const *, struct dirdata *)); + +#ifdef _WIN32 +#define CLOSEDIR_VOID 1 +#endif + +static int +dir_sort (dir, dirdata) + struct file_data const *dir; + struct dirdata *dirdata; +{ + register struct dirent *next; + register int i; + + /* Address of block containing the files that are described. */ + char const **names; + + /* Number of files in directory. */ + size_t nnames; + + /* Allocated and used storage for file name data. */ + char *data; + size_t data_alloc, data_used; + + dirdata->names = 0; + dirdata->data = 0; + nnames = 0; + data = 0; + + if (dir->desc != -1) + { + /* Open the directory and check for errors. */ + register DIR *reading = opendir (dir->name); + if (!reading) + return -1; + + /* Initialize the table of filenames. */ + + data_alloc = max (1, (size_t) dir->stat.st_size); + data_used = 0; + dirdata->data = data = xmalloc (data_alloc); + + /* Read the directory entries, and insert the subfiles + into the `data' table. */ + + while ((errno = 0, (next = readdir (reading)) != 0)) + { + char *d_name = next->d_name; + size_t d_size = NAMLEN (next) + 1; + + /* Ignore the files `.' and `..' */ + if (d_name[0] == '.' + && (d_name[1] == 0 || (d_name[1] == '.' && d_name[2] == 0))) + continue; + + if (excluded_filename (d_name)) + continue; + + while (data_alloc < data_used + d_size) + dirdata->data = data = xrealloc (data, data_alloc *= 2); + memcpy (data + data_used, d_name, d_size); + data_used += d_size; + nnames++; + } + if (errno) + { + int e = errno; + closedir (reading); + errno = e; + return -1; + } +#if CLOSEDIR_VOID + closedir (reading); +#else + if (closedir (reading) != 0) + return -1; +#endif + } + + /* Create the `names' table from the `data' table. */ + dirdata->names = names = (char const **) xmalloc (sizeof (char *) + * (nnames + 1)); + for (i = 0; i < nnames; i++) + { + names[i] = data; + data += strlen (data) + 1; + } + names[nnames] = 0; + + /* Sort the table. */ + qsort (names, nnames, sizeof (char *), compare_names); + + return 0; +} + +/* Sort the files now in the table. */ + +static int +compare_names (file1, file2) + void const *file1, *file2; +{ + return filename_cmp (* (char const *const *) file1, + * (char const *const *) file2); +} + +/* Compare the contents of two directories named in FILEVEC[0] and FILEVEC[1]. + This is a top-level routine; it does everything necessary for diff + on two directories. + + FILEVEC[0].desc == -1 says directory FILEVEC[0] doesn't exist, + but pretend it is empty. Likewise for FILEVEC[1]. + + HANDLE_FILE is a caller-provided subroutine called to handle each file. + It gets five operands: dir and name (rel to original working dir) of file + in dir 0, dir and name pathname of file in dir 1, and the recursion depth. + + For a file that appears in only one of the dirs, one of the name-args + to HANDLE_FILE is zero. + + DEPTH is the current depth in recursion, used for skipping top-level + files by the -S option. + + Returns the maximum of all the values returned by HANDLE_FILE, + or 2 if trouble is encountered in opening files. */ + +int +diff_dirs (filevec, handle_file, depth) + struct file_data const filevec[]; + int (*handle_file) PARAMS((char const *, char const *, char const *, char const *, int)); + int depth; +{ + struct dirdata dirdata[2]; + int val = 0; /* Return value. */ + int i; + + /* Get sorted contents of both dirs. */ + for (i = 0; i < 2; i++) + if (dir_sort (&filevec[i], &dirdata[i]) != 0) + { + perror_with_name (filevec[i].name); + val = 2; + } + + if (val == 0) + { + register char const * const *names0 = dirdata[0].names; + register char const * const *names1 = dirdata[1].names; + char const *name0 = filevec[0].name; + char const *name1 = filevec[1].name; + + /* If `-S name' was given, and this is the topmost level of comparison, + ignore all file names less than the specified starting name. */ + + if (dir_start_file && depth == 0) + { + while (*names0 && filename_cmp (*names0, dir_start_file) < 0) + names0++; + while (*names1 && filename_cmp (*names1, dir_start_file) < 0) + names1++; + } + + /* Loop while files remain in one or both dirs. */ + while (*names0 || *names1) + { + /* Compare next name in dir 0 with next name in dir 1. + At the end of a dir, + pretend the "next name" in that dir is very large. */ + int nameorder = (!*names0 ? 1 : !*names1 ? -1 + : filename_cmp (*names0, *names1)); + int v1 = (*handle_file) (name0, 0 < nameorder ? 0 : *names0++, + name1, nameorder < 0 ? 0 : *names1++, + depth + 1); + if (v1 > val) + val = v1; + } + } + + for (i = 0; i < 2; i++) + { + if (dirdata[i].names) + free (dirdata[i].names); + if (dirdata[i].data) + free (dirdata[i].data); + } + + return val; +} diff --git a/contrib/cvs/diff/ed.c b/contrib/cvs/diff/ed.c new file mode 100644 index 0000000..717ef35 --- /dev/null +++ b/contrib/cvs/diff/ed.c @@ -0,0 +1,200 @@ +/* Output routines for ed-script format. + Copyright (C) 1988, 89, 91, 92, 93 Free Software Foundation, Inc. + +This file is part of GNU DIFF. + +GNU DIFF is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +GNU DIFF is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU DIFF; see the file COPYING. If not, write to +the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ + +#include "diff.h" + +static void print_ed_hunk PARAMS((struct change *)); +static void print_rcs_hunk PARAMS((struct change *)); +static void pr_forward_ed_hunk PARAMS((struct change *)); + +/* Print our script as ed commands. */ + +void +print_ed_script (script) + struct change *script; +{ + print_script (script, find_reverse_change, print_ed_hunk); +} + +/* Print a hunk of an ed diff */ + +static void +print_ed_hunk (hunk) + struct change *hunk; +{ + int f0, l0, f1, l1; + int deletes, inserts; + +#if 0 + hunk = flip_script (hunk); +#endif +#ifdef DEBUG + debug_script (hunk); +#endif + + /* Determine range of line numbers involved in each file. */ + analyze_hunk (hunk, &f0, &l0, &f1, &l1, &deletes, &inserts); + if (!deletes && !inserts) + return; + + begin_output (); + + /* Print out the line number header for this hunk */ + print_number_range (',', &files[0], f0, l0); + fprintf (outfile, "%c\n", change_letter (inserts, deletes)); + + /* Print new/changed lines from second file, if needed */ + if (inserts) + { + int i; + int inserting = 1; + for (i = f1; i <= l1; i++) + { + /* Resume the insert, if we stopped. */ + if (! inserting) + fprintf (outfile, "%da\n", + i - f1 + translate_line_number (&files[0], f0) - 1); + inserting = 1; + + /* If the file's line is just a dot, it would confuse `ed'. + So output it with a double dot, and set the flag LEADING_DOT + so that we will output another ed-command later + to change the double dot into a single dot. */ + + if (files[1].linbuf[i][0] == '.' + && files[1].linbuf[i][1] == '\n') + { + fprintf (outfile, "..\n"); + fprintf (outfile, ".\n"); + /* Now change that double dot to the desired single dot. */ + fprintf (outfile, "%ds/^\\.\\././\n", + i - f1 + translate_line_number (&files[0], f0)); + inserting = 0; + } + else + /* Line is not `.', so output it unmodified. */ + print_1_line ("", &files[1].linbuf[i]); + } + + /* End insert mode, if we are still in it. */ + if (inserting) + fprintf (outfile, ".\n"); + } +} + +/* Print change script in the style of ed commands, + but print the changes in the order they appear in the input files, + which means that the commands are not truly useful with ed. */ + +void +pr_forward_ed_script (script) + struct change *script; +{ + print_script (script, find_change, pr_forward_ed_hunk); +} + +static void +pr_forward_ed_hunk (hunk) + struct change *hunk; +{ + int i; + int f0, l0, f1, l1; + int deletes, inserts; + + /* Determine range of line numbers involved in each file. */ + analyze_hunk (hunk, &f0, &l0, &f1, &l1, &deletes, &inserts); + if (!deletes && !inserts) + return; + + begin_output (); + + fprintf (outfile, "%c", change_letter (inserts, deletes)); + print_number_range (' ', files, f0, l0); + fprintf (outfile, "\n"); + + /* If deletion only, print just the number range. */ + + if (!inserts) + return; + + /* For insertion (with or without deletion), print the number range + and the lines from file 2. */ + + for (i = f1; i <= l1; i++) + print_1_line ("", &files[1].linbuf[i]); + + fprintf (outfile, ".\n"); +} + +/* Print in a format somewhat like ed commands + except that each insert command states the number of lines it inserts. + This format is used for RCS. */ + +void +print_rcs_script (script) + struct change *script; +{ + print_script (script, find_change, print_rcs_hunk); +} + +/* Print a hunk of an RCS diff */ + +static void +print_rcs_hunk (hunk) + struct change *hunk; +{ + int i; + int f0, l0, f1, l1; + int deletes, inserts; + int tf0, tl0, tf1, tl1; + + /* Determine range of line numbers involved in each file. */ + analyze_hunk (hunk, &f0, &l0, &f1, &l1, &deletes, &inserts); + if (!deletes && !inserts) + return; + + begin_output (); + + translate_range (&files[0], f0, l0, &tf0, &tl0); + + if (deletes) + { + fprintf (outfile, "d"); + /* For deletion, print just the starting line number from file 0 + and the number of lines deleted. */ + fprintf (outfile, "%d %d\n", + tf0, + (tl0 >= tf0 ? tl0 - tf0 + 1 : 1)); + } + + if (inserts) + { + fprintf (outfile, "a"); + + /* Take last-line-number from file 0 and # lines from file 1. */ + translate_range (&files[1], f1, l1, &tf1, &tl1); + fprintf (outfile, "%d %d\n", + tl0, + (tl1 >= tf1 ? tl1 - tf1 + 1 : 1)); + + /* Print the inserted lines. */ + for (i = f1; i <= l1; i++) + print_1_line ("", &files[1].linbuf[i]); + } +} diff --git a/contrib/cvs/diff/ifdef.c b/contrib/cvs/diff/ifdef.c new file mode 100644 index 0000000..2834cbd --- /dev/null +++ b/contrib/cvs/diff/ifdef.c @@ -0,0 +1,428 @@ +/* #ifdef-format output routines for GNU DIFF. + Copyright (C) 1989, 1991, 1992, 1993, 1994 Free Software Foundation, Inc. + +This file is part of GNU DIFF. + +GNU DIFF is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY. No author or distributor +accepts responsibility to anyone for the consequences of using it +or for whether it serves any particular purpose or works at all, +unless he says so in writing. Refer to the GNU DIFF General Public +License for full details. + +Everyone is granted permission to copy, modify and redistribute +GNU DIFF, but only under the conditions described in the +GNU DIFF General Public License. A copy of this license is +supposed to have been given to you along with GNU DIFF so you +can know your rights and responsibilities. It should be in a +file named COPYING. Among other things, the copyright notice +and this notice must be preserved on all copies. */ + + +#include "diff.h" + +struct group +{ + struct file_data const *file; + int from, upto; /* start and limit lines for this group of lines */ +}; + +static char *format_group PARAMS((FILE *, char *, int, struct group const *)); +static char *scan_char_literal PARAMS((char *, int *)); +static char *scan_printf_spec PARAMS((char *)); +static int groups_letter_value PARAMS((struct group const *, int)); +static void format_ifdef PARAMS((char *, int, int, int, int)); +static void print_ifdef_hunk PARAMS((struct change *)); +static void print_ifdef_lines PARAMS((FILE *, char *, struct group const *)); + +static int next_line; + +/* Print the edit-script SCRIPT as a merged #ifdef file. */ + +void +print_ifdef_script (script) + struct change *script; +{ + next_line = - files[0].prefix_lines; + print_script (script, find_change, print_ifdef_hunk); + if (next_line < files[0].valid_lines) + { + begin_output (); + format_ifdef (group_format[UNCHANGED], next_line, files[0].valid_lines, + next_line - files[0].valid_lines + files[1].valid_lines, + files[1].valid_lines); + } +} + +/* Print a hunk of an ifdef diff. + This is a contiguous portion of a complete edit script, + describing changes in consecutive lines. */ + +static void +print_ifdef_hunk (hunk) + struct change *hunk; +{ + int first0, last0, first1, last1, deletes, inserts; + char *format; + + /* Determine range of line numbers involved in each file. */ + analyze_hunk (hunk, &first0, &last0, &first1, &last1, &deletes, &inserts); + if (inserts) + format = deletes ? group_format[CHANGED] : group_format[NEW]; + else if (deletes) + format = group_format[OLD]; + else + return; + + begin_output (); + + /* Print lines up to this change. */ + if (next_line < first0) + format_ifdef (group_format[UNCHANGED], next_line, first0, + next_line - first0 + first1, first1); + + /* Print this change. */ + next_line = last0 + 1; + format_ifdef (format, first0, next_line, first1, last1 + 1); +} + +/* Print a set of lines according to FORMAT. + Lines BEG0 up to END0 are from the first file; + lines BEG1 up to END1 are from the second file. */ + +static void +format_ifdef (format, beg0, end0, beg1, end1) + char *format; + int beg0, end0, beg1, end1; +{ + struct group groups[2]; + + groups[0].file = &files[0]; + groups[0].from = beg0; + groups[0].upto = end0; + groups[1].file = &files[1]; + groups[1].from = beg1; + groups[1].upto = end1; + format_group (outfile, format, '\0', groups); +} + +/* Print to file OUT a set of lines according to FORMAT. + The format ends at the first free instance of ENDCHAR. + Yield the address of the terminating character. + GROUPS specifies which lines to print. + If OUT is zero, do not actually print anything; just scan the format. */ + +static char * +format_group (out, format, endchar, groups) + register FILE *out; + char *format; + int endchar; + struct group const *groups; +{ + register char c; + register char *f = format; + + while ((c = *f) != endchar && c != 0) + { + f++; + if (c == '%') + { + char *spec = f; + switch ((c = *f++)) + { + case '%': + break; + + case '(': + /* Print if-then-else format e.g. `%(n=1?thenpart:elsepart)'. */ + { + int i, value[2]; + FILE *thenout, *elseout; + + for (i = 0; i < 2; i++) + { + unsigned char f0 = f[0]; + if (ISDIGIT (f0)) + { + value[i] = atoi (f); + while (ISDIGIT ((unsigned char) *++f)) + continue; + } + else + { + value[i] = groups_letter_value (groups, f0); + if (value[i] < 0) + goto bad_format; + f++; + } + if (*f++ != "=?"[i]) + goto bad_format; + } + if (value[0] == value[1]) + thenout = out, elseout = 0; + else + thenout = 0, elseout = out; + f = format_group (thenout, f, ':', groups); + if (*f) + { + f = format_group (elseout, f + 1, ')', groups); + if (*f) + f++; + } + } + continue; + + case '<': + /* Print lines deleted from first file. */ + print_ifdef_lines (out, line_format[OLD], &groups[0]); + continue; + + case '=': + /* Print common lines. */ + print_ifdef_lines (out, line_format[UNCHANGED], &groups[0]); + continue; + + case '>': + /* Print lines inserted from second file. */ + print_ifdef_lines (out, line_format[NEW], &groups[1]); + continue; + + default: + { + int value; + char *speclim; + + f = scan_printf_spec (spec); + if (!f) + goto bad_format; + speclim = f; + c = *f++; + switch (c) + { + case '\'': + f = scan_char_literal (f, &value); + if (!f) + goto bad_format; + break; + + default: + value = groups_letter_value (groups, c); + if (value < 0) + goto bad_format; + break; + } + if (out) + { + /* Temporarily replace e.g. "%3dnx" with "%3d\0x". */ + *speclim = 0; + fprintf (out, spec - 1, value); + /* Undo the temporary replacement. */ + *speclim = c; + } + } + continue; + + bad_format: + c = '%'; + f = spec; + break; + } + } + if (out) + putc (c, out); + } + return f; +} + +/* For the line group pair G, return the number corresponding to LETTER. + Return -1 if LETTER is not a group format letter. */ +static int +groups_letter_value (g, letter) + struct group const *g; + int letter; +{ + if (ISUPPER (letter)) + { + g++; + letter = tolower (letter); + } + switch (letter) + { + case 'e': return translate_line_number (g->file, g->from) - 1; + case 'f': return translate_line_number (g->file, g->from); + case 'l': return translate_line_number (g->file, g->upto) - 1; + case 'm': return translate_line_number (g->file, g->upto); + case 'n': return g->upto - g->from; + default: return -1; + } +} + +/* Print to file OUT, using FORMAT to print the line group GROUP. + But do nothing if OUT is zero. */ +static void +print_ifdef_lines (out, format, group) + register FILE *out; + char *format; + struct group const *group; +{ + struct file_data const *file = group->file; + char const * const *linbuf = file->linbuf; + int from = group->from, upto = group->upto; + + if (!out) + return; + + /* If possible, use a single fwrite; it's faster. */ + if (!tab_expand_flag && format[0] == '%') + { + if (format[1] == 'l' && format[2] == '\n' && !format[3]) + { + fwrite (linbuf[from], sizeof (char), + linbuf[upto] + (linbuf[upto][-1] != '\n') - linbuf[from], + out); + return; + } + if (format[1] == 'L' && !format[2]) + { + fwrite (linbuf[from], sizeof (char), + linbuf[upto] - linbuf[from], out); + return; + } + } + + for (; from < upto; from++) + { + register char c; + register char *f = format; + + while ((c = *f++) != 0) + { + if (c == '%') + { + char *spec = f; + switch ((c = *f++)) + { + case '%': + break; + + case 'l': + output_1_line (linbuf[from], + linbuf[from + 1] + - (linbuf[from + 1][-1] == '\n'), 0, 0); + continue; + + case 'L': + output_1_line (linbuf[from], linbuf[from + 1], 0, 0); + continue; + + default: + { + int value; + char *speclim; + + f = scan_printf_spec (spec); + if (!f) + goto bad_format; + speclim = f; + c = *f++; + switch (c) + { + case '\'': + f = scan_char_literal (f, &value); + if (!f) + goto bad_format; + break; + + case 'n': + value = translate_line_number (file, from); + break; + + default: + goto bad_format; + } + /* Temporarily replace e.g. "%3dnx" with "%3d\0x". */ + *speclim = 0; + fprintf (out, spec - 1, value); + /* Undo the temporary replacement. */ + *speclim = c; + } + continue; + + bad_format: + c = '%'; + f = spec; + break; + } + } + putc (c, out); + } + } +} + +/* Scan the character literal represented in the string LIT; LIT points just + after the initial apostrophe. Put the literal's value into *INTPTR. + Yield the address of the first character after the closing apostrophe, + or zero if the literal is ill-formed. */ +static char * +scan_char_literal (lit, intptr) + char *lit; + int *intptr; +{ + register char *p = lit; + int value, digits; + char c = *p++; + + switch (c) + { + case 0: + case '\'': + return 0; + + case '\\': + value = 0; + while ((c = *p++) != '\'') + { + unsigned digit = c - '0'; + if (8 <= digit) + return 0; + value = 8 * value + digit; + } + digits = p - lit - 2; + if (! (1 <= digits && digits <= 3)) + return 0; + break; + + default: + value = c; + if (*p++ != '\'') + return 0; + break; + } + *intptr = value; + return p; +} + +/* Scan optional printf-style SPEC of the form `-*[0-9]*(.[0-9]*)?[cdoxX]'. + Return the address of the character following SPEC, or zero if failure. */ +static char * +scan_printf_spec (spec) + register char *spec; +{ + register unsigned char c; + + while ((c = *spec++) == '-') + continue; + while (ISDIGIT (c)) + c = *spec++; + if (c == '.') + while (ISDIGIT (c = *spec++)) + continue; + switch (c) + { + case 'c': case 'd': case 'o': case 'x': case 'X': + return spec; + + default: + return 0; + } +} diff --git a/contrib/cvs/diff/io.c b/contrib/cvs/diff/io.c new file mode 100644 index 0000000..6605915 --- /dev/null +++ b/contrib/cvs/diff/io.c @@ -0,0 +1,714 @@ +/* File I/O for GNU DIFF. + Copyright (C) 1988, 1989, 1992, 1993, 1994 Free Software Foundation, Inc. + +This file is part of GNU DIFF. + +GNU DIFF is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +GNU DIFF is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU DIFF; see the file COPYING. If not, write to +the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ + +#include "diff.h" + +/* Rotate a value n bits to the left. */ +#define UINT_BIT (sizeof (unsigned) * CHAR_BIT) +#define ROL(v, n) ((v) << (n) | (v) >> (UINT_BIT - (n))) + +/* Given a hash value and a new character, return a new hash value. */ +#define HASH(h, c) ((c) + ROL (h, 7)) + +/* Guess remaining number of lines from number N of lines so far, + size S so far, and total size T. */ +#define GUESS_LINES(n,s,t) (((t) - (s)) / ((n) < 10 ? 32 : (s) / ((n)-1)) + 5) + +/* Type used for fast prefix comparison in find_identical_ends. */ +#ifndef word +#define word int +#endif + +/* Lines are put into equivalence classes (of lines that match in line_cmp). + Each equivalence class is represented by one of these structures, + but only while the classes are being computed. + Afterward, each class is represented by a number. */ +struct equivclass +{ + int next; /* Next item in this bucket. */ + unsigned hash; /* Hash of lines in this class. */ + char const *line; /* A line that fits this class. */ + size_t length; /* That line's length, not counting its newline. */ +}; + +/* Hash-table: array of buckets, each being a chain of equivalence classes. + buckets[-1] is reserved for incomplete lines. */ +static int *buckets; + +/* Number of buckets in the hash table array, not counting buckets[-1]. */ +static int nbuckets; + +/* Array in which the equivalence classes are allocated. + The bucket-chains go through the elements in this array. + The number of an equivalence class is its index in this array. */ +static struct equivclass *equivs; + +/* Index of first free element in the array `equivs'. */ +static int equivs_index; + +/* Number of elements allocated in the array `equivs'. */ +static int equivs_alloc; + +static void find_and_hash_each_line PARAMS((struct file_data *)); +static void find_identical_ends PARAMS((struct file_data[])); +static void prepare_text_end PARAMS((struct file_data *)); + +/* Check for binary files and compare them for exact identity. */ + +/* Return 1 if BUF contains a non text character. + SIZE is the number of characters in BUF. */ + +#define binary_file_p(buf, size) (memchr (buf, '\0', size) != 0) + +/* Get ready to read the current file. + Return nonzero if SKIP_TEST is zero, + and if it appears to be a binary file. */ + +int +sip (current, skip_test) + struct file_data *current; + int skip_test; +{ + /* If we have a nonexistent file at this stage, treat it as empty. */ + if (current->desc < 0) + { + /* Leave room for a sentinel. */ + current->bufsize = sizeof (word); + current->buffer = xmalloc (current->bufsize); + } + else + { + current->bufsize = STAT_BLOCKSIZE (current->stat); + current->buffer = xmalloc (current->bufsize); + + if (! skip_test) + { + /* Check first part of file to see if it's a binary file. */ +#if HAVE_SETMODE + int oldmode = setmode (current->desc, O_BINARY); +#endif + size_t n = read (current->desc, current->buffer, current->bufsize); + if (n == -1) + pfatal_with_name (current->name); + current->buffered_chars = n; +#if HAVE_SETMODE + if (oldmode != O_BINARY) + { + if (lseek (current->desc, - (off_t) n, SEEK_CUR) == -1) + pfatal_with_name (current->name); + setmode (current->desc, oldmode); + current->buffered_chars = 0; + } +#endif + return binary_file_p (current->buffer, n); + } + } + + current->buffered_chars = 0; + return 0; +} + +/* Slurp the rest of the current file completely into memory. */ + +void +slurp (current) + struct file_data *current; +{ + size_t cc; + + if (current->desc < 0) + /* The file is nonexistent. */ + ; + else if (S_ISREG (current->stat.st_mode)) + { + /* It's a regular file; slurp in the rest all at once. */ + + /* Get the size out of the stat block. + Allocate enough room for appended newline and sentinel. */ + cc = current->stat.st_size + 1 + sizeof (word); + if (current->bufsize < cc) + { + current->bufsize = cc; + current->buffer = xrealloc (current->buffer, cc); + } + + if (current->buffered_chars < current->stat.st_size) + { + cc = read (current->desc, + current->buffer + current->buffered_chars, + current->stat.st_size - current->buffered_chars); + if (cc == -1) + pfatal_with_name (current->name); + current->buffered_chars += cc; + } + } + /* It's not a regular file; read it, growing the buffer as needed. */ + else if (always_text_flag || current->buffered_chars != 0) + { + for (;;) + { + if (current->buffered_chars == current->bufsize) + { + current->bufsize = current->bufsize * 2; + current->buffer = xrealloc (current->buffer, current->bufsize); + } + cc = read (current->desc, + current->buffer + current->buffered_chars, + current->bufsize - current->buffered_chars); + if (cc == 0) + break; + if (cc == -1) + pfatal_with_name (current->name); + current->buffered_chars += cc; + } + /* Allocate just enough room for appended newline and sentinel. */ + current->bufsize = current->buffered_chars + 1 + sizeof (word); + current->buffer = xrealloc (current->buffer, current->bufsize); + } +} + +/* Split the file into lines, simultaneously computing the equivalence class for + each line. */ + +static void +find_and_hash_each_line (current) + struct file_data *current; +{ + unsigned h; + unsigned char const *p = (unsigned char const *) current->prefix_end; + unsigned char c; + int i, *bucket; + size_t length; + + /* Cache often-used quantities in local variables to help the compiler. */ + char const **linbuf = current->linbuf; + int alloc_lines = current->alloc_lines; + int line = 0; + int linbuf_base = current->linbuf_base; + int *cureqs = (int *) xmalloc (alloc_lines * sizeof (int)); + struct equivclass *eqs = equivs; + int eqs_index = equivs_index; + int eqs_alloc = equivs_alloc; + char const *suffix_begin = current->suffix_begin; + char const *bufend = current->buffer + current->buffered_chars; + int use_line_cmp = ignore_some_line_changes; + + while ((char const *) p < suffix_begin) + { + char const *ip = (char const *) p; + + /* Compute the equivalence class for this line. */ + + h = 0; + + /* Hash this line until we find a newline. */ + if (ignore_case_flag) + { + if (ignore_all_space_flag) + while ((c = *p++) != '\n') + { + if (! ISSPACE (c)) + h = HASH (h, ISUPPER (c) ? tolower (c) : c); + } + else if (ignore_space_change_flag) + while ((c = *p++) != '\n') + { + if (ISSPACE (c)) + { + for (;;) + { + c = *p++; + if (!ISSPACE (c)) + break; + if (c == '\n') + goto hashing_done; + } + h = HASH (h, ' '); + } + /* C is now the first non-space. */ + h = HASH (h, ISUPPER (c) ? tolower (c) : c); + } + else + while ((c = *p++) != '\n') + h = HASH (h, ISUPPER (c) ? tolower (c) : c); + } + else + { + if (ignore_all_space_flag) + while ((c = *p++) != '\n') + { + if (! ISSPACE (c)) + h = HASH (h, c); + } + else if (ignore_space_change_flag) + while ((c = *p++) != '\n') + { + if (ISSPACE (c)) + { + for (;;) + { + c = *p++; + if (!ISSPACE (c)) + break; + if (c == '\n') + goto hashing_done; + } + h = HASH (h, ' '); + } + /* C is now the first non-space. */ + h = HASH (h, c); + } + else + while ((c = *p++) != '\n') + h = HASH (h, c); + } + hashing_done:; + + bucket = &buckets[h % nbuckets]; + length = (char const *) p - ip - 1; + + if ((char const *) p == bufend + && current->missing_newline + && ROBUST_OUTPUT_STYLE (output_style)) + { + /* This line is incomplete. If this is significant, + put the line into bucket[-1]. */ + if (! (ignore_space_change_flag | ignore_all_space_flag)) + bucket = &buckets[-1]; + + /* Omit the inserted newline when computing linbuf later. */ + p--; + bufend = suffix_begin = (char const *) p; + } + + for (i = *bucket; ; i = eqs[i].next) + if (!i) + { + /* Create a new equivalence class in this bucket. */ + i = eqs_index++; + if (i == eqs_alloc) + eqs = (struct equivclass *) + xrealloc (eqs, (eqs_alloc*=2) * sizeof(*eqs)); + eqs[i].next = *bucket; + eqs[i].hash = h; + eqs[i].line = ip; + eqs[i].length = length; + *bucket = i; + break; + } + else if (eqs[i].hash == h) + { + char const *eqline = eqs[i].line; + + /* Reuse existing equivalence class if the lines are identical. + This detects the common case of exact identity + faster than complete comparison would. */ + if (eqs[i].length == length && memcmp (eqline, ip, length) == 0) + break; + + /* Reuse existing class if line_cmp reports the lines equal. */ + if (use_line_cmp && line_cmp (eqline, ip) == 0) + break; + } + + /* Maybe increase the size of the line table. */ + if (line == alloc_lines) + { + /* Double (alloc_lines - linbuf_base) by adding to alloc_lines. */ + alloc_lines = 2 * alloc_lines - linbuf_base; + cureqs = (int *) xrealloc (cureqs, alloc_lines * sizeof (*cureqs)); + linbuf = (char const **) xrealloc (linbuf + linbuf_base, + (alloc_lines - linbuf_base) + * sizeof (*linbuf)) + - linbuf_base; + } + linbuf[line] = ip; + cureqs[line] = i; + ++line; + } + + current->buffered_lines = line; + + for (i = 0; ; i++) + { + /* Record the line start for lines in the suffix that we care about. + Record one more line start than lines, + so that we can compute the length of any buffered line. */ + if (line == alloc_lines) + { + /* Double (alloc_lines - linbuf_base) by adding to alloc_lines. */ + alloc_lines = 2 * alloc_lines - linbuf_base; + linbuf = (char const **) xrealloc (linbuf + linbuf_base, + (alloc_lines - linbuf_base) + * sizeof (*linbuf)) + - linbuf_base; + } + linbuf[line] = (char const *) p; + + if ((char const *) p == bufend) + break; + + if (context <= i && no_diff_means_no_output) + break; + + line++; + + while (*p++ != '\n') + ; + } + + /* Done with cache in local variables. */ + current->linbuf = linbuf; + current->valid_lines = line; + current->alloc_lines = alloc_lines; + current->equivs = cureqs; + equivs = eqs; + equivs_alloc = eqs_alloc; + equivs_index = eqs_index; +} + +/* Prepare the end of the text. Make sure it's initialized. + Make sure text ends in a newline, + but remember that we had to add one. */ + +static void +prepare_text_end (current) + struct file_data *current; +{ + size_t buffered_chars = current->buffered_chars; + char *p = current->buffer; + + if (buffered_chars == 0 || p[buffered_chars - 1] == '\n') + current->missing_newline = 0; + else + { + p[buffered_chars++] = '\n'; + current->buffered_chars = buffered_chars; + current->missing_newline = 1; + } + + /* Don't use uninitialized storage when planting or using sentinels. */ + if (p) + bzero (p + buffered_chars, sizeof (word)); +} + +/* Given a vector of two file_data objects, find the identical + prefixes and suffixes of each object. */ + +static void +find_identical_ends (filevec) + struct file_data filevec[]; +{ + word *w0, *w1; + char *p0, *p1, *buffer0, *buffer1; + char const *end0, *beg0; + char const **linbuf0, **linbuf1; + int i, lines; + size_t n0, n1, tem; + int alloc_lines0, alloc_lines1; + int buffered_prefix, prefix_count, prefix_mask; + + slurp (&filevec[0]); + if (filevec[0].desc != filevec[1].desc) + slurp (&filevec[1]); + else + { + filevec[1].buffer = filevec[0].buffer; + filevec[1].bufsize = filevec[0].bufsize; + filevec[1].buffered_chars = filevec[0].buffered_chars; + } + for (i = 0; i < 2; i++) + prepare_text_end (&filevec[i]); + + /* Find identical prefix. */ + + p0 = buffer0 = filevec[0].buffer; + p1 = buffer1 = filevec[1].buffer; + + n0 = filevec[0].buffered_chars; + n1 = filevec[1].buffered_chars; + + if (p0 == p1) + /* The buffers are the same; sentinels won't work. */ + p0 = p1 += n1; + else + { + /* Insert end sentinels, in this case characters that are guaranteed + to make the equality test false, and thus terminate the loop. */ + + if (n0 < n1) + p0[n0] = ~p1[n0]; + else + p1[n1] = ~p0[n1]; + + /* Loop until first mismatch, or to the sentinel characters. */ + + /* Compare a word at a time for speed. */ + w0 = (word *) p0; + w1 = (word *) p1; + while (*w0++ == *w1++) + ; + --w0, --w1; + + /* Do the last few bytes of comparison a byte at a time. */ + p0 = (char *) w0; + p1 = (char *) w1; + while (*p0++ == *p1++) + ; + --p0, --p1; + + /* Don't mistakenly count missing newline as part of prefix. */ + if (ROBUST_OUTPUT_STYLE (output_style) + && (buffer0 + n0 - filevec[0].missing_newline < p0) + != + (buffer1 + n1 - filevec[1].missing_newline < p1)) + --p0, --p1; + } + + /* Now P0 and P1 point at the first nonmatching characters. */ + + /* Skip back to last line-beginning in the prefix, + and then discard up to HORIZON_LINES lines from the prefix. */ + i = horizon_lines; + while (p0 != buffer0 && (p0[-1] != '\n' || i--)) + --p0, --p1; + + /* Record the prefix. */ + filevec[0].prefix_end = p0; + filevec[1].prefix_end = p1; + + /* Find identical suffix. */ + + /* P0 and P1 point beyond the last chars not yet compared. */ + p0 = buffer0 + n0; + p1 = buffer1 + n1; + + if (! ROBUST_OUTPUT_STYLE (output_style) + || filevec[0].missing_newline == filevec[1].missing_newline) + { + end0 = p0; /* Addr of last char in file 0. */ + + /* Get value of P0 at which we should stop scanning backward: + this is when either P0 or P1 points just past the last char + of the identical prefix. */ + beg0 = filevec[0].prefix_end + (n0 < n1 ? 0 : n0 - n1); + + /* Scan back until chars don't match or we reach that point. */ + while (p0 != beg0) + if (*--p0 != *--p1) + { + /* Point at the first char of the matching suffix. */ + ++p0, ++p1; + beg0 = p0; + break; + } + + /* Are we at a line-beginning in both files? If not, add the rest of + this line to the main body. Discard up to HORIZON_LINES lines from + the identical suffix. Also, discard one extra line, + because shift_boundaries may need it. */ + i = horizon_lines + !((buffer0 == p0 || p0[-1] == '\n') + && + (buffer1 == p1 || p1[-1] == '\n')); + while (i-- && p0 != end0) + while (*p0++ != '\n') + ; + + p1 += p0 - beg0; + } + + /* Record the suffix. */ + filevec[0].suffix_begin = p0; + filevec[1].suffix_begin = p1; + + /* Calculate number of lines of prefix to save. + + prefix_count == 0 means save the whole prefix; + we need this with for options like -D that output the whole file. + We also need it for options like -F that output some preceding line; + at least we will need to find the last few lines, + but since we don't know how many, it's easiest to find them all. + + Otherwise, prefix_count != 0. Save just prefix_count lines at start + of the line buffer; they'll be moved to the proper location later. + Handle 1 more line than the context says (because we count 1 too many), + rounded up to the next power of 2 to speed index computation. */ + + if (no_diff_means_no_output && ! function_regexp_list) + { + for (prefix_count = 1; prefix_count < context + 1; prefix_count *= 2) + ; + prefix_mask = prefix_count - 1; + alloc_lines0 + = prefix_count + + GUESS_LINES (0, 0, p0 - filevec[0].prefix_end) + + context; + } + else + { + prefix_count = 0; + prefix_mask = ~0; + alloc_lines0 = GUESS_LINES (0, 0, n0); + } + + lines = 0; + linbuf0 = (char const **) xmalloc (alloc_lines0 * sizeof (*linbuf0)); + + /* If the prefix is needed, find the prefix lines. */ + if (! (no_diff_means_no_output + && filevec[0].prefix_end == p0 + && filevec[1].prefix_end == p1)) + { + p0 = buffer0; + end0 = filevec[0].prefix_end; + while (p0 != end0) + { + int l = lines++ & prefix_mask; + if (l == alloc_lines0) + linbuf0 = (char const **) xrealloc (linbuf0, (alloc_lines0 *= 2) + * sizeof(*linbuf0)); + linbuf0[l] = p0; + while (*p0++ != '\n') + ; + } + } + buffered_prefix = prefix_count && context < lines ? context : lines; + + /* Allocate line buffer 1. */ + tem = prefix_count ? filevec[1].suffix_begin - buffer1 : n1; + + alloc_lines1 + = (buffered_prefix + + GUESS_LINES (lines, filevec[1].prefix_end - buffer1, tem) + + context); + linbuf1 = (char const **) xmalloc (alloc_lines1 * sizeof (*linbuf1)); + + if (buffered_prefix != lines) + { + /* Rotate prefix lines to proper location. */ + for (i = 0; i < buffered_prefix; i++) + linbuf1[i] = linbuf0[(lines - context + i) & prefix_mask]; + for (i = 0; i < buffered_prefix; i++) + linbuf0[i] = linbuf1[i]; + } + + /* Initialize line buffer 1 from line buffer 0. */ + for (i = 0; i < buffered_prefix; i++) + linbuf1[i] = linbuf0[i] - buffer0 + buffer1; + + /* Record the line buffer, adjusted so that + linbuf*[0] points at the first differing line. */ + filevec[0].linbuf = linbuf0 + buffered_prefix; + filevec[1].linbuf = linbuf1 + buffered_prefix; + filevec[0].linbuf_base = filevec[1].linbuf_base = - buffered_prefix; + filevec[0].alloc_lines = alloc_lines0 - buffered_prefix; + filevec[1].alloc_lines = alloc_lines1 - buffered_prefix; + filevec[0].prefix_lines = filevec[1].prefix_lines = lines; +} + +/* Largest primes less than some power of two, for nbuckets. Values range + from useful to preposterous. If one of these numbers isn't prime + after all, don't blame it on me, blame it on primes (6) . . . */ +static int const primes[] = +{ + 509, + 1021, + 2039, + 4093, + 8191, + 16381, + 32749, +#if 32767 < INT_MAX + 65521, + 131071, + 262139, + 524287, + 1048573, + 2097143, + 4194301, + 8388593, + 16777213, + 33554393, + 67108859, /* Preposterously large . . . */ + 134217689, + 268435399, + 536870909, + 1073741789, + 2147483647, +#endif + 0 +}; + +/* Given a vector of two file_data objects, read the file associated + with each one, and build the table of equivalence classes. + Return 1 if either file appears to be a binary file. + If PRETEND_BINARY is nonzero, pretend they are binary regardless. */ + +int +read_files (filevec, pretend_binary) + struct file_data filevec[]; + int pretend_binary; +{ + int i; + int skip_test = always_text_flag | pretend_binary; + int appears_binary = pretend_binary | sip (&filevec[0], skip_test); + + if (filevec[0].desc != filevec[1].desc) + appears_binary |= sip (&filevec[1], skip_test | appears_binary); + else + { + filevec[1].buffer = filevec[0].buffer; + filevec[1].bufsize = filevec[0].bufsize; + filevec[1].buffered_chars = filevec[0].buffered_chars; + } + if (appears_binary) + { +#if HAVE_SETMODE + setmode (filevec[0].desc, O_BINARY); + setmode (filevec[1].desc, O_BINARY); +#endif + return 1; + } + + find_identical_ends (filevec); + + equivs_alloc = filevec[0].alloc_lines + filevec[1].alloc_lines + 1; + equivs = (struct equivclass *) xmalloc (equivs_alloc * sizeof (struct equivclass)); + /* Equivalence class 0 is permanently safe for lines that were not + hashed. Real equivalence classes start at 1. */ + equivs_index = 1; + + for (i = 0; primes[i] < equivs_alloc / 3; i++) + if (! primes[i]) + abort (); + nbuckets = primes[i]; + + buckets = (int *) xmalloc ((nbuckets + 1) * sizeof (*buckets)); + bzero (buckets++, (nbuckets + 1) * sizeof (*buckets)); + + for (i = 0; i < 2; i++) + find_and_hash_each_line (&filevec[i]); + + filevec[0].equiv_max = filevec[1].equiv_max = equivs_index; + + free (equivs); + free (buckets - 1); + + return 0; +} diff --git a/contrib/cvs/diff/normal.c b/contrib/cvs/diff/normal.c new file mode 100644 index 0000000..4d9e23c --- /dev/null +++ b/contrib/cvs/diff/normal.c @@ -0,0 +1,71 @@ +/* Normal-format output routines for GNU DIFF. + Copyright (C) 1988, 1989, 1993 Free Software Foundation, Inc. + +This file is part of GNU DIFF. + +GNU DIFF is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +GNU DIFF is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU DIFF; see the file COPYING. If not, write to +the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ + + +#include "diff.h" + +static void print_normal_hunk PARAMS((struct change *)); + +/* Print the edit-script SCRIPT as a normal diff. + INF points to an array of descriptions of the two files. */ + +void +print_normal_script (script) + struct change *script; +{ + print_script (script, find_change, print_normal_hunk); +} + +/* Print a hunk of a normal diff. + This is a contiguous portion of a complete edit script, + describing changes in consecutive lines. */ + +static void +print_normal_hunk (hunk) + struct change *hunk; +{ + int first0, last0, first1, last1, deletes, inserts; + register int i; + + /* Determine range of line numbers involved in each file. */ + analyze_hunk (hunk, &first0, &last0, &first1, &last1, &deletes, &inserts); + if (!deletes && !inserts) + return; + + begin_output (); + + /* Print out the line number header for this hunk */ + print_number_range (',', &files[0], first0, last0); + fprintf (outfile, "%c", change_letter (inserts, deletes)); + print_number_range (',', &files[1], first1, last1); + fprintf (outfile, "\n"); + + /* Print the lines that the first file has. */ + if (deletes) + for (i = first0; i <= last0; i++) + print_1_line ("<", &files[0].linbuf[i]); + + if (inserts && deletes) + fprintf (outfile, "---\n"); + + /* Print the lines that the second file has. */ + if (inserts) + for (i = first1; i <= last1; i++) + print_1_line (">", &files[1].linbuf[i]); +} diff --git a/contrib/cvs/diff/side.c b/contrib/cvs/diff/side.c new file mode 100644 index 0000000..a150b5e --- /dev/null +++ b/contrib/cvs/diff/side.c @@ -0,0 +1,284 @@ +/* sdiff-format output routines for GNU DIFF. + Copyright (C) 1991, 1992, 1993 Free Software Foundation, Inc. + +This file is part of GNU DIFF. + +GNU DIFF is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY. No author or distributor +accepts responsibility to anyone for the consequences of using it +or for whether it serves any particular purpose or works at all, +unless he says so in writing. Refer to the GNU DIFF General Public +License for full details. + +Everyone is granted permission to copy, modify and redistribute +GNU DIFF, but only under the conditions described in the +GNU DIFF General Public License. A copy of this license is +supposed to have been given to you along with GNU DIFF so you +can know your rights and responsibilities. It should be in a +file named COPYING. Among other things, the copyright notice +and this notice must be preserved on all copies. */ + + +#include "diff.h" + +static unsigned print_half_line PARAMS((char const * const *, unsigned, unsigned)); +static unsigned tab_from_to PARAMS((unsigned, unsigned)); +static void print_1sdiff_line PARAMS((char const * const *, int, char const * const *)); +static void print_sdiff_common_lines PARAMS((int, int)); +static void print_sdiff_hunk PARAMS((struct change *)); + +/* Next line number to be printed in the two input files. */ +static int next0, next1; + +/* Print the edit-script SCRIPT as a sdiff style output. */ + +void +print_sdiff_script (script) + struct change *script; +{ + begin_output (); + + next0 = next1 = - files[0].prefix_lines; + print_script (script, find_change, print_sdiff_hunk); + + print_sdiff_common_lines (files[0].valid_lines, files[1].valid_lines); +} + +/* Tab from column FROM to column TO, where FROM <= TO. Yield TO. */ + +static unsigned +tab_from_to (from, to) + unsigned from, to; +{ + FILE *out = outfile; + unsigned tab; + + if (! tab_expand_flag) + for (tab = from + TAB_WIDTH - from % TAB_WIDTH; tab <= to; tab += TAB_WIDTH) + { + putc ('\t', out); + from = tab; + } + while (from++ < to) + putc (' ', out); + return to; +} + +/* + * Print the text for half an sdiff line. This means truncate to width + * observing tabs, and trim a trailing newline. Returns the last column + * written (not the number of chars). + */ +static unsigned +print_half_line (line, indent, out_bound) + char const * const *line; + unsigned indent, out_bound; +{ + FILE *out = outfile; + register unsigned in_position = 0, out_position = 0; + register char const + *text_pointer = line[0], + *text_limit = line[1]; + + while (text_pointer < text_limit) + { + register unsigned char c = *text_pointer++; + + switch (c) + { + case '\t': + { + unsigned spaces = TAB_WIDTH - in_position % TAB_WIDTH; + if (in_position == out_position) + { + unsigned tabstop = out_position + spaces; + if (tab_expand_flag) + { + if (out_bound < tabstop) + tabstop = out_bound; + for (; out_position < tabstop; out_position++) + putc (' ', out); + } + else + if (tabstop < out_bound) + { + out_position = tabstop; + putc (c, out); + } + } + in_position += spaces; + } + break; + + case '\r': + { + putc (c, out); + tab_from_to (0, indent); + in_position = out_position = 0; + } + break; + + case '\b': + if (in_position != 0 && --in_position < out_bound) + if (out_position <= in_position) + /* Add spaces to make up for suppressed tab past out_bound. */ + for (; out_position < in_position; out_position++) + putc (' ', out); + else + { + out_position = in_position; + putc (c, out); + } + break; + + case '\f': + case '\v': + control_char: + if (in_position < out_bound) + putc (c, out); + break; + + default: + if (! ISPRINT (c)) + goto control_char; + /* falls through */ + case ' ': + if (in_position++ < out_bound) + { + out_position = in_position; + putc (c, out); + } + break; + + case '\n': + return out_position; + } + } + + return out_position; +} + +/* + * Print side by side lines with a separator in the middle. + * 0 parameters are taken to indicate white space text. + * Blank lines that can easily be caught are reduced to a single newline. + */ + +static void +print_1sdiff_line (left, sep, right) + char const * const *left; + int sep; + char const * const *right; +{ + FILE *out = outfile; + unsigned hw = sdiff_half_width, c2o = sdiff_column2_offset; + unsigned col = 0; + int put_newline = 0; + + if (left) + { + if (left[1][-1] == '\n') + put_newline = 1; + col = print_half_line (left, 0, hw); + } + + if (sep != ' ') + { + col = tab_from_to (col, (hw + c2o - 1) / 2) + 1; + if (sep == '|' && put_newline != (right[1][-1] == '\n')) + sep = put_newline ? '/' : '\\'; + putc (sep, out); + } + + if (right) + { + if (right[1][-1] == '\n') + put_newline = 1; + if (**right != '\n') + { + col = tab_from_to (col, c2o); + print_half_line (right, col, hw); + } + } + + if (put_newline) + putc ('\n', out); +} + +/* Print lines common to both files in side-by-side format. */ +static void +print_sdiff_common_lines (limit0, limit1) + int limit0, limit1; +{ + int i0 = next0, i1 = next1; + + if (! sdiff_skip_common_lines && (i0 != limit0 || i1 != limit1)) + { + if (sdiff_help_sdiff) + fprintf (outfile, "i%d,%d\n", limit0 - i0, limit1 - i1); + + if (! sdiff_left_only) + { + while (i0 != limit0 && i1 != limit1) + print_1sdiff_line (&files[0].linbuf[i0++], ' ', &files[1].linbuf[i1++]); + while (i1 != limit1) + print_1sdiff_line (0, ')', &files[1].linbuf[i1++]); + } + while (i0 != limit0) + print_1sdiff_line (&files[0].linbuf[i0++], '(', 0); + } + + next0 = limit0; + next1 = limit1; +} + +/* Print a hunk of an sdiff diff. + This is a contiguous portion of a complete edit script, + describing changes in consecutive lines. */ + +static void +print_sdiff_hunk (hunk) + struct change *hunk; +{ + int first0, last0, first1, last1, deletes, inserts; + register int i, j; + + /* Determine range of line numbers involved in each file. */ + analyze_hunk (hunk, &first0, &last0, &first1, &last1, &deletes, &inserts); + if (!deletes && !inserts) + return; + + /* Print out lines up to this change. */ + print_sdiff_common_lines (first0, first1); + + if (sdiff_help_sdiff) + fprintf (outfile, "c%d,%d\n", last0 - first0 + 1, last1 - first1 + 1); + + /* Print ``xxx | xxx '' lines */ + if (inserts && deletes) + { + for (i = first0, j = first1; i <= last0 && j <= last1; ++i, ++j) + print_1sdiff_line (&files[0].linbuf[i], '|', &files[1].linbuf[j]); + deletes = i <= last0; + inserts = j <= last1; + next0 = first0 = i; + next1 = first1 = j; + } + + + /* Print `` > xxx '' lines */ + if (inserts) + { + for (j = first1; j <= last1; ++j) + print_1sdiff_line (0, '>', &files[1].linbuf[j]); + next1 = j; + } + + /* Print ``xxx < '' lines */ + if (deletes) + { + for (i = first0; i <= last0; ++i) + print_1sdiff_line (&files[0].linbuf[i], '<', 0); + next0 = i; + } +} diff --git a/contrib/cvs/diff/system.h b/contrib/cvs/diff/system.h new file mode 100644 index 0000000..7812b76 --- /dev/null +++ b/contrib/cvs/diff/system.h @@ -0,0 +1,270 @@ +/* System dependent declarations. + Copyright (C) 1988, 1989, 1992, 1993, 1994 Free Software Foundation, Inc. + +This file is part of GNU DIFF. + +GNU DIFF is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +GNU DIFF is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU DIFF; see the file COPYING. If not, write to +the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ + +/* We must define `volatile' and `const' first (the latter inside config.h), + so that they're used consistently in all system includes. */ +#if !__STDC__ +#ifndef volatile +#define volatile +#endif +#endif +#include <config.h> + +#include <sys/types.h> +#include <sys/stat.h> + +#if __STDC__ +#define PARAMS(args) args +#define VOID void +#else +#define PARAMS(args) () +#define VOID char +#endif + +#if STAT_MACROS_BROKEN +#undef S_ISBLK +#undef S_ISCHR +#undef S_ISDIR +#undef S_ISFIFO +#undef S_ISREG +#undef S_ISSOCK +#endif +#ifndef S_ISDIR +#define S_ISDIR(mode) (((mode) & S_IFMT) == S_IFDIR) +#endif +#ifndef S_ISREG +#define S_ISREG(mode) (((mode) & S_IFMT) == S_IFREG) +#endif +#if !defined(S_ISBLK) && defined(S_IFBLK) +#define S_ISBLK(mode) (((mode) & S_IFMT) == S_IFBLK) +#endif +#if !defined(S_ISCHR) && defined(S_IFCHR) +#define S_ISCHR(mode) (((mode) & S_IFMT) == S_IFCHR) +#endif +#if !defined(S_ISFIFO) && defined(S_IFFIFO) +#define S_ISFIFO(mode) (((mode) & S_IFMT) == S_IFFIFO) +#endif +#if !defined(S_ISSOCK) && defined(S_IFSOCK) +#define S_ISSOCK(mode) (((mode) & S_IFMT) == S_IFSOCK) +#endif + +#if HAVE_UNISTD_H +#include <unistd.h> +#endif + +#ifndef SEEK_SET +#define SEEK_SET 0 +#endif +#ifndef SEEK_CUR +#define SEEK_CUR 1 +#endif + +#ifndef STDIN_FILENO +#define STDIN_FILENO 0 +#endif +#ifndef STDOUT_FILENO +#define STDOUT_FILENO 1 +#endif +#ifndef STDERR_FILENO +#define STDERR_FILENO 2 +#endif + +/* I believe that all relevant systems have + time.h. It is in ANSI, for example. The + code below looks quite bogus as I don't think + sys/time.h is ever a substitute for time.h; + it is something different. */ +#define HAVE_TIME_H 1 + +#if HAVE_TIME_H +#include <time.h> +#else +#include <sys/time.h> +#endif + +#if HAVE_FCNTL_H +#include <fcntl.h> +#else +#if HAVE_SYS_FILE_H +#include <sys/file.h> +#endif +#endif + +#ifndef O_RDONLY +#define O_RDONLY 0 +#endif + +#if HAVE_SYS_WAIT_H +#include <sys/wait.h> +#endif +#ifndef WEXITSTATUS +#define WEXITSTATUS(stat_val) ((unsigned) (stat_val) >> 8) +#endif +#ifndef WIFEXITED +#define WIFEXITED(stat_val) (((stat_val) & 255) == 0) +#endif + +#ifndef STAT_BLOCKSIZE +#if HAVE_ST_BLKSIZE +#define STAT_BLOCKSIZE(s) (s).st_blksize +#else +#define STAT_BLOCKSIZE(s) (8 * 1024) +#endif +#endif + +#if HAVE_DIRENT_H +# include <dirent.h> +# define NAMLEN(dirent) strlen((dirent)->d_name) +#else +# define dirent direct +# define NAMLEN(dirent) ((dirent)->d_namlen) +# if HAVE_SYS_NDIR_H +# include <sys/ndir.h> +# endif +# if HAVE_SYS_DIR_H +# include <sys/dir.h> +# endif +# if HAVE_NDIR_H +# include <ndir.h> +# endif +#endif + +#if HAVE_VFORK_H +#include <vfork.h> +#endif + +#if HAVE_STDLIB_H || defined(STDC_HEADERS) +#include <stdlib.h> +#else +VOID *malloc (); +VOID *realloc (); +#endif +#ifndef getenv +char *getenv (); +#endif + +#if HAVE_LIMITS_H +#include <limits.h> +#endif +#ifndef INT_MAX +#define INT_MAX 2147483647 +#endif +#ifndef CHAR_BIT +#define CHAR_BIT 8 +#endif + +#if STDC_HEADERS || HAVE_STRING_H +# include <string.h> +# ifndef bzero +# define bzero(s, n) memset (s, 0, n) +# endif +#else +# if !HAVE_STRCHR +# define strchr index +# define strrchr rindex +# endif +char *strchr (), *strrchr (); +# if !HAVE_MEMCHR +# define memcmp(s1, s2, n) bcmp (s1, s2, n) +# define memcpy(d, s, n) bcopy (s, d, n) +void *memchr (); +# endif +#endif + +#include <ctype.h> +/* CTYPE_DOMAIN (C) is nonzero if the unsigned char C can safely be given + as an argument to <ctype.h> macros like `isspace'. */ +#if STDC_HEADERS +#define CTYPE_DOMAIN(c) 1 +#else +#define CTYPE_DOMAIN(c) ((unsigned) (c) <= 0177) +#endif +#ifndef ISPRINT +#define ISPRINT(c) (CTYPE_DOMAIN (c) && isprint (c)) +#endif +#ifndef ISSPACE +#define ISSPACE(c) (CTYPE_DOMAIN (c) && isspace (c)) +#endif +#ifndef ISUPPER +#define ISUPPER(c) (CTYPE_DOMAIN (c) && isupper (c)) +#endif + +#ifndef ISDIGIT +#define ISDIGIT(c) ((unsigned) (c) - '0' <= 9) +#endif + +#include <errno.h> +#if !STDC_HEADERS +extern int errno; +#endif + +#ifdef min +#undef min +#endif +#ifdef max +#undef max +#endif +#define min(a,b) ((a) <= (b) ? (a) : (b)) +#define max(a,b) ((a) >= (b) ? (a) : (b)) + +/* This section contains Posix-compliant defaults for macros + that are meant to be overridden by hand in config.h as needed. */ + +#ifndef filename_cmp +#define filename_cmp(a, b) strcmp (a, b) +#endif + +#ifndef filename_lastdirchar +#define filename_lastdirchar(filename) strrchr (filename, '/') +#endif + +#ifndef HAVE_FORK +#define HAVE_FORK 1 +#endif + +#ifndef HAVE_SETMODE +#define HAVE_SETMODE 0 +#endif + +#ifndef initialize_main +#define initialize_main(argcp, argvp) +#endif + +/* Do struct stat *S, *T describe the same file? Answer -1 if unknown. */ +#ifndef same_file +#define same_file(s,t) ((s)->st_ino==(t)->st_ino && (s)->st_dev==(t)->st_dev) +#endif + +/* Place into Q a quoted version of A suitable for `popen' or `system', + incrementing Q and junking A. + Do not increment Q by more than 4 * strlen (A) + 2. */ +#ifndef SYSTEM_QUOTE_ARG +#define SYSTEM_QUOTE_ARG(q, a) \ + { \ + *(q)++ = '\''; \ + for (; *(a); *(q)++ = *(a)++) \ + if (*(a) == '\'') \ + { \ + *(q)++ = '\''; \ + *(q)++ = '\\'; \ + *(q)++ = '\''; \ + } \ + *(q)++ = '\''; \ + } +#endif diff --git a/contrib/cvs/diff/util.c b/contrib/cvs/diff/util.c new file mode 100644 index 0000000..89cc274 --- /dev/null +++ b/contrib/cvs/diff/util.c @@ -0,0 +1,722 @@ +/* Support routines for GNU DIFF. + Copyright (C) 1988, 1989, 1992, 1993, 1994, 1997 Free Software Foundation, Inc. + +This file is part of GNU DIFF. + +GNU DIFF is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +GNU DIFF is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU DIFF; see the file COPYING. If not, write to +the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ + +#include "diff.h" + +/* Queue up one-line messages to be printed at the end, + when -l is specified. Each message is recorded with a `struct msg'. */ + +struct msg +{ + struct msg *next; + char const *format; + char const *arg1; + char const *arg2; + char const *arg3; + char const *arg4; +}; + +/* Head of the chain of queues messages. */ + +static struct msg *msg_chain; + +/* Tail of the chain of queues messages. */ + +static struct msg **msg_chain_end = &msg_chain; + +/* Use when a system call returns non-zero status. + TEXT should normally be the file name. */ + +void +perror_with_name (text) + char const *text; +{ + int e = errno; + fprintf (stderr, "%s: ", diff_program_name); + errno = e; + perror (text); +} + +/* Use when a system call returns non-zero status and that is fatal. */ + +void +pfatal_with_name (text) + char const *text; +{ + int e = errno; + print_message_queue (); + fprintf (stderr, "%s: ", diff_program_name); + errno = e; + perror (text); + DIFF_ABORT (2); +} + +/* Print an error message from the format-string FORMAT + with args ARG1 and ARG2. */ + +void +diff_error (format, arg, arg1) + char const *format, *arg, *arg1; +{ + fprintf (stderr, "%s: ", diff_program_name); + fprintf (stderr, format, arg, arg1); + fprintf (stderr, "\n"); +} + +/* Print an error message containing the string TEXT, then exit. */ + +void +fatal (m) + char const *m; +{ + print_message_queue (); + diff_error ("%s", m, 0); + DIFF_ABORT (2); +} + +/* Like printf, except if -l in effect then save the message and print later. + This is used for things like "binary files differ" and "Only in ...". */ + +void +message (format, arg1, arg2) + char const *format, *arg1, *arg2; +{ + message5 (format, arg1, arg2, 0, 0); +} + +void +message5 (format, arg1, arg2, arg3, arg4) + char const *format, *arg1, *arg2, *arg3, *arg4; +{ + if (paginate_flag) + { + struct msg *new = (struct msg *) xmalloc (sizeof (struct msg)); + new->format = format; + new->arg1 = concat (arg1, "", ""); + new->arg2 = concat (arg2, "", ""); + new->arg3 = arg3 ? concat (arg3, "", "") : 0; + new->arg4 = arg4 ? concat (arg4, "", "") : 0; + new->next = 0; + *msg_chain_end = new; + msg_chain_end = &new->next; + } + else + { + if (sdiff_help_sdiff) + putc (' ', outfile); + fprintf (outfile, format, arg1, arg2, arg3, arg4); + } +} + +/* Output all the messages that were saved up by calls to `message'. */ + +void +print_message_queue () +{ + struct msg *m; + + for (m = msg_chain; m; m = m->next) + fprintf (outfile, m->format, m->arg1, m->arg2, m->arg3, m->arg4); +} + +/* Call before outputting the results of comparing files NAME0 and NAME1 + to set up OUTFILE, the stdio stream for the output to go to. + + Usually, OUTFILE is just stdout. But when -l was specified + we fork off a `pr' and make OUTFILE a pipe to it. + `pr' then outputs to our stdout. */ + +static char const *current_name0; +static char const *current_name1; +static int current_depth; + +static int output_in_progress = 0; + +void +setup_output (name0, name1, depth) + char const *name0, *name1; + int depth; +{ + current_name0 = name0; + current_name1 = name1; + current_depth = depth; +} + +#if HAVE_FORK && defined (PR_PROGRAM) +static pid_t pr_pid; +#endif + +void +begin_output () +{ + char *name; + + if (output_in_progress) + return; + output_in_progress = 1; + + /* Construct the header of this piece of diff. */ + name = xmalloc (strlen (current_name0) + strlen (current_name1) + + strlen (switch_string) + 7); + /* Posix.2 section 4.17.6.1.1 specifies this format. But there is a + bug in the first printing (IEEE Std 1003.2-1992 p 251 l 3304): + it says that we must print only the last component of the pathnames. + This requirement is silly and does not match historical practice. */ + sprintf (name, "diff%s %s %s", switch_string, current_name0, current_name1); + + if (paginate_flag) + { + /* Make OUTFILE a pipe to a subsidiary `pr'. */ + +#ifdef PR_PROGRAM + +# if HAVE_FORK + int pipes[2]; + + if (pipe (pipes) != 0) + pfatal_with_name ("pipe"); + + fflush (stdout); + + pr_pid = vfork (); + if (pr_pid < 0) + pfatal_with_name ("vfork"); + + if (pr_pid == 0) + { + close (pipes[1]); + if (pipes[0] != STDIN_FILENO) + { + if (dup2 (pipes[0], STDIN_FILENO) < 0) + pfatal_with_name ("dup2"); + close (pipes[0]); + } + + execl (PR_PROGRAM, PR_PROGRAM, "-f", "-h", name, 0); + pfatal_with_name (PR_PROGRAM); + } + else + { + close (pipes[0]); + outfile = fdopen (pipes[1], "w"); + if (!outfile) + pfatal_with_name ("fdopen"); + } +# else /* ! HAVE_FORK */ + char *command = xmalloc (4 * strlen (name) + strlen (PR_PROGRAM) + 10); + char *p; + char const *a = name; + sprintf (command, "%s -f -h ", PR_PROGRAM); + p = command + strlen (command); + SYSTEM_QUOTE_ARG (p, a); + *p = 0; + outfile = popen (command, "w"); + if (!outfile) + pfatal_with_name (command); + free (command); +# endif /* ! HAVE_FORK */ +#else + fatal ("This port does not support the --paginate option to diff."); +#endif + } + else + { + + /* If -l was not specified, output the diff straight to `stdout'. */ + + /* If handling multiple files (because scanning a directory), + print which files the following output is about. */ + if (current_depth > 0) + fprintf (outfile, "%s\n", name); + } + + free (name); + + /* A special header is needed at the beginning of context output. */ + switch (output_style) + { + case OUTPUT_CONTEXT: + print_context_header (files, 0); + break; + + case OUTPUT_UNIFIED: + print_context_header (files, 1); + break; + + default: + break; + } +} + +/* Call after the end of output of diffs for one file. + If -l was given, close OUTFILE and get rid of the `pr' subfork. */ + +void +finish_output () +{ + if (paginate_flag && outfile != 0 && outfile != stdout) + { +#ifdef PR_PROGRAM + int wstatus; + if (ferror (outfile)) + fatal ("write error"); +# if ! HAVE_FORK + wstatus = pclose (outfile); +# else /* HAVE_FORK */ + if (fclose (outfile) != 0) + pfatal_with_name ("write error"); + if (waitpid (pr_pid, &wstatus, 0) < 0) + pfatal_with_name ("waitpid"); +# endif /* HAVE_FORK */ + if (wstatus != 0) + fatal ("subsidiary pr failed"); +#else + fatal ("internal error in finish_output"); +#endif + } + + output_in_progress = 0; +} + +/* Compare two lines (typically one from each input file) + according to the command line options. + For efficiency, this is invoked only when the lines do not match exactly + but an option like -i might cause us to ignore the difference. + Return nonzero if the lines differ. */ + +int +line_cmp (s1, s2) + char const *s1, *s2; +{ + register unsigned char const *t1 = (unsigned char const *) s1; + register unsigned char const *t2 = (unsigned char const *) s2; + + while (1) + { + register unsigned char c1 = *t1++; + register unsigned char c2 = *t2++; + + /* Test for exact char equality first, since it's a common case. */ + if (c1 != c2) + { + /* Ignore horizontal white space if -b or -w is specified. */ + + if (ignore_all_space_flag) + { + /* For -w, just skip past any white space. */ + while (ISSPACE (c1) && c1 != '\n') c1 = *t1++; + while (ISSPACE (c2) && c2 != '\n') c2 = *t2++; + } + else if (ignore_space_change_flag) + { + /* For -b, advance past any sequence of white space in line 1 + and consider it just one Space, or nothing at all + if it is at the end of the line. */ + if (ISSPACE (c1)) + { + while (c1 != '\n') + { + c1 = *t1++; + if (! ISSPACE (c1)) + { + --t1; + c1 = ' '; + break; + } + } + } + + /* Likewise for line 2. */ + if (ISSPACE (c2)) + { + while (c2 != '\n') + { + c2 = *t2++; + if (! ISSPACE (c2)) + { + --t2; + c2 = ' '; + break; + } + } + } + + if (c1 != c2) + { + /* If we went too far when doing the simple test + for equality, go back to the first non-white-space + character in both sides and try again. */ + if (c2 == ' ' && c1 != '\n' + && (unsigned char const *) s1 + 1 < t1 + && ISSPACE(t1[-2])) + { + --t1; + continue; + } + if (c1 == ' ' && c2 != '\n' + && (unsigned char const *) s2 + 1 < t2 + && ISSPACE(t2[-2])) + { + --t2; + continue; + } + } + } + + /* Lowercase all letters if -i is specified. */ + + if (ignore_case_flag) + { + if (ISUPPER (c1)) + c1 = tolower (c1); + if (ISUPPER (c2)) + c2 = tolower (c2); + } + + if (c1 != c2) + break; + } + if (c1 == '\n') + return 0; + } + + return (1); +} + +/* Find the consecutive changes at the start of the script START. + Return the last link before the first gap. */ + +struct change * +find_change (start) + struct change *start; +{ + return start; +} + +struct change * +find_reverse_change (start) + struct change *start; +{ + return start; +} + +/* Divide SCRIPT into pieces by calling HUNKFUN and + print each piece with PRINTFUN. + Both functions take one arg, an edit script. + + HUNKFUN is called with the tail of the script + and returns the last link that belongs together with the start + of the tail. + + PRINTFUN takes a subscript which belongs together (with a null + link at the end) and prints it. */ + +void +print_script (script, hunkfun, printfun) + struct change *script; + struct change * (*hunkfun) PARAMS((struct change *)); + void (*printfun) PARAMS((struct change *)); +{ + struct change *next = script; + + while (next) + { + struct change *this, *end; + + /* Find a set of changes that belong together. */ + this = next; + end = (*hunkfun) (next); + + /* Disconnect them from the rest of the changes, + making them a hunk, and remember the rest for next iteration. */ + next = end->link; + end->link = 0; +#ifdef DEBUG + debug_script (this); +#endif + + /* Print this hunk. */ + (*printfun) (this); + + /* Reconnect the script so it will all be freed properly. */ + end->link = next; + } +} + +/* Print the text of a single line LINE, + flagging it with the characters in LINE_FLAG (which say whether + the line is inserted, deleted, changed, etc.). */ + +void +print_1_line (line_flag, line) + char const *line_flag; + char const * const *line; +{ + char const *text = line[0], *limit = line[1]; /* Help the compiler. */ + FILE *out = outfile; /* Help the compiler some more. */ + char const *flag_format = 0; + + /* If -T was specified, use a Tab between the line-flag and the text. + Otherwise use a Space (as Unix diff does). + Print neither space nor tab if line-flags are empty. */ + + if (line_flag && *line_flag) + { + flag_format = tab_align_flag ? "%s\t" : "%s "; + fprintf (out, flag_format, line_flag); + } + + output_1_line (text, limit, flag_format, line_flag); + + if ((!line_flag || line_flag[0]) && limit[-1] != '\n') + fprintf (out, "\n\\ No newline at end of file\n"); +} + +/* Output a line from TEXT up to LIMIT. Without -t, output verbatim. + With -t, expand white space characters to spaces, and if FLAG_FORMAT + is nonzero, output it with argument LINE_FLAG after every + internal carriage return, so that tab stops continue to line up. */ + +void +output_1_line (text, limit, flag_format, line_flag) + char const *text, *limit, *flag_format, *line_flag; +{ + if (!tab_expand_flag) + fwrite (text, sizeof (char), limit - text, outfile); + else + { + register FILE *out = outfile; + register unsigned char c; + register char const *t = text; + register unsigned column = 0; + + while (t < limit) + switch ((c = *t++)) + { + case '\t': + { + unsigned spaces = TAB_WIDTH - column % TAB_WIDTH; + column += spaces; + do + putc (' ', out); + while (--spaces); + } + break; + + case '\r': + putc (c, out); + if (flag_format && t < limit && *t != '\n') + fprintf (out, flag_format, line_flag); + column = 0; + break; + + case '\b': + if (column == 0) + continue; + column--; + putc (c, out); + break; + + default: + if (ISPRINT (c)) + column++; + putc (c, out); + break; + } + } +} + +int +change_letter (inserts, deletes) + int inserts, deletes; +{ + if (!inserts) + return 'd'; + else if (!deletes) + return 'a'; + else + return 'c'; +} + +/* Translate an internal line number (an index into diff's table of lines) + into an actual line number in the input file. + The internal line number is LNUM. FILE points to the data on the file. + + Internal line numbers count from 0 starting after the prefix. + Actual line numbers count from 1 within the entire file. */ + +int +translate_line_number (file, lnum) + struct file_data const *file; + int lnum; +{ + return lnum + file->prefix_lines + 1; +} + +void +translate_range (file, a, b, aptr, bptr) + struct file_data const *file; + int a, b; + int *aptr, *bptr; +{ + *aptr = translate_line_number (file, a - 1) + 1; + *bptr = translate_line_number (file, b + 1) - 1; +} + +/* Print a pair of line numbers with SEPCHAR, translated for file FILE. + If the two numbers are identical, print just one number. + + Args A and B are internal line numbers. + We print the translated (real) line numbers. */ + +void +print_number_range (sepchar, file, a, b) + int sepchar; + struct file_data *file; + int a, b; +{ + int trans_a, trans_b; + translate_range (file, a, b, &trans_a, &trans_b); + + /* Note: we can have B < A in the case of a range of no lines. + In this case, we should print the line number before the range, + which is B. */ + if (trans_b > trans_a) + fprintf (outfile, "%d%c%d", trans_a, sepchar, trans_b); + else + fprintf (outfile, "%d", trans_b); +} + +/* Look at a hunk of edit script and report the range of lines in each file + that it applies to. HUNK is the start of the hunk, which is a chain + of `struct change'. The first and last line numbers of file 0 are stored in + *FIRST0 and *LAST0, and likewise for file 1 in *FIRST1 and *LAST1. + Note that these are internal line numbers that count from 0. + + If no lines from file 0 are deleted, then FIRST0 is LAST0+1. + + Also set *DELETES nonzero if any lines of file 0 are deleted + and set *INSERTS nonzero if any lines of file 1 are inserted. + If only ignorable lines are inserted or deleted, both are + set to 0. */ + +void +analyze_hunk (hunk, first0, last0, first1, last1, deletes, inserts) + struct change *hunk; + int *first0, *last0, *first1, *last1; + int *deletes, *inserts; +{ + int l0, l1, show_from, show_to; + int i; + int trivial = ignore_blank_lines_flag || ignore_regexp_list; + struct change *next; + + show_from = show_to = 0; + + *first0 = hunk->line0; + *first1 = hunk->line1; + + next = hunk; + do + { + l0 = next->line0 + next->deleted - 1; + l1 = next->line1 + next->inserted - 1; + show_from += next->deleted; + show_to += next->inserted; + + for (i = next->line0; i <= l0 && trivial; i++) + if (!ignore_blank_lines_flag || files[0].linbuf[i][0] != '\n') + { + struct regexp_list *r; + char const *line = files[0].linbuf[i]; + int len = files[0].linbuf[i + 1] - line; + + for (r = ignore_regexp_list; r; r = r->next) + if (0 <= re_search (&r->buf, line, len, 0, len, 0)) + break; /* Found a match. Ignore this line. */ + /* If we got all the way through the regexp list without + finding a match, then it's nontrivial. */ + if (!r) + trivial = 0; + } + + for (i = next->line1; i <= l1 && trivial; i++) + if (!ignore_blank_lines_flag || files[1].linbuf[i][0] != '\n') + { + struct regexp_list *r; + char const *line = files[1].linbuf[i]; + int len = files[1].linbuf[i + 1] - line; + + for (r = ignore_regexp_list; r; r = r->next) + if (0 <= re_search (&r->buf, line, len, 0, len, 0)) + break; /* Found a match. Ignore this line. */ + /* If we got all the way through the regexp list without + finding a match, then it's nontrivial. */ + if (!r) + trivial = 0; + } + } + while ((next = next->link) != 0); + + *last0 = l0; + *last1 = l1; + + /* If all inserted or deleted lines are ignorable, + tell the caller to ignore this hunk. */ + + if (trivial) + show_from = show_to = 0; + + *deletes = show_from; + *inserts = show_to; +} + +/* Concatenate three strings, returning a newly malloc'd string. */ + +char * +concat (s1, s2, s3) + char const *s1, *s2, *s3; +{ + size_t len = strlen (s1) + strlen (s2) + strlen (s3); + char *new = xmalloc (len + 1); + sprintf (new, "%s%s%s", s1, s2, s3); + return new; +} + +/* Yield the newly malloc'd pathname + of the file in DIR whose filename is FILE. */ + +char * +dir_file_pathname (dir, file) + char const *dir, *file; +{ + char const *p = filename_lastdirchar (dir); + return concat (dir, "/" + (p && !p[1]), file); +} + +void +debug_script (sp) + struct change *sp; +{ + fflush (stdout); + for (; sp; sp = sp->link) + fprintf (stderr, "%3d %3d delete %d insert %d\n", + sp->line0, sp->line1, sp->deleted, sp->inserted); + fflush (stderr); +} diff --git a/contrib/cvs/diff/version.c b/contrib/cvs/diff/version.c new file mode 100644 index 0000000..343a098 --- /dev/null +++ b/contrib/cvs/diff/version.c @@ -0,0 +1,5 @@ +/* Version number of GNU diff. */ + +#include <config.h> + +char const diff_version_string[] = "2.7"; |