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