1 /* $OpenBSD: diffreg.c,v 1.91 2016/03/01 20:57:35 natano Exp $ */
4 * Copyright (C) Caldera International Inc. 2001-2002.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
10 * 1. Redistributions of source code and documentation must retain the above
11 * copyright notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 * 3. All advertising materials mentioning features or use of this software
16 * must display the following acknowledgement:
17 * This product includes software developed or owned by Caldera
19 * 4. Neither the name of Caldera International, Inc. nor the names of other
20 * contributors may be used to endorse or promote products derived from
21 * this software without specific prior written permission.
23 * USE OF THE SOFTWARE PROVIDED FOR UNDER THIS LICENSE BY CALDERA
24 * INTERNATIONAL, INC. AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR
25 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
26 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
27 * IN NO EVENT SHALL CALDERA INTERNATIONAL, INC. BE LIABLE FOR ANY DIRECT,
28 * INDIRECT INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
29 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
30 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
32 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
33 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
34 * POSSIBILITY OF SUCH DAMAGE.
37 * Copyright (c) 1991, 1993
38 * The Regents of the University of California. All rights reserved.
40 * Redistribution and use in source and binary forms, with or without
41 * modification, are permitted provided that the following conditions
43 * 1. Redistributions of source code must retain the above copyright
44 * notice, this list of conditions and the following disclaimer.
45 * 2. Redistributions in binary form must reproduce the above copyright
46 * notice, this list of conditions and the following disclaimer in the
47 * documentation and/or other materials provided with the distribution.
48 * 3. Neither the name of the University nor the names of its contributors
49 * may be used to endorse or promote products derived from this software
50 * without specific prior written permission.
52 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
53 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
54 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
55 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
56 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
57 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
58 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
59 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
60 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
61 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
64 * @(#)diffreg.c 8.1 (Berkeley) 6/6/93
69 #include <sys/queue.h>
87 #include "got_error.h"
88 #include "got_object.h"
91 #include "got_lib_diff.h"
93 #define MINIMUM(a, b) (((a) < (b)) ? (a) : (b))
94 #define MAXIMUM(a, b) (((a) > (b)) ? (a) : (b))
97 * diff - compare two files.
101 * Uses an algorithm due to Harold Stone, which finds
102 * a pair of longest identical subsequences in the two
105 * The major goal is to generate the match vector J.
106 * J[i] is the index of the line in file1 corresponding
107 * to line i file0. J[i] = 0 if there is no
108 * such line in file1.
110 * Lines are hashed so as to work in core. All potential
111 * matches are located by sorting the lines of each file
112 * on the hash (called ``value''). In particular, this
113 * collects the equivalence classes in file1 together.
114 * Subroutine equiv replaces the value of each line in
115 * file0 by the index of the first element of its
116 * matching equivalence in (the reordered) file1.
117 * To save space equiv squeezes file1 into a single
118 * array member in which the equivalence classes
119 * are simply concatenated, except that their first
120 * members are flagged by changing sign.
122 * Next the indices that point into member are unsorted into
123 * array class according to the original order of file0.
125 * The cleverness lies in routine stone. This marches
126 * through the lines of file0, developing a vector klist
127 * of "k-candidates". At step i a k-candidate is a matched
128 * pair of lines x,y (x in file0 y in file1) such that
129 * there is a common subsequence of length k
130 * between the first i lines of file0 and the first y
131 * lines of file1, but there is no such subsequence for
132 * any smaller y. x is the earliest possible mate to y
133 * that occurs in such a subsequence.
135 * Whenever any of the members of the equivalence class of
136 * lines in file1 matable to a line in file0 has serial number
137 * less than the y of some k-candidate, that k-candidate
138 * with the smallest such y is replaced. The new
139 * k-candidate is chained (via pred) to the current
140 * k-1 candidate so that the actual subsequence can
141 * be recovered. When a member has serial number greater
142 * that the y of all k-candidates, the klist is extended.
143 * At the end, the longest subsequence is pulled out
144 * and placed in the array J by unravel
146 * With J in hand, the matches there recorded are
147 * check'ed against reality to assure that no spurious
148 * matches have crept in due to hashing. If they have,
149 * they are broken, and "jackpot" is recorded--a harmless
150 * matter except that a true match for a spuriously
151 * mated line may now be unnecessarily reported as a change.
153 * Much of the complexity of the program comes simply
154 * from trying to minimize core utilization and
155 * maximize the range of doable problems by dynamically
156 * allocating what is needed and reusing what is not.
157 * The core requirements for problems larger than somewhat
158 * are (in words) 2*length(file0) + length(file1) +
159 * 3*(number of k-candidates installed), typically about
160 * 6n words for files of length n.
175 * The following struct is used to record change information when
176 * doing a "context" or "unified" diff. (see routine "change" to
177 * understand the highly mnemonic field names)
180 int a; /* start line in old file */
181 int b; /* end line in old file */
182 int c; /* start line in new file */
183 int d; /* end line in new file */
186 static void diff_output(FILE *, const char *, ...);
187 static int output(FILE *, struct got_diff_state *, struct got_diff_args *, const char *, FILE *, const char *, FILE *, int);
188 static void check(struct got_diff_state *, FILE *, FILE *, int);
189 static void range(FILE *, int, int, char *);
190 static void uni_range(FILE *, int, int);
191 static void dump_context_vec(FILE *, struct got_diff_state *, struct got_diff_args *, FILE *, FILE *, int);
192 static void dump_unified_vec(FILE *, struct got_diff_state *, struct got_diff_args *, FILE *, FILE *, int);
193 static int prepare(struct got_diff_state *, int, FILE *, off_t, int);
194 static void prune(struct got_diff_state *);
195 static void equiv(struct line *, int, struct line *, int, int *);
196 static void unravel(struct got_diff_state *, int);
197 static int unsort(struct line *, int, int *);
198 static int change(FILE *, struct got_diff_state *, struct got_diff_args *, const char *, FILE *, const char *, FILE *, int, int, int, int, int *);
199 static void sort(struct line *, int);
200 static void print_header(FILE *, struct got_diff_state *, struct got_diff_args *, const char *, const char *);
201 static int ignoreline(char *);
202 static int asciifile(FILE *);
203 static int fetch(FILE *, struct got_diff_state *, struct got_diff_args *, long *, int, int, FILE *, int, int, int);
204 static int newcand(struct got_diff_state *, int, int, int, int *);
205 static int search(struct got_diff_state *, int *, int, int);
206 static int skipline(FILE *);
207 static int isqrt(int);
208 static int stone(struct got_diff_state *, int *, int, int *, int *, int);
209 static int readhash(struct got_diff_state *, FILE *, int);
210 static int files_differ(struct got_diff_state *, FILE *, FILE *, int);
211 static char *match_function(struct got_diff_state *, const long *, int, FILE *);
212 static char *preadline(int, size_t, off_t);
215 * chrtran points to one of 2 translation tables: cup2low if folding upper to
216 * lower case clow2low if not folding case
218 u_char clow2low[256] = {
219 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a,
220 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15,
221 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20,
222 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b,
223 0x2c, 0x2d, 0x2e, 0x2f, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36,
224 0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, 0x40, 0x41,
225 0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49, 0x4a, 0x4b, 0x4c,
226 0x4d, 0x4e, 0x4f, 0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57,
227 0x58, 0x59, 0x5a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f, 0x60, 0x61, 0x62,
228 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d,
229 0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78,
230 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x80, 0x81, 0x82, 0x83,
231 0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e,
232 0x8f, 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99,
233 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f, 0xa0, 0xa1, 0xa2, 0xa3, 0xa4,
234 0xa5, 0xa6, 0xa7, 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
235 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba,
236 0xbb, 0xbc, 0xbd, 0xbe, 0xbf, 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5,
237 0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, 0xd0,
238 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, 0xdb,
239 0xdc, 0xdd, 0xde, 0xdf, 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6,
240 0xe7, 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef, 0xf0, 0xf1,
241 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, 0xf9, 0xfa, 0xfb, 0xfc,
245 u_char cup2low[256] = {
246 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a,
247 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15,
248 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20,
249 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b,
250 0x2c, 0x2d, 0x2e, 0x2f, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36,
251 0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, 0x60, 0x61,
252 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c,
253 0x6d, 0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
254 0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x60, 0x61, 0x62,
255 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d,
256 0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78,
257 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x80, 0x81, 0x82, 0x83,
258 0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e,
259 0x8f, 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99,
260 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f, 0xa0, 0xa1, 0xa2, 0xa3, 0xa4,
261 0xa5, 0xa6, 0xa7, 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
262 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba,
263 0xbb, 0xbc, 0xbd, 0xbe, 0xbf, 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5,
264 0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, 0xd0,
265 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, 0xdb,
266 0xdc, 0xdd, 0xde, 0xdf, 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6,
267 0xe7, 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef, 0xf0, 0xf1,
268 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, 0xf9, 0xfa, 0xfb, 0xfc,
273 diff_output(FILE *outfile, const char *fmt, ...)
278 vfprintf(outfile, fmt, ap);
282 const struct got_error *
283 got_diffreg(int *rval, FILE *f1, FILE *f2, int flags,
284 struct got_diff_args *args, struct got_diff_state *ds, FILE *outfile)
286 const struct got_error *err = NULL;
292 ds->lastmatchline = 0;
293 ds->context_vec_ptr = ds->context_vec_start - 1;
294 if (flags & D_IGNORECASE)
295 ds->chrtran = cup2low;
297 ds->chrtran = clow2low;
298 if (S_ISDIR(ds->stb1.st_mode) != S_ISDIR(ds->stb2.st_mode)) {
299 *rval = (S_ISDIR(ds->stb1.st_mode) ? D_MISMATCH1 : D_MISMATCH2);
302 if (flags & D_EMPTY1) {
303 f1 = fopen(_PATH_DEVNULL, "r");
305 return got_error_from_errno();
307 else if (f1 == NULL) {
312 if (flags & D_EMPTY2) {
313 f2 = fopen(_PATH_DEVNULL, "r");
315 return got_error_from_errno();
316 } else if (f2 == NULL) {
321 switch (files_differ(ds, f1, f2, flags)) {
332 if ((flags & D_FORCEASCII) == 0 &&
333 (!asciifile(f1) || !asciifile(f2))) {
338 if (prepare(ds, 0, f1, ds->stb1.st_size, flags)) {
339 err = got_error_from_errno();
342 if (prepare(ds, 1, f2, ds->stb2.st_size, flags)) {
343 err = got_error_from_errno();
348 sort(ds->sfile[0], ds->slen[0]);
349 sort(ds->sfile[1], ds->slen[1]);
351 ds->member = (int *)ds->file[1];
352 equiv(ds->sfile[0], ds->slen[0], ds->sfile[1], ds->slen[1], ds->member);
353 ds->member = reallocarray(ds->member, ds->slen[1] + 2, sizeof(*ds->member));
354 if (ds->member == NULL) {
355 err = got_error_from_errno();
359 ds->class = (int *)ds->file[0];
360 if (unsort(ds->sfile[0], ds->slen[0], ds->class)) {
361 err = got_error_from_errno();
364 ds->class = reallocarray(ds->class, ds->slen[0] + 2, sizeof(*ds->class));
365 if (ds->class == NULL) {
366 err = got_error_from_errno();
370 ds->klist = calloc(ds->slen[0] + 2, sizeof(*ds->klist));
371 if (ds->klist == NULL) {
372 err = got_error_from_errno();
377 ds->clist = calloc(ds->clistlen, sizeof(*ds->clist));
378 if (ds->clist == NULL) {
379 err = got_error_from_errno();
382 i = stone(ds, ds->class, ds->slen[0], ds->member, ds->klist, flags);
384 err = got_error_from_errno();
392 ds->J = reallocarray(ds->J, ds->len[0] + 2, sizeof(*ds->J));
394 err = got_error_from_errno();
397 unravel(ds, ds->klist[i]);
403 ds->ixold = reallocarray(ds->ixold, ds->len[0] + 2, sizeof(*ds->ixold));
404 if (ds->ixold == NULL) {
405 err = got_error_from_errno();
408 ds->ixnew = reallocarray(ds->ixnew, ds->len[1] + 2, sizeof(*ds->ixnew));
409 if (ds->ixnew == NULL) {
410 err = got_error_from_errno();
413 check(ds, f1, f2, flags);
414 if (output(outfile, ds, args, args->label[0], f1, args->label[1], f2,
416 err = got_error_from_errno();
432 * Check to see if the given files differ.
433 * Returns 0 if they are the same, 1 if different, and -1 on error.
434 * XXX - could use code from cmp(1) [faster]
437 files_differ(struct got_diff_state *ds, FILE *f1, FILE *f2, int flags)
439 char buf1[BUFSIZ], buf2[BUFSIZ];
442 if ((flags & (D_EMPTY1|D_EMPTY2)) || ds->stb1.st_size != ds->stb2.st_size ||
443 (ds->stb1.st_mode & S_IFMT) != (ds->stb2.st_mode & S_IFMT))
446 i = fread(buf1, 1, sizeof(buf1), f1);
447 j = fread(buf2, 1, sizeof(buf2), f2);
448 if ((!i && ferror(f1)) || (!j && ferror(f2)))
454 if (memcmp(buf1, buf2, i) != 0)
460 prepare(struct got_diff_state *ds, int i, FILE *fd, off_t filesize, int flags)
468 sz = (filesize <= SIZE_MAX ? filesize : SIZE_MAX) / 25;
472 p = calloc(sz + 3, sizeof(*p));
475 for (j = 0; (h = readhash(ds, fd, flags));) {
478 p = reallocarray(p, sz + 3, sizeof(*p));
491 prune(struct got_diff_state *ds)
495 for (ds->pref = 0; ds->pref < ds->len[0] && ds->pref < ds->len[1] &&
496 ds->file[0][ds->pref + 1].value == ds->file[1][ds->pref + 1].value;
499 for (ds->suff = 0; ds->suff < ds->len[0] - ds->pref && ds->suff < ds->len[1] - ds->pref &&
500 ds->file[0][ds->len[0] - ds->suff].value == ds->file[1][ds->len[1] - ds->suff].value;
503 for (j = 0; j < 2; j++) {
504 ds->sfile[j] = ds->file[j] + ds->pref;
505 ds->slen[j] = ds->len[j] - ds->pref - ds->suff;
506 for (i = 0; i <= ds->slen[j]; i++)
507 ds->sfile[j][i].serial = i;
512 equiv(struct line *a, int n, struct line *b, int m, int *c)
517 while (i <= n && j <= m) {
518 if (a[i].value < b[j].value)
520 else if (a[i].value == b[j].value)
531 while (b[j + 1].value == b[j].value) {
539 /* Code taken from ping.c */
548 do { /* newton was a stinker */
553 } while ((x - y) > 1 || (x - y) < -1);
559 stone(struct got_diff_state *ds, int *a, int n, int *b, int *c, int flags)
562 int oldc, tc, oldl, sq;
563 u_int numtries, bound;
566 if (flags & D_MINIMAL)
570 bound = MAXIMUM(256, sq);
574 c[0] = newcand(ds, 0, 0, 0, &error);
577 for (i = 1; i <= n; i++) {
586 if (y <= ds->clist[oldc].y)
588 l = search(ds, c, k, y);
592 if (ds->clist[c[l]].y <= y)
595 c[l] = newcand(ds, i, y, oldc, &error);
602 c[l] = newcand(ds, i, y, oldc, &error);
608 } while ((y = b[++j]) > 0 && numtries < bound);
614 newcand(struct got_diff_state *ds, int x, int y, int pred, int *errorp)
618 if (ds->clen == ds->clistlen) {
619 ds->clistlen = ds->clistlen * 11 / 10;
620 ds->clist = reallocarray(ds->clist, ds->clistlen,
622 if (ds->clist == NULL) {
627 q = ds->clist + ds->clen;
636 search(struct got_diff_state *ds, int *c, int k, int y)
640 if (ds->clist[c[k]].y < y) /* quick look for typical case */
648 t = ds->clist[c[l]].y;
660 unravel(struct got_diff_state *ds, int p)
665 for (i = 0; i <= ds->len[0]; i++)
666 ds->J[i] = i <= ds->pref ? i :
667 i > ds->len[0] - ds->suff ? i + ds->len[1] - ds->len[0] : 0;
668 for (q = ds->clist + p; q->y != 0; q = ds->clist + q->pred)
669 ds->J[q->x + ds->pref] = q->y + ds->pref;
673 * Check does double duty:
674 * 1. ferret out any fortuitous correspondences due
675 * to confounding by hashing (which result in "jackpot")
676 * 2. collect random access indexes to the two files
679 check(struct got_diff_state *ds, FILE *f1, FILE *f2, int flags)
681 int i, j, jackpot, c, d;
687 ds->ixold[0] = ds->ixnew[0] = 0;
690 for (i = 1; i <= ds->len[0]; i++) {
692 ds->ixold[i] = ctold += skipline(f1);
695 while (j < ds->J[i]) {
696 ds->ixnew[j] = ctnew += skipline(f2);
699 if (flags & (D_FOLDBLANKS|D_IGNOREBLANKS|D_IGNORECASE)) {
704 * GNU diff ignores a missing newline
705 * in one file for -b or -w.
707 if (flags & (D_FOLDBLANKS|D_IGNOREBLANKS)) {
708 if (c == EOF && d == '\n') {
711 } else if (c == '\n' && d == EOF) {
718 if ((flags & D_FOLDBLANKS) && isspace(c) &&
724 } while (isspace(c = getc(f1)));
729 } while (isspace(d = getc(f2)));
730 } else if ((flags & D_IGNOREBLANKS)) {
731 while (isspace(c) && c != '\n') {
735 while (isspace(d) && d != '\n') {
740 if (ds->chrtran[c] != ds->chrtran[d]) {
743 if (c != '\n' && c != EOF)
744 ctold += skipline(f1);
745 if (d != '\n' && c != EOF)
746 ctnew += skipline(f2);
749 if (c == '\n' || c == EOF)
756 if ((c = getc(f1)) != (d = getc(f2))) {
759 if (c != '\n' && c != EOF)
760 ctold += skipline(f1);
761 if (d != '\n' && c != EOF)
762 ctnew += skipline(f2);
765 if (c == '\n' || c == EOF)
769 ds->ixold[i] = ctold;
770 ds->ixnew[j] = ctnew;
773 for (; j <= ds->len[1]; j++)
774 ds->ixnew[j] = ctnew += skipline(f2);
777 * fprintf(stderr, "jackpot\n");
781 /* shellsort CACM #201 */
783 sort(struct line *a, int n)
785 struct line *ai, *aim, w;
790 for (j = 1; j <= n; j *= 2)
792 for (m /= 2; m != 0; m /= 2) {
794 for (j = 1; j <= k; j++) {
795 for (ai = &a[j]; ai > a; ai -= m) {
798 break; /* wraparound */
799 if (aim->value > ai[0].value ||
800 (aim->value == ai[0].value &&
801 aim->serial > ai[0].serial))
803 w.value = ai[0].value;
804 ai[0].value = aim->value;
805 aim->value = w.value;
806 w.serial = ai[0].serial;
807 ai[0].serial = aim->serial;
808 aim->serial = w.serial;
815 unsort(struct line *f, int l, int *b)
819 a = calloc(l + 1, sizeof(*a));
822 for (i = 1; i <= l; i++)
823 a[f[i].serial] = f[i].value;
824 for (i = 1; i <= l; i++)
836 for (i = 1; (c = getc(f)) != '\n' && c != EOF; i++)
842 output(FILE *outfile, struct got_diff_state *ds, struct got_diff_args *args,
843 const char *file1, FILE *f1, const char *file2, FILE *f2, int flags)
845 int m, i0, i1, j0, j1;
852 ds->J[m + 1] = ds->len[1] + 1;
853 if (args->diff_format != D_EDIT) {
854 for (i0 = 1; i0 <= m; i0 = i1 + 1) {
855 while (i0 <= m && ds->J[i0] == ds->J[i0 - 1] + 1)
857 j0 = ds->J[i0 - 1] + 1;
859 while (i1 < m && ds->J[i1 + 1] == 0)
861 j1 = ds->J[i1 + 1] - 1;
863 error = change(outfile, ds, args, file1, f1, file2, f2,
864 i0, i1, j0, j1, &flags);
869 for (i0 = m; i0 >= 1; i0 = i1 - 1) {
870 while (i0 >= 1 && ds->J[i0] == ds->J[i0 + 1] - 1 && ds->J[i0] != 0)
872 j0 = ds->J[i0 + 1] - 1;
874 while (i1 > 1 && ds->J[i1 - 1] == 0)
876 j1 = ds->J[i1 - 1] + 1;
878 change(outfile, ds, args, file1, f1, file2, f2, i1, i0,
885 error = change(outfile, ds, args, file1, f1, file2, f2, 1, 0,
886 1, ds->len[1], &flags);
890 if (args->diff_format == D_IFDEF) {
893 if ((c = getc(f1)) == EOF)
895 diff_output(outfile, "%c", c);
899 if (ds->anychange != 0) {
900 if (args->diff_format == D_CONTEXT)
901 dump_context_vec(outfile, ds, args, f1, f2, flags);
902 else if (args->diff_format == D_UNIFIED)
903 dump_unified_vec(outfile, ds, args, f1, f2, flags);
910 range(FILE *outfile, int a, int b, char *separator)
912 diff_output(outfile, "%d", a > b ? b : a);
914 diff_output(outfile, "%s%d", separator, b);
918 uni_range(FILE *outfile, int a, int b)
921 diff_output(outfile, "%d,%d", a, b - a + 1);
923 diff_output(outfile, "%d", b);
925 diff_output(outfile, "%d,0", b);
929 preadline(int fd, size_t rlen, off_t off)
934 line = malloc(rlen + 1);
937 if ((nr = pread(fd, line, rlen, off)) < 0) {
941 if (nr > 0 && line[nr-1] == '\n')
948 ignoreline(char *line)
950 return 0; /* do not ignore any lines */
954 * Indicate that there is a difference between lines a and b of the from file
955 * to get to lines c to d of the to file. If a is greater then b then there
956 * are no lines in the from file involved and this means that there were
957 * lines appended (beginning at b). If c is greater than d then there are
958 * lines missing from the to file.
961 change(FILE *outfile, struct got_diff_state *ds, struct got_diff_args *args,
962 const char *file1, FILE *f1, const char *file2, FILE *f2,
963 int a, int b, int c, int d, int *pflags)
965 size_t max_context = 64;
969 if (args->diff_format != D_IFDEF && a > b && c > d)
971 if (args->ignore_pats != NULL) {
974 * All lines in the change, insert, or delete must
975 * match an ignore pattern for the change to be
978 if (a <= b) { /* Changes and deletes. */
979 for (i = a; i <= b; i++) {
980 line = preadline(fileno(f1),
981 ds->ixold[i] - ds->ixold[i - 1],
985 if (!ignoreline(line))
989 if (a > b || c <= d) { /* Changes and inserts. */
990 for (i = c; i <= d; i++) {
991 line = preadline(fileno(f2),
992 ds->ixnew[i] - ds->ixnew[i - 1],
996 if (!ignoreline(line))
1003 if (*pflags & D_HEADER) {
1004 diff_output(outfile, "%s %s %s\n", args->diffargs, file1, file2);
1005 *pflags &= ~D_HEADER;
1007 if (args->diff_format == D_CONTEXT || args->diff_format == D_UNIFIED) {
1009 * Allocate change records as needed.
1011 if (ds->context_vec_ptr == ds->context_vec_end - 1) {
1012 ptrdiff_t offset = ds->context_vec_ptr - ds->context_vec_start;
1014 ds->context_vec_start =
1015 reallocarray(ds->context_vec_start, max_context,
1016 sizeof(*ds->context_vec_start));
1017 if (ds->context_vec_start == NULL)
1019 ds->context_vec_end = ds->context_vec_start + max_context;
1020 ds->context_vec_ptr = ds->context_vec_start + offset;
1022 if (ds->anychange == 0) {
1024 * Print the context/unidiff header first time through.
1026 print_header(outfile, ds, args, file1, file2);
1028 } else if (a > ds->context_vec_ptr->b + (2 * args->diff_context) + 1 &&
1029 c > ds->context_vec_ptr->d + (2 * args->diff_context) + 1) {
1031 * If this change is more than 'diff_context' lines from the
1032 * previous change, dump the record and reset it.
1034 if (args->diff_format == D_CONTEXT)
1035 dump_context_vec(outfile, ds, args, f1, f2, *pflags);
1037 dump_unified_vec(outfile, ds, args, f1, f2, *pflags);
1039 ds->context_vec_ptr++;
1040 ds->context_vec_ptr->a = a;
1041 ds->context_vec_ptr->b = b;
1042 ds->context_vec_ptr->c = c;
1043 ds->context_vec_ptr->d = d;
1046 if (ds->anychange == 0)
1048 switch (args->diff_format) {
1053 range(outfile, a, b, ",");
1054 diff_output(outfile, "%c", a > b ? 'a' : c > d ? 'd' : 'c');
1055 if (args->diff_format == D_NORMAL)
1056 range(outfile, c, d, ",");
1057 diff_output(outfile, "\n");
1060 diff_output(outfile, "%c", a > b ? 'a' : c > d ? 'd' : 'c');
1061 range(outfile, a, b, " ");
1062 diff_output(outfile, "\n");
1066 diff_output(outfile, "a%d %d\n", b, d - c + 1);
1068 diff_output(outfile, "d%d %d\n", a, b - a + 1);
1070 /* add changed lines */
1071 diff_output(outfile, "a%d %d\n", b, d - c + 1);
1075 if (args->diff_format == D_NORMAL || args->diff_format == D_IFDEF) {
1076 fetch(outfile, ds, args, ds->ixold, a, b, f1, '<', 1, *pflags);
1077 if (a <= b && c <= d && args->diff_format == D_NORMAL)
1078 diff_output(outfile, "---\n");
1080 i = fetch(outfile, ds, args, ds->ixnew, c, d, f2, args->diff_format == D_NORMAL ? '>' : '\0', 0, *pflags);
1081 if (i != 0 && args->diff_format == D_EDIT) {
1083 * A non-zero return value for D_EDIT indicates that the
1084 * last line printed was a bare dot (".") that has been
1085 * escaped as ".." to prevent ed(1) from misinterpreting
1086 * it. We have to add a substitute command to change this
1087 * back and restart where we left off.
1089 diff_output(outfile, ".\n");
1090 diff_output(outfile, "%ds/.//\n", a + i - 1);
1096 if ((args->diff_format == D_EDIT || args->diff_format == D_REVERSE) && c <= d)
1097 diff_output(outfile, ".\n");
1099 diff_output(outfile, "#endif /* %s */\n", args->ifdefname);
1107 fetch(FILE *outfile, struct got_diff_state *ds, struct got_diff_args *args,
1108 long *f, int a, int b, FILE *lb, int ch, int oldfile, int flags)
1110 int i, j, c, lastc, col, nc;
1113 * When doing #ifdef's, copy down to current line
1114 * if this is the first file, so that stuff makes it to output.
1116 if (args->diff_format == D_IFDEF && oldfile) {
1117 long curpos = ftell(lb);
1118 /* print through if append (a>b), else to (nb: 0 vs 1 orig) */
1119 nc = f[a > b ? b : a - 1] - curpos;
1120 for (i = 0; i < nc; i++)
1121 diff_output(outfile, "%c", getc(lb));
1125 if (args->diff_format == D_IFDEF) {
1127 diff_output(outfile, "#else /* %s%s */\n",
1128 oldfile == 1 ? "!" : "", args->ifdefname);
1131 diff_output(outfile, "#ifndef %s\n", args->ifdefname);
1133 diff_output(outfile, "#ifdef %s\n", args->ifdefname);
1135 ds->inifdef = 1 + oldfile;
1137 for (i = a; i <= b; i++) {
1138 fseek(lb, f[i - 1], SEEK_SET);
1139 nc = f[i] - f[i - 1];
1140 if (args->diff_format != D_IFDEF && ch != '\0') {
1141 diff_output(outfile, "%c", ch);
1142 if (args->Tflag && (args->diff_format == D_NORMAL || args->diff_format == D_CONTEXT
1143 || args->diff_format == D_UNIFIED))
1144 diff_output(outfile, "\t");
1145 else if (args->diff_format != D_UNIFIED)
1146 diff_output(outfile, " ");
1149 for (j = 0, lastc = '\0'; j < nc; j++, lastc = c) {
1150 if ((c = getc(lb)) == EOF) {
1151 if (args->diff_format == D_EDIT || args->diff_format == D_REVERSE ||
1152 args->diff_format == D_NREVERSE)
1153 warnx("No newline at end of file");
1155 diff_output(outfile, "\n\\ No newline at end of "
1159 if (c == '\t' && (flags & D_EXPANDTABS)) {
1161 diff_output(outfile, " ");
1162 } while (++col & 7);
1164 if (args->diff_format == D_EDIT && j == 1 && c == '\n'
1167 * Don't print a bare "." line
1168 * since that will confuse ed(1).
1169 * Print ".." instead and return,
1170 * giving the caller an offset
1171 * from which to restart.
1173 diff_output(outfile, ".\n");
1176 diff_output(outfile, "%c", c);
1185 * Hash function taken from Robert Sedgewick, Algorithms in C, 3d ed., p 578.
1188 readhash(struct got_diff_state *ds, FILE *f, int flags)
1195 if ((flags & (D_FOLDBLANKS|D_IGNOREBLANKS)) == 0) {
1196 if (flags & D_IGNORECASE)
1197 for (i = 0; (t = getc(f)) != '\n'; i++) {
1203 sum = sum * 127 + ds->chrtran[t];
1206 for (i = 0; (t = getc(f)) != '\n'; i++) {
1212 sum = sum * 127 + t;
1216 switch (t = getc(f)) {
1225 if (space && (flags & D_IGNOREBLANKS) == 0) {
1229 sum = sum * 127 + ds->chrtran[t];
1243 * There is a remote possibility that we end up with a zero sum.
1244 * Zero is used as an EOF marker, so return 1 instead.
1246 return (sum == 0 ? 1 : sum);
1252 unsigned char buf[BUFSIZ];
1259 cnt = fread(buf, 1, sizeof(buf), f);
1260 return (memchr(buf, '\0', cnt) == NULL);
1263 #define begins_with(s, pre) (strncmp(s, pre, sizeof(pre)-1) == 0)
1266 match_function(struct got_diff_state *ds, const long *f, int pos, FILE *fp)
1268 unsigned char buf[FUNCTION_CONTEXT_SIZE];
1270 int last = ds->lastline;
1274 while (pos > last) {
1275 fseek(fp, f[pos - 1], SEEK_SET);
1276 nc = f[pos] - f[pos - 1];
1277 if (nc >= sizeof(buf))
1278 nc = sizeof(buf) - 1;
1279 nc = fread(buf, 1, nc, fp);
1282 buf[strcspn(buf, "\n")] = '\0';
1283 if (isalpha(buf[0]) || buf[0] == '_' || buf[0] == '$') {
1284 if (begins_with(buf, "private:")) {
1286 state = " (private)";
1287 } else if (begins_with(buf, "protected:")) {
1289 state = " (protected)";
1290 } else if (begins_with(buf, "public:")) {
1292 state = " (public)";
1294 strlcpy(ds->lastbuf, buf, sizeof ds->lastbuf);
1296 strlcat(ds->lastbuf, state,
1297 sizeof ds->lastbuf);
1298 ds->lastmatchline = pos;
1305 return ds->lastmatchline > 0 ? ds->lastbuf : NULL;
1308 /* dump accumulated "context" diff changes */
1310 dump_context_vec(FILE *outfile, struct got_diff_state *ds, struct got_diff_args *args,
1311 FILE *f1, FILE *f2, int flags)
1313 struct context_vec *cvp = ds->context_vec_start;
1314 int lowa, upb, lowc, upd, do_output;
1318 if (ds->context_vec_start > ds->context_vec_ptr)
1321 b = d = 0; /* gcc */
1322 lowa = MAXIMUM(1, cvp->a - args->diff_context);
1323 upb = MINIMUM(ds->len[0], ds->context_vec_ptr->b + args->diff_context);
1324 lowc = MAXIMUM(1, cvp->c - args->diff_context);
1325 upd = MINIMUM(ds->len[1], ds->context_vec_ptr->d + args->diff_context);
1327 diff_output(outfile, "***************");
1328 if ((flags & D_PROTOTYPE)) {
1329 f = match_function(ds, ds->ixold, lowa-1, f1);
1331 diff_output(outfile, " %s", f);
1333 diff_output(outfile, "\n*** ");
1334 range(outfile, lowa, upb, ",");
1335 diff_output(outfile, " ****\n");
1338 * Output changes to the "old" file. The first loop suppresses
1339 * output if there were no changes to the "old" file (we'll see
1340 * the "old" lines as context in the "new" list).
1343 for (; cvp <= ds->context_vec_ptr; cvp++)
1344 if (cvp->a <= cvp->b) {
1345 cvp = ds->context_vec_start;
1350 while (cvp <= ds->context_vec_ptr) {
1356 if (a <= b && c <= d)
1359 ch = (a <= b) ? 'd' : 'a';
1362 fetch(outfile, ds, args, ds->ixold, lowa, b, f1, ' ', 0, flags);
1364 fetch(outfile, ds, args, ds->ixold, lowa, a - 1, f1, ' ', 0, flags);
1365 fetch(outfile, ds, args, ds->ixold, a, b, f1,
1366 ch == 'c' ? '!' : '-', 0, flags);
1371 fetch(outfile, ds, args, ds->ixold, b + 1, upb, f1, ' ', 0, flags);
1373 /* output changes to the "new" file */
1374 diff_output(outfile, "--- ");
1375 range(outfile, lowc, upd, ",");
1376 diff_output(outfile, " ----\n");
1379 for (cvp = ds->context_vec_start; cvp <= ds->context_vec_ptr; cvp++)
1380 if (cvp->c <= cvp->d) {
1381 cvp = ds->context_vec_start;
1386 while (cvp <= ds->context_vec_ptr) {
1392 if (a <= b && c <= d)
1395 ch = (a <= b) ? 'd' : 'a';
1398 fetch(outfile, ds, args, ds->ixnew, lowc, d, f2, ' ', 0, flags);
1400 fetch(outfile, ds, args, ds->ixnew, lowc, c - 1, f2, ' ', 0, flags);
1401 fetch(outfile, ds, args, ds->ixnew, c, d, f2,
1402 ch == 'c' ? '!' : '+', 0, flags);
1407 fetch(outfile, ds, args, ds->ixnew, d + 1, upd, f2, ' ', 0, flags);
1409 ds->context_vec_ptr = ds->context_vec_start - 1;
1412 /* dump accumulated "unified" diff changes */
1414 dump_unified_vec(FILE *outfile, struct got_diff_state *ds, struct got_diff_args *args,
1415 FILE *f1, FILE *f2, int flags)
1417 struct context_vec *cvp = ds->context_vec_start;
1418 int lowa, upb, lowc, upd;
1422 if (ds->context_vec_start > ds->context_vec_ptr)
1425 b = d = 0; /* gcc */
1426 lowa = MAXIMUM(1, cvp->a - args->diff_context);
1427 upb = MINIMUM(ds->len[0], ds->context_vec_ptr->b + args->diff_context);
1428 lowc = MAXIMUM(1, cvp->c - args->diff_context);
1429 upd = MINIMUM(ds->len[1], ds->context_vec_ptr->d + args->diff_context);
1431 diff_output(outfile, "@@ -");
1432 uni_range(outfile, lowa, upb);
1433 diff_output(outfile, " +");
1434 uni_range(outfile, lowc, upd);
1435 diff_output(outfile, " @@");
1436 if ((flags & D_PROTOTYPE)) {
1437 f = match_function(ds, ds->ixold, lowa-1, f1);
1439 diff_output(outfile, " %s", f);
1441 diff_output(outfile, "\n");
1444 * Output changes in "unified" diff format--the old and new lines
1445 * are printed together.
1447 for (; cvp <= ds->context_vec_ptr; cvp++) {
1454 * c: both new and old changes
1455 * d: only changes in the old file
1456 * a: only changes in the new file
1458 if (a <= b && c <= d)
1461 ch = (a <= b) ? 'd' : 'a';
1465 fetch(outfile, ds, args, ds->ixold, lowa, a - 1, f1, ' ', 0, flags);
1466 fetch(outfile, ds, args, ds->ixold, a, b, f1, '-', 0, flags);
1467 fetch(outfile, ds, args, ds->ixnew, c, d, f2, '+', 0, flags);
1470 fetch(outfile, ds, args, ds->ixold, lowa, a - 1, f1, ' ', 0, flags);
1471 fetch(outfile, ds, args, ds->ixold, a, b, f1, '-', 0, flags);
1474 fetch(outfile, ds, args, ds->ixnew, lowc, c - 1, f2, ' ', 0, flags);
1475 fetch(outfile, ds, args, ds->ixnew, c, d, f2, '+', 0, flags);
1481 fetch(outfile, ds, args, ds->ixnew, d + 1, upd, f2, ' ', 0, flags);
1483 ds->context_vec_ptr = ds->context_vec_start - 1;
1487 print_header(FILE *outfile, struct got_diff_state *ds, struct got_diff_args *args,
1488 const char *file1, const char *file2)
1490 if (args->label[0] != NULL)
1491 diff_output(outfile, "%s %s\n", args->diff_format == D_CONTEXT ? "***" : "---",
1494 diff_output(outfile, "%s %s\t%s", args->diff_format == D_CONTEXT ? "***" : "---",
1495 file1, ctime(&ds->stb1.st_mtime));
1496 if (args->label[1] != NULL)
1497 diff_output(outfile, "%s %s\n", args->diff_format == D_CONTEXT ? "---" : "+++",
1500 diff_output(outfile, "%s %s\t%s", args->diff_format == D_CONTEXT ? "---" : "+++",
1501 file2, ctime(&ds->stb2.st_mtime));