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 err = got_error_from_errno();
309 else if (f1 == NULL) {
314 if (flags & D_EMPTY2) {
315 f2 = fopen(_PATH_DEVNULL, "r");
317 err = got_error_from_errno();
320 } else if (f2 == NULL) {
325 switch (files_differ(ds, f1, f2, flags)) {
336 if ((flags & D_FORCEASCII) == 0 &&
337 (!asciifile(f1) || !asciifile(f2))) {
342 if (prepare(ds, 0, f1, ds->stb1.st_size, flags)) {
343 err = got_error_from_errno();
346 if (prepare(ds, 1, f2, ds->stb2.st_size, flags)) {
347 err = got_error_from_errno();
352 sort(ds->sfile[0], ds->slen[0]);
353 sort(ds->sfile[1], ds->slen[1]);
355 ds->member = (int *)ds->file[1];
356 equiv(ds->sfile[0], ds->slen[0], ds->sfile[1], ds->slen[1], ds->member);
357 ds->member = reallocarray(ds->member, ds->slen[1] + 2, sizeof(*ds->member));
358 if (ds->member == NULL) {
359 err = got_error_from_errno();
363 ds->class = (int *)ds->file[0];
364 if (unsort(ds->sfile[0], ds->slen[0], ds->class)) {
365 err = got_error_from_errno();
368 ds->class = reallocarray(ds->class, ds->slen[0] + 2, sizeof(*ds->class));
369 if (ds->class == NULL) {
370 err = got_error_from_errno();
374 ds->klist = calloc(ds->slen[0] + 2, sizeof(*ds->klist));
375 if (ds->klist == NULL) {
376 err = got_error_from_errno();
381 ds->clist = calloc(ds->clistlen, sizeof(*ds->clist));
382 if (ds->clist == NULL) {
383 err = got_error_from_errno();
386 i = stone(ds, ds->class, ds->slen[0], ds->member, ds->klist, flags);
388 err = got_error_from_errno();
396 ds->J = reallocarray(ds->J, ds->len[0] + 2, sizeof(*ds->J));
398 err = got_error_from_errno();
401 unravel(ds, ds->klist[i]);
407 ds->ixold = reallocarray(ds->ixold, ds->len[0] + 2, sizeof(*ds->ixold));
408 if (ds->ixold == NULL) {
409 err = got_error_from_errno();
412 ds->ixnew = reallocarray(ds->ixnew, ds->len[1] + 2, sizeof(*ds->ixnew));
413 if (ds->ixnew == NULL) {
414 err = got_error_from_errno();
417 check(ds, f1, f2, flags);
418 if (output(outfile, ds, args, args->label[0], f1, args->label[1], f2,
420 err = got_error_from_errno();
436 * Check to see if the given files differ.
437 * Returns 0 if they are the same, 1 if different, and -1 on error.
438 * XXX - could use code from cmp(1) [faster]
441 files_differ(struct got_diff_state *ds, FILE *f1, FILE *f2, int flags)
443 char buf1[BUFSIZ], buf2[BUFSIZ];
446 if ((flags & (D_EMPTY1|D_EMPTY2)) || ds->stb1.st_size != ds->stb2.st_size ||
447 (ds->stb1.st_mode & S_IFMT) != (ds->stb2.st_mode & S_IFMT))
450 i = fread(buf1, 1, sizeof(buf1), f1);
451 j = fread(buf2, 1, sizeof(buf2), f2);
452 if ((!i && ferror(f1)) || (!j && ferror(f2)))
458 if (memcmp(buf1, buf2, i) != 0)
464 prepare(struct got_diff_state *ds, int i, FILE *fd, off_t filesize, int flags)
472 sz = (filesize <= SIZE_MAX ? filesize : SIZE_MAX) / 25;
476 p = calloc(sz + 3, sizeof(*p));
479 for (j = 0; (h = readhash(ds, fd, flags));) {
482 p = reallocarray(p, sz + 3, sizeof(*p));
495 prune(struct got_diff_state *ds)
499 for (ds->pref = 0; ds->pref < ds->len[0] && ds->pref < ds->len[1] &&
500 ds->file[0][ds->pref + 1].value == ds->file[1][ds->pref + 1].value;
503 for (ds->suff = 0; ds->suff < ds->len[0] - ds->pref && ds->suff < ds->len[1] - ds->pref &&
504 ds->file[0][ds->len[0] - ds->suff].value == ds->file[1][ds->len[1] - ds->suff].value;
507 for (j = 0; j < 2; j++) {
508 ds->sfile[j] = ds->file[j] + ds->pref;
509 ds->slen[j] = ds->len[j] - ds->pref - ds->suff;
510 for (i = 0; i <= ds->slen[j]; i++)
511 ds->sfile[j][i].serial = i;
516 equiv(struct line *a, int n, struct line *b, int m, int *c)
521 while (i <= n && j <= m) {
522 if (a[i].value < b[j].value)
524 else if (a[i].value == b[j].value)
535 while (b[j + 1].value == b[j].value) {
543 /* Code taken from ping.c */
552 do { /* newton was a stinker */
557 } while ((x - y) > 1 || (x - y) < -1);
563 stone(struct got_diff_state *ds, int *a, int n, int *b, int *c, int flags)
566 int oldc, tc, oldl, sq;
567 u_int numtries, bound;
570 if (flags & D_MINIMAL)
574 bound = MAXIMUM(256, sq);
578 c[0] = newcand(ds, 0, 0, 0, &error);
581 for (i = 1; i <= n; i++) {
590 if (y <= ds->clist[oldc].y)
592 l = search(ds, c, k, y);
596 if (ds->clist[c[l]].y <= y)
599 c[l] = newcand(ds, i, y, oldc, &error);
606 c[l] = newcand(ds, i, y, oldc, &error);
612 } while ((y = b[++j]) > 0 && numtries < bound);
618 newcand(struct got_diff_state *ds, int x, int y, int pred, int *errorp)
622 if (ds->clen == ds->clistlen) {
623 ds->clistlen = ds->clistlen * 11 / 10;
624 ds->clist = reallocarray(ds->clist, ds->clistlen,
626 if (ds->clist == NULL) {
631 q = ds->clist + ds->clen;
640 search(struct got_diff_state *ds, int *c, int k, int y)
644 if (ds->clist[c[k]].y < y) /* quick look for typical case */
652 t = ds->clist[c[l]].y;
664 unravel(struct got_diff_state *ds, int p)
669 for (i = 0; i <= ds->len[0]; i++)
670 ds->J[i] = i <= ds->pref ? i :
671 i > ds->len[0] - ds->suff ? i + ds->len[1] - ds->len[0] : 0;
672 for (q = ds->clist + p; q->y != 0; q = ds->clist + q->pred)
673 ds->J[q->x + ds->pref] = q->y + ds->pref;
677 * Check does double duty:
678 * 1. ferret out any fortuitous correspondences due
679 * to confounding by hashing (which result in "jackpot")
680 * 2. collect random access indexes to the two files
683 check(struct got_diff_state *ds, FILE *f1, FILE *f2, int flags)
685 int i, j, jackpot, c, d;
691 ds->ixold[0] = ds->ixnew[0] = 0;
694 for (i = 1; i <= ds->len[0]; i++) {
696 ds->ixold[i] = ctold += skipline(f1);
699 while (j < ds->J[i]) {
700 ds->ixnew[j] = ctnew += skipline(f2);
703 if (flags & (D_FOLDBLANKS|D_IGNOREBLANKS|D_IGNORECASE)) {
708 * GNU diff ignores a missing newline
709 * in one file for -b or -w.
711 if (flags & (D_FOLDBLANKS|D_IGNOREBLANKS)) {
712 if (c == EOF && d == '\n') {
715 } else if (c == '\n' && d == EOF) {
722 if ((flags & D_FOLDBLANKS) && isspace(c) &&
728 } while (isspace(c = getc(f1)));
733 } while (isspace(d = getc(f2)));
734 } else if ((flags & D_IGNOREBLANKS)) {
735 while (isspace(c) && c != '\n') {
739 while (isspace(d) && d != '\n') {
744 if (ds->chrtran[c] != ds->chrtran[d]) {
747 if (c != '\n' && c != EOF)
748 ctold += skipline(f1);
749 if (d != '\n' && c != EOF)
750 ctnew += skipline(f2);
753 if (c == '\n' || c == EOF)
760 if ((c = getc(f1)) != (d = getc(f2))) {
763 if (c != '\n' && c != EOF)
764 ctold += skipline(f1);
765 if (d != '\n' && c != EOF)
766 ctnew += skipline(f2);
769 if (c == '\n' || c == EOF)
773 ds->ixold[i] = ctold;
774 ds->ixnew[j] = ctnew;
777 for (; j <= ds->len[1]; j++)
778 ds->ixnew[j] = ctnew += skipline(f2);
781 * fprintf(stderr, "jackpot\n");
785 /* shellsort CACM #201 */
787 sort(struct line *a, int n)
789 struct line *ai, *aim, w;
794 for (j = 1; j <= n; j *= 2)
796 for (m /= 2; m != 0; m /= 2) {
798 for (j = 1; j <= k; j++) {
799 for (ai = &a[j]; ai > a; ai -= m) {
802 break; /* wraparound */
803 if (aim->value > ai[0].value ||
804 (aim->value == ai[0].value &&
805 aim->serial > ai[0].serial))
807 w.value = ai[0].value;
808 ai[0].value = aim->value;
809 aim->value = w.value;
810 w.serial = ai[0].serial;
811 ai[0].serial = aim->serial;
812 aim->serial = w.serial;
819 unsort(struct line *f, int l, int *b)
823 a = calloc(l + 1, sizeof(*a));
826 for (i = 1; i <= l; i++)
827 a[f[i].serial] = f[i].value;
828 for (i = 1; i <= l; i++)
840 for (i = 1; (c = getc(f)) != '\n' && c != EOF; i++)
846 output(FILE *outfile, struct got_diff_state *ds, struct got_diff_args *args,
847 const char *file1, FILE *f1, const char *file2, FILE *f2, int flags)
849 int m, i0, i1, j0, j1;
856 ds->J[m + 1] = ds->len[1] + 1;
857 if (args->diff_format != D_EDIT) {
858 for (i0 = 1; i0 <= m; i0 = i1 + 1) {
859 while (i0 <= m && ds->J[i0] == ds->J[i0 - 1] + 1)
861 j0 = ds->J[i0 - 1] + 1;
863 while (i1 < m && ds->J[i1 + 1] == 0)
865 j1 = ds->J[i1 + 1] - 1;
867 error = change(outfile, ds, args, file1, f1, file2, f2,
868 i0, i1, j0, j1, &flags);
873 for (i0 = m; i0 >= 1; i0 = i1 - 1) {
874 while (i0 >= 1 && ds->J[i0] == ds->J[i0 + 1] - 1 && ds->J[i0] != 0)
876 j0 = ds->J[i0 + 1] - 1;
878 while (i1 > 1 && ds->J[i1 - 1] == 0)
880 j1 = ds->J[i1 - 1] + 1;
882 change(outfile, ds, args, file1, f1, file2, f2, i1, i0,
889 error = change(outfile, ds, args, file1, f1, file2, f2, 1, 0,
890 1, ds->len[1], &flags);
894 if (args->diff_format == D_IFDEF) {
897 if ((c = getc(f1)) == EOF)
899 diff_output(outfile, "%c", c);
903 if (ds->anychange != 0) {
904 if (args->diff_format == D_CONTEXT)
905 dump_context_vec(outfile, ds, args, f1, f2, flags);
906 else if (args->diff_format == D_UNIFIED)
907 dump_unified_vec(outfile, ds, args, f1, f2, flags);
914 range(FILE *outfile, int a, int b, char *separator)
916 diff_output(outfile, "%d", a > b ? b : a);
918 diff_output(outfile, "%s%d", separator, b);
922 uni_range(FILE *outfile, int a, int b)
925 diff_output(outfile, "%d,%d", a, b - a + 1);
927 diff_output(outfile, "%d", b);
929 diff_output(outfile, "%d,0", b);
933 preadline(int fd, size_t rlen, off_t off)
938 line = malloc(rlen + 1);
941 if ((nr = pread(fd, line, rlen, off)) < 0) {
945 if (nr > 0 && line[nr-1] == '\n')
952 ignoreline(char *line)
954 return 0; /* do not ignore any lines */
958 * Indicate that there is a difference between lines a and b of the from file
959 * to get to lines c to d of the to file. If a is greater then b then there
960 * are no lines in the from file involved and this means that there were
961 * lines appended (beginning at b). If c is greater than d then there are
962 * lines missing from the to file.
965 change(FILE *outfile, struct got_diff_state *ds, struct got_diff_args *args,
966 const char *file1, FILE *f1, const char *file2, FILE *f2,
967 int a, int b, int c, int d, int *pflags)
969 size_t max_context = 64;
973 if (args->diff_format != D_IFDEF && a > b && c > d)
975 if (args->ignore_pats != NULL) {
978 * All lines in the change, insert, or delete must
979 * match an ignore pattern for the change to be
982 if (a <= b) { /* Changes and deletes. */
983 for (i = a; i <= b; i++) {
984 line = preadline(fileno(f1),
985 ds->ixold[i] - ds->ixold[i - 1],
989 if (!ignoreline(line))
993 if (a > b || c <= d) { /* Changes and inserts. */
994 for (i = c; i <= d; i++) {
995 line = preadline(fileno(f2),
996 ds->ixnew[i] - ds->ixnew[i - 1],
1000 if (!ignoreline(line))
1007 if (*pflags & D_HEADER) {
1008 diff_output(outfile, "%s %s %s\n", args->diffargs, file1, file2);
1009 *pflags &= ~D_HEADER;
1011 if (args->diff_format == D_CONTEXT || args->diff_format == D_UNIFIED) {
1013 * Allocate change records as needed.
1015 if (ds->context_vec_ptr == ds->context_vec_end - 1) {
1016 ptrdiff_t offset = ds->context_vec_ptr - ds->context_vec_start;
1018 ds->context_vec_start =
1019 reallocarray(ds->context_vec_start, max_context,
1020 sizeof(*ds->context_vec_start));
1021 if (ds->context_vec_start == NULL)
1023 ds->context_vec_end = ds->context_vec_start + max_context;
1024 ds->context_vec_ptr = ds->context_vec_start + offset;
1026 if (ds->anychange == 0) {
1028 * Print the context/unidiff header first time through.
1030 print_header(outfile, ds, args, file1, file2);
1032 } else if (a > ds->context_vec_ptr->b + (2 * args->diff_context) + 1 &&
1033 c > ds->context_vec_ptr->d + (2 * args->diff_context) + 1) {
1035 * If this change is more than 'diff_context' lines from the
1036 * previous change, dump the record and reset it.
1038 if (args->diff_format == D_CONTEXT)
1039 dump_context_vec(outfile, ds, args, f1, f2, *pflags);
1041 dump_unified_vec(outfile, ds, args, f1, f2, *pflags);
1043 ds->context_vec_ptr++;
1044 ds->context_vec_ptr->a = a;
1045 ds->context_vec_ptr->b = b;
1046 ds->context_vec_ptr->c = c;
1047 ds->context_vec_ptr->d = d;
1050 if (ds->anychange == 0)
1052 switch (args->diff_format) {
1057 range(outfile, a, b, ",");
1058 diff_output(outfile, "%c", a > b ? 'a' : c > d ? 'd' : 'c');
1059 if (args->diff_format == D_NORMAL)
1060 range(outfile, c, d, ",");
1061 diff_output(outfile, "\n");
1064 diff_output(outfile, "%c", a > b ? 'a' : c > d ? 'd' : 'c');
1065 range(outfile, a, b, " ");
1066 diff_output(outfile, "\n");
1070 diff_output(outfile, "a%d %d\n", b, d - c + 1);
1072 diff_output(outfile, "d%d %d\n", a, b - a + 1);
1074 /* add changed lines */
1075 diff_output(outfile, "a%d %d\n", b, d - c + 1);
1079 if (args->diff_format == D_NORMAL || args->diff_format == D_IFDEF) {
1080 fetch(outfile, ds, args, ds->ixold, a, b, f1, '<', 1, *pflags);
1081 if (a <= b && c <= d && args->diff_format == D_NORMAL)
1082 diff_output(outfile, "---\n");
1084 i = fetch(outfile, ds, args, ds->ixnew, c, d, f2, args->diff_format == D_NORMAL ? '>' : '\0', 0, *pflags);
1085 if (i != 0 && args->diff_format == D_EDIT) {
1087 * A non-zero return value for D_EDIT indicates that the
1088 * last line printed was a bare dot (".") that has been
1089 * escaped as ".." to prevent ed(1) from misinterpreting
1090 * it. We have to add a substitute command to change this
1091 * back and restart where we left off.
1093 diff_output(outfile, ".\n");
1094 diff_output(outfile, "%ds/.//\n", a + i - 1);
1100 if ((args->diff_format == D_EDIT || args->diff_format == D_REVERSE) && c <= d)
1101 diff_output(outfile, ".\n");
1103 diff_output(outfile, "#endif /* %s */\n", args->ifdefname);
1111 fetch(FILE *outfile, struct got_diff_state *ds, struct got_diff_args *args,
1112 long *f, int a, int b, FILE *lb, int ch, int oldfile, int flags)
1114 int i, j, c, lastc, col, nc;
1117 * When doing #ifdef's, copy down to current line
1118 * if this is the first file, so that stuff makes it to output.
1120 if (args->diff_format == D_IFDEF && oldfile) {
1121 long curpos = ftell(lb);
1122 /* print through if append (a>b), else to (nb: 0 vs 1 orig) */
1123 nc = f[a > b ? b : a - 1] - curpos;
1124 for (i = 0; i < nc; i++)
1125 diff_output(outfile, "%c", getc(lb));
1129 if (args->diff_format == D_IFDEF) {
1131 diff_output(outfile, "#else /* %s%s */\n",
1132 oldfile == 1 ? "!" : "", args->ifdefname);
1135 diff_output(outfile, "#ifndef %s\n", args->ifdefname);
1137 diff_output(outfile, "#ifdef %s\n", args->ifdefname);
1139 ds->inifdef = 1 + oldfile;
1141 for (i = a; i <= b; i++) {
1142 fseek(lb, f[i - 1], SEEK_SET);
1143 nc = f[i] - f[i - 1];
1144 if (args->diff_format != D_IFDEF && ch != '\0') {
1145 diff_output(outfile, "%c", ch);
1146 if (args->Tflag && (args->diff_format == D_NORMAL || args->diff_format == D_CONTEXT
1147 || args->diff_format == D_UNIFIED))
1148 diff_output(outfile, "\t");
1149 else if (args->diff_format != D_UNIFIED)
1150 diff_output(outfile, " ");
1153 for (j = 0, lastc = '\0'; j < nc; j++, lastc = c) {
1154 if ((c = getc(lb)) == EOF) {
1155 if (args->diff_format == D_EDIT || args->diff_format == D_REVERSE ||
1156 args->diff_format == D_NREVERSE)
1157 warnx("No newline at end of file");
1159 diff_output(outfile, "\n\\ No newline at end of "
1163 if (c == '\t' && (flags & D_EXPANDTABS)) {
1165 diff_output(outfile, " ");
1166 } while (++col & 7);
1168 if (args->diff_format == D_EDIT && j == 1 && c == '\n'
1171 * Don't print a bare "." line
1172 * since that will confuse ed(1).
1173 * Print ".." instead and return,
1174 * giving the caller an offset
1175 * from which to restart.
1177 diff_output(outfile, ".\n");
1180 diff_output(outfile, "%c", c);
1189 * Hash function taken from Robert Sedgewick, Algorithms in C, 3d ed., p 578.
1192 readhash(struct got_diff_state *ds, FILE *f, int flags)
1199 if ((flags & (D_FOLDBLANKS|D_IGNOREBLANKS)) == 0) {
1200 if (flags & D_IGNORECASE)
1201 for (i = 0; (t = getc(f)) != '\n'; i++) {
1207 sum = sum * 127 + ds->chrtran[t];
1210 for (i = 0; (t = getc(f)) != '\n'; i++) {
1216 sum = sum * 127 + t;
1220 switch (t = getc(f)) {
1229 if (space && (flags & D_IGNOREBLANKS) == 0) {
1233 sum = sum * 127 + ds->chrtran[t];
1247 * There is a remote possibility that we end up with a zero sum.
1248 * Zero is used as an EOF marker, so return 1 instead.
1250 return (sum == 0 ? 1 : sum);
1256 unsigned char buf[BUFSIZ];
1263 cnt = fread(buf, 1, sizeof(buf), f);
1264 return (memchr(buf, '\0', cnt) == NULL);
1267 #define begins_with(s, pre) (strncmp(s, pre, sizeof(pre)-1) == 0)
1270 match_function(struct got_diff_state *ds, const long *f, int pos, FILE *fp)
1272 unsigned char buf[FUNCTION_CONTEXT_SIZE];
1274 int last = ds->lastline;
1278 while (pos > last) {
1279 fseek(fp, f[pos - 1], SEEK_SET);
1280 nc = f[pos] - f[pos - 1];
1281 if (nc >= sizeof(buf))
1282 nc = sizeof(buf) - 1;
1283 nc = fread(buf, 1, nc, fp);
1286 buf[strcspn(buf, "\n")] = '\0';
1287 if (isalpha(buf[0]) || buf[0] == '_' || buf[0] == '$') {
1288 if (begins_with(buf, "private:")) {
1290 state = " (private)";
1291 } else if (begins_with(buf, "protected:")) {
1293 state = " (protected)";
1294 } else if (begins_with(buf, "public:")) {
1296 state = " (public)";
1298 strlcpy(ds->lastbuf, buf, sizeof ds->lastbuf);
1300 strlcat(ds->lastbuf, state,
1301 sizeof ds->lastbuf);
1302 ds->lastmatchline = pos;
1309 return ds->lastmatchline > 0 ? ds->lastbuf : NULL;
1312 /* dump accumulated "context" diff changes */
1314 dump_context_vec(FILE *outfile, struct got_diff_state *ds, struct got_diff_args *args,
1315 FILE *f1, FILE *f2, int flags)
1317 struct context_vec *cvp = ds->context_vec_start;
1318 int lowa, upb, lowc, upd, do_output;
1322 if (ds->context_vec_start > ds->context_vec_ptr)
1325 b = d = 0; /* gcc */
1326 lowa = MAXIMUM(1, cvp->a - args->diff_context);
1327 upb = MINIMUM(ds->len[0], ds->context_vec_ptr->b + args->diff_context);
1328 lowc = MAXIMUM(1, cvp->c - args->diff_context);
1329 upd = MINIMUM(ds->len[1], ds->context_vec_ptr->d + args->diff_context);
1331 diff_output(outfile, "***************");
1332 if ((flags & D_PROTOTYPE)) {
1333 f = match_function(ds, ds->ixold, lowa-1, f1);
1335 diff_output(outfile, " %s", f);
1337 diff_output(outfile, "\n*** ");
1338 range(outfile, lowa, upb, ",");
1339 diff_output(outfile, " ****\n");
1342 * Output changes to the "old" file. The first loop suppresses
1343 * output if there were no changes to the "old" file (we'll see
1344 * the "old" lines as context in the "new" list).
1347 for (; cvp <= ds->context_vec_ptr; cvp++)
1348 if (cvp->a <= cvp->b) {
1349 cvp = ds->context_vec_start;
1354 while (cvp <= ds->context_vec_ptr) {
1360 if (a <= b && c <= d)
1363 ch = (a <= b) ? 'd' : 'a';
1366 fetch(outfile, ds, args, ds->ixold, lowa, b, f1, ' ', 0, flags);
1368 fetch(outfile, ds, args, ds->ixold, lowa, a - 1, f1, ' ', 0, flags);
1369 fetch(outfile, ds, args, ds->ixold, a, b, f1,
1370 ch == 'c' ? '!' : '-', 0, flags);
1375 fetch(outfile, ds, args, ds->ixold, b + 1, upb, f1, ' ', 0, flags);
1377 /* output changes to the "new" file */
1378 diff_output(outfile, "--- ");
1379 range(outfile, lowc, upd, ",");
1380 diff_output(outfile, " ----\n");
1383 for (cvp = ds->context_vec_start; cvp <= ds->context_vec_ptr; cvp++)
1384 if (cvp->c <= cvp->d) {
1385 cvp = ds->context_vec_start;
1390 while (cvp <= ds->context_vec_ptr) {
1396 if (a <= b && c <= d)
1399 ch = (a <= b) ? 'd' : 'a';
1402 fetch(outfile, ds, args, ds->ixnew, lowc, d, f2, ' ', 0, flags);
1404 fetch(outfile, ds, args, ds->ixnew, lowc, c - 1, f2, ' ', 0, flags);
1405 fetch(outfile, ds, args, ds->ixnew, c, d, f2,
1406 ch == 'c' ? '!' : '+', 0, flags);
1411 fetch(outfile, ds, args, ds->ixnew, d + 1, upd, f2, ' ', 0, flags);
1413 ds->context_vec_ptr = ds->context_vec_start - 1;
1416 /* dump accumulated "unified" diff changes */
1418 dump_unified_vec(FILE *outfile, struct got_diff_state *ds, struct got_diff_args *args,
1419 FILE *f1, FILE *f2, int flags)
1421 struct context_vec *cvp = ds->context_vec_start;
1422 int lowa, upb, lowc, upd;
1426 if (ds->context_vec_start > ds->context_vec_ptr)
1429 b = d = 0; /* gcc */
1430 lowa = MAXIMUM(1, cvp->a - args->diff_context);
1431 upb = MINIMUM(ds->len[0], ds->context_vec_ptr->b + args->diff_context);
1432 lowc = MAXIMUM(1, cvp->c - args->diff_context);
1433 upd = MINIMUM(ds->len[1], ds->context_vec_ptr->d + args->diff_context);
1435 diff_output(outfile, "@@ -");
1436 uni_range(outfile, lowa, upb);
1437 diff_output(outfile, " +");
1438 uni_range(outfile, lowc, upd);
1439 diff_output(outfile, " @@");
1440 if ((flags & D_PROTOTYPE)) {
1441 f = match_function(ds, ds->ixold, lowa-1, f1);
1443 diff_output(outfile, " %s", f);
1445 diff_output(outfile, "\n");
1448 * Output changes in "unified" diff format--the old and new lines
1449 * are printed together.
1451 for (; cvp <= ds->context_vec_ptr; cvp++) {
1458 * c: both new and old changes
1459 * d: only changes in the old file
1460 * a: only changes in the new file
1462 if (a <= b && c <= d)
1465 ch = (a <= b) ? 'd' : 'a';
1469 fetch(outfile, ds, args, ds->ixold, lowa, a - 1, f1, ' ', 0, flags);
1470 fetch(outfile, ds, args, ds->ixold, a, b, f1, '-', 0, flags);
1471 fetch(outfile, ds, args, ds->ixnew, c, d, f2, '+', 0, flags);
1474 fetch(outfile, ds, args, ds->ixold, lowa, a - 1, f1, ' ', 0, flags);
1475 fetch(outfile, ds, args, ds->ixold, a, b, f1, '-', 0, flags);
1478 fetch(outfile, ds, args, ds->ixnew, lowc, c - 1, f2, ' ', 0, flags);
1479 fetch(outfile, ds, args, ds->ixnew, c, d, f2, '+', 0, flags);
1485 fetch(outfile, ds, args, ds->ixnew, d + 1, upd, f2, ' ', 0, flags);
1487 ds->context_vec_ptr = ds->context_vec_start - 1;
1491 print_header(FILE *outfile, struct got_diff_state *ds, struct got_diff_args *args,
1492 const char *file1, const char *file2)
1494 if (args->label[0] != NULL)
1495 diff_output(outfile, "%s %s\n", args->diff_format == D_CONTEXT ? "***" : "---",
1498 diff_output(outfile, "%s %s\t%s", args->diff_format == D_CONTEXT ? "***" : "---",
1499 file1, ctime(&ds->stb1.st_mtime));
1500 if (args->label[1] != NULL)
1501 diff_output(outfile, "%s %s\n", args->diff_format == D_CONTEXT ? "---" : "+++",
1504 diff_output(outfile, "%s %s\t%s", args->diff_format == D_CONTEXT ? "---" : "+++",
1505 file2, ctime(&ds->stb2.st_mtime));