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");
304 else if (f1 == NULL) {
309 if (flags & D_EMPTY2)
310 f2 = fopen(_PATH_DEVNULL, "r");
311 else if (f2 == NULL) {
316 switch (files_differ(ds, f1, f2, flags)) {
327 if ((flags & D_FORCEASCII) == 0 &&
328 (!asciifile(f1) || !asciifile(f2))) {
333 if (prepare(ds, 0, f1, ds->stb1.st_size, flags)) {
334 err = got_error_from_errno();
337 if (prepare(ds, 1, f2, ds->stb2.st_size, flags)) {
338 err = got_error_from_errno();
343 sort(ds->sfile[0], ds->slen[0]);
344 sort(ds->sfile[1], ds->slen[1]);
346 ds->member = (int *)ds->file[1];
347 equiv(ds->sfile[0], ds->slen[0], ds->sfile[1], ds->slen[1], ds->member);
348 ds->member = reallocarray(ds->member, ds->slen[1] + 2, sizeof(*ds->member));
349 if (ds->member == NULL) {
350 err = got_error_from_errno();
354 ds->class = (int *)ds->file[0];
355 if (unsort(ds->sfile[0], ds->slen[0], ds->class)) {
356 err = got_error_from_errno();
359 ds->class = reallocarray(ds->class, ds->slen[0] + 2, sizeof(*ds->class));
360 if (ds->class == NULL) {
361 err = got_error_from_errno();
365 ds->klist = calloc(ds->slen[0] + 2, sizeof(*ds->klist));
366 if (ds->klist == NULL) {
367 err = got_error_from_errno();
372 ds->clist = calloc(ds->clistlen, sizeof(*ds->clist));
373 if (ds->clist == NULL) {
374 err = got_error_from_errno();
377 i = stone(ds, ds->class, ds->slen[0], ds->member, ds->klist, flags);
379 err = got_error_from_errno();
387 ds->J = reallocarray(ds->J, ds->len[0] + 2, sizeof(*ds->J));
389 err = got_error_from_errno();
392 unravel(ds, ds->klist[i]);
398 ds->ixold = reallocarray(ds->ixold, ds->len[0] + 2, sizeof(*ds->ixold));
399 if (ds->ixold == NULL) {
400 err = got_error_from_errno();
403 ds->ixnew = reallocarray(ds->ixnew, ds->len[1] + 2, sizeof(*ds->ixnew));
404 if (ds->ixnew == NULL) {
405 err = got_error_from_errno();
408 check(ds, f1, f2, flags);
409 if (output(outfile, ds, args, args->label[0], f1, args->label[1], f2,
411 err = got_error_from_errno();
427 * Check to see if the given files differ.
428 * Returns 0 if they are the same, 1 if different, and -1 on error.
429 * XXX - could use code from cmp(1) [faster]
432 files_differ(struct got_diff_state *ds, FILE *f1, FILE *f2, int flags)
434 char buf1[BUFSIZ], buf2[BUFSIZ];
437 if ((flags & (D_EMPTY1|D_EMPTY2)) || ds->stb1.st_size != ds->stb2.st_size ||
438 (ds->stb1.st_mode & S_IFMT) != (ds->stb2.st_mode & S_IFMT))
441 i = fread(buf1, 1, sizeof(buf1), f1);
442 j = fread(buf2, 1, sizeof(buf2), f2);
443 if ((!i && ferror(f1)) || (!j && ferror(f2)))
449 if (memcmp(buf1, buf2, i) != 0)
455 prepare(struct got_diff_state *ds, int i, FILE *fd, off_t filesize, int flags)
463 sz = (filesize <= SIZE_MAX ? filesize : SIZE_MAX) / 25;
467 p = calloc(sz + 3, sizeof(*p));
470 for (j = 0; (h = readhash(ds, fd, flags));) {
473 p = reallocarray(p, sz + 3, sizeof(*p));
486 prune(struct got_diff_state *ds)
490 for (ds->pref = 0; ds->pref < ds->len[0] && ds->pref < ds->len[1] &&
491 ds->file[0][ds->pref + 1].value == ds->file[1][ds->pref + 1].value;
494 for (ds->suff = 0; ds->suff < ds->len[0] - ds->pref && ds->suff < ds->len[1] - ds->pref &&
495 ds->file[0][ds->len[0] - ds->suff].value == ds->file[1][ds->len[1] - ds->suff].value;
498 for (j = 0; j < 2; j++) {
499 ds->sfile[j] = ds->file[j] + ds->pref;
500 ds->slen[j] = ds->len[j] - ds->pref - ds->suff;
501 for (i = 0; i <= ds->slen[j]; i++)
502 ds->sfile[j][i].serial = i;
507 equiv(struct line *a, int n, struct line *b, int m, int *c)
512 while (i <= n && j <= m) {
513 if (a[i].value < b[j].value)
515 else if (a[i].value == b[j].value)
526 while (b[j + 1].value == b[j].value) {
534 /* Code taken from ping.c */
543 do { /* newton was a stinker */
548 } while ((x - y) > 1 || (x - y) < -1);
554 stone(struct got_diff_state *ds, int *a, int n, int *b, int *c, int flags)
557 int oldc, tc, oldl, sq;
558 u_int numtries, bound;
561 if (flags & D_MINIMAL)
565 bound = MAXIMUM(256, sq);
569 c[0] = newcand(ds, 0, 0, 0, &error);
572 for (i = 1; i <= n; i++) {
581 if (y <= ds->clist[oldc].y)
583 l = search(ds, c, k, y);
587 if (ds->clist[c[l]].y <= y)
590 c[l] = newcand(ds, i, y, oldc, &error);
597 c[l] = newcand(ds, i, y, oldc, &error);
603 } while ((y = b[++j]) > 0 && numtries < bound);
609 newcand(struct got_diff_state *ds, int x, int y, int pred, int *errorp)
613 if (ds->clen == ds->clistlen) {
614 ds->clistlen = ds->clistlen * 11 / 10;
615 ds->clist = reallocarray(ds->clist, ds->clistlen,
617 if (ds->clist == NULL) {
622 q = ds->clist + ds->clen;
631 search(struct got_diff_state *ds, int *c, int k, int y)
635 if (ds->clist[c[k]].y < y) /* quick look for typical case */
643 t = ds->clist[c[l]].y;
655 unravel(struct got_diff_state *ds, int p)
660 for (i = 0; i <= ds->len[0]; i++)
661 ds->J[i] = i <= ds->pref ? i :
662 i > ds->len[0] - ds->suff ? i + ds->len[1] - ds->len[0] : 0;
663 for (q = ds->clist + p; q->y != 0; q = ds->clist + q->pred)
664 ds->J[q->x + ds->pref] = q->y + ds->pref;
668 * Check does double duty:
669 * 1. ferret out any fortuitous correspondences due
670 * to confounding by hashing (which result in "jackpot")
671 * 2. collect random access indexes to the two files
674 check(struct got_diff_state *ds, FILE *f1, FILE *f2, int flags)
676 int i, j, jackpot, c, d;
682 ds->ixold[0] = ds->ixnew[0] = 0;
685 for (i = 1; i <= ds->len[0]; i++) {
687 ds->ixold[i] = ctold += skipline(f1);
690 while (j < ds->J[i]) {
691 ds->ixnew[j] = ctnew += skipline(f2);
694 if (flags & (D_FOLDBLANKS|D_IGNOREBLANKS|D_IGNORECASE)) {
699 * GNU diff ignores a missing newline
700 * in one file for -b or -w.
702 if (flags & (D_FOLDBLANKS|D_IGNOREBLANKS)) {
703 if (c == EOF && d == '\n') {
706 } else if (c == '\n' && d == EOF) {
713 if ((flags & D_FOLDBLANKS) && isspace(c) &&
719 } while (isspace(c = getc(f1)));
724 } while (isspace(d = getc(f2)));
725 } else if ((flags & D_IGNOREBLANKS)) {
726 while (isspace(c) && c != '\n') {
730 while (isspace(d) && d != '\n') {
735 if (ds->chrtran[c] != ds->chrtran[d]) {
738 if (c != '\n' && c != EOF)
739 ctold += skipline(f1);
740 if (d != '\n' && c != EOF)
741 ctnew += skipline(f2);
744 if (c == '\n' || c == EOF)
751 if ((c = getc(f1)) != (d = getc(f2))) {
754 if (c != '\n' && c != EOF)
755 ctold += skipline(f1);
756 if (d != '\n' && c != EOF)
757 ctnew += skipline(f2);
760 if (c == '\n' || c == EOF)
764 ds->ixold[i] = ctold;
765 ds->ixnew[j] = ctnew;
768 for (; j <= ds->len[1]; j++)
769 ds->ixnew[j] = ctnew += skipline(f2);
772 * fprintf(stderr, "jackpot\n");
776 /* shellsort CACM #201 */
778 sort(struct line *a, int n)
780 struct line *ai, *aim, w;
785 for (j = 1; j <= n; j *= 2)
787 for (m /= 2; m != 0; m /= 2) {
789 for (j = 1; j <= k; j++) {
790 for (ai = &a[j]; ai > a; ai -= m) {
793 break; /* wraparound */
794 if (aim->value > ai[0].value ||
795 (aim->value == ai[0].value &&
796 aim->serial > ai[0].serial))
798 w.value = ai[0].value;
799 ai[0].value = aim->value;
800 aim->value = w.value;
801 w.serial = ai[0].serial;
802 ai[0].serial = aim->serial;
803 aim->serial = w.serial;
810 unsort(struct line *f, int l, int *b)
814 a = calloc(l + 1, sizeof(*a));
817 for (i = 1; i <= l; i++)
818 a[f[i].serial] = f[i].value;
819 for (i = 1; i <= l; i++)
831 for (i = 1; (c = getc(f)) != '\n' && c != EOF; i++)
837 output(FILE *outfile, struct got_diff_state *ds, struct got_diff_args *args,
838 const char *file1, FILE *f1, const char *file2, FILE *f2, int flags)
840 int m, i0, i1, j0, j1;
847 ds->J[m + 1] = ds->len[1] + 1;
848 if (args->diff_format != D_EDIT) {
849 for (i0 = 1; i0 <= m; i0 = i1 + 1) {
850 while (i0 <= m && ds->J[i0] == ds->J[i0 - 1] + 1)
852 j0 = ds->J[i0 - 1] + 1;
854 while (i1 < m && ds->J[i1 + 1] == 0)
856 j1 = ds->J[i1 + 1] - 1;
858 error = change(outfile, ds, args, file1, f1, file2, f2,
859 i0, i1, j0, j1, &flags);
864 for (i0 = m; i0 >= 1; i0 = i1 - 1) {
865 while (i0 >= 1 && ds->J[i0] == ds->J[i0 + 1] - 1 && ds->J[i0] != 0)
867 j0 = ds->J[i0 + 1] - 1;
869 while (i1 > 1 && ds->J[i1 - 1] == 0)
871 j1 = ds->J[i1 - 1] + 1;
873 change(outfile, ds, args, file1, f1, file2, f2, i1, i0,
880 error = change(outfile, ds, args, file1, f1, file2, f2, 1, 0,
881 1, ds->len[1], &flags);
885 if (args->diff_format == D_IFDEF) {
888 if ((c = getc(f1)) == EOF)
890 diff_output(outfile, "%c", c);
894 if (ds->anychange != 0) {
895 if (args->diff_format == D_CONTEXT)
896 dump_context_vec(outfile, ds, args, f1, f2, flags);
897 else if (args->diff_format == D_UNIFIED)
898 dump_unified_vec(outfile, ds, args, f1, f2, flags);
905 range(FILE *outfile, int a, int b, char *separator)
907 diff_output(outfile, "%d", a > b ? b : a);
909 diff_output(outfile, "%s%d", separator, b);
913 uni_range(FILE *outfile, int a, int b)
916 diff_output(outfile, "%d,%d", a, b - a + 1);
918 diff_output(outfile, "%d", b);
920 diff_output(outfile, "%d,0", b);
924 preadline(int fd, size_t rlen, off_t off)
929 line = malloc(rlen + 1);
932 if ((nr = pread(fd, line, rlen, off)) < 0) {
936 if (nr > 0 && line[nr-1] == '\n')
943 ignoreline(char *line)
945 return 0; /* do not ignore any lines */
949 * Indicate that there is a difference between lines a and b of the from file
950 * to get to lines c to d of the to file. If a is greater then b then there
951 * are no lines in the from file involved and this means that there were
952 * lines appended (beginning at b). If c is greater than d then there are
953 * lines missing from the to file.
956 change(FILE *outfile, struct got_diff_state *ds, struct got_diff_args *args,
957 const char *file1, FILE *f1, const char *file2, FILE *f2,
958 int a, int b, int c, int d, int *pflags)
960 size_t max_context = 64;
964 if (args->diff_format != D_IFDEF && a > b && c > d)
966 if (args->ignore_pats != NULL) {
969 * All lines in the change, insert, or delete must
970 * match an ignore pattern for the change to be
973 if (a <= b) { /* Changes and deletes. */
974 for (i = a; i <= b; i++) {
975 line = preadline(fileno(f1),
976 ds->ixold[i] - ds->ixold[i - 1],
980 if (!ignoreline(line))
984 if (a > b || c <= d) { /* Changes and inserts. */
985 for (i = c; i <= d; i++) {
986 line = preadline(fileno(f2),
987 ds->ixnew[i] - ds->ixnew[i - 1],
991 if (!ignoreline(line))
998 if (*pflags & D_HEADER) {
999 diff_output(outfile, "%s %s %s\n", args->diffargs, file1, file2);
1000 *pflags &= ~D_HEADER;
1002 if (args->diff_format == D_CONTEXT || args->diff_format == D_UNIFIED) {
1004 * Allocate change records as needed.
1006 if (ds->context_vec_ptr == ds->context_vec_end - 1) {
1007 ptrdiff_t offset = ds->context_vec_ptr - ds->context_vec_start;
1009 ds->context_vec_start =
1010 reallocarray(ds->context_vec_start, max_context,
1011 sizeof(*ds->context_vec_start));
1012 if (ds->context_vec_start == NULL)
1014 ds->context_vec_end = ds->context_vec_start + max_context;
1015 ds->context_vec_ptr = ds->context_vec_start + offset;
1017 if (ds->anychange == 0) {
1019 * Print the context/unidiff header first time through.
1021 print_header(outfile, ds, args, file1, file2);
1023 } else if (a > ds->context_vec_ptr->b + (2 * args->diff_context) + 1 &&
1024 c > ds->context_vec_ptr->d + (2 * args->diff_context) + 1) {
1026 * If this change is more than 'diff_context' lines from the
1027 * previous change, dump the record and reset it.
1029 if (args->diff_format == D_CONTEXT)
1030 dump_context_vec(outfile, ds, args, f1, f2, *pflags);
1032 dump_unified_vec(outfile, ds, args, f1, f2, *pflags);
1034 ds->context_vec_ptr++;
1035 ds->context_vec_ptr->a = a;
1036 ds->context_vec_ptr->b = b;
1037 ds->context_vec_ptr->c = c;
1038 ds->context_vec_ptr->d = d;
1041 if (ds->anychange == 0)
1043 switch (args->diff_format) {
1048 range(outfile, a, b, ",");
1049 diff_output(outfile, "%c", a > b ? 'a' : c > d ? 'd' : 'c');
1050 if (args->diff_format == D_NORMAL)
1051 range(outfile, c, d, ",");
1052 diff_output(outfile, "\n");
1055 diff_output(outfile, "%c", a > b ? 'a' : c > d ? 'd' : 'c');
1056 range(outfile, a, b, " ");
1057 diff_output(outfile, "\n");
1061 diff_output(outfile, "a%d %d\n", b, d - c + 1);
1063 diff_output(outfile, "d%d %d\n", a, b - a + 1);
1065 /* add changed lines */
1066 diff_output(outfile, "a%d %d\n", b, d - c + 1);
1070 if (args->diff_format == D_NORMAL || args->diff_format == D_IFDEF) {
1071 fetch(outfile, ds, args, ds->ixold, a, b, f1, '<', 1, *pflags);
1072 if (a <= b && c <= d && args->diff_format == D_NORMAL)
1073 diff_output(outfile, "---\n");
1075 i = fetch(outfile, ds, args, ds->ixnew, c, d, f2, args->diff_format == D_NORMAL ? '>' : '\0', 0, *pflags);
1076 if (i != 0 && args->diff_format == D_EDIT) {
1078 * A non-zero return value for D_EDIT indicates that the
1079 * last line printed was a bare dot (".") that has been
1080 * escaped as ".." to prevent ed(1) from misinterpreting
1081 * it. We have to add a substitute command to change this
1082 * back and restart where we left off.
1084 diff_output(outfile, ".\n");
1085 diff_output(outfile, "%ds/.//\n", a + i - 1);
1091 if ((args->diff_format == D_EDIT || args->diff_format == D_REVERSE) && c <= d)
1092 diff_output(outfile, ".\n");
1094 diff_output(outfile, "#endif /* %s */\n", args->ifdefname);
1102 fetch(FILE *outfile, struct got_diff_state *ds, struct got_diff_args *args,
1103 long *f, int a, int b, FILE *lb, int ch, int oldfile, int flags)
1105 int i, j, c, lastc, col, nc;
1108 * When doing #ifdef's, copy down to current line
1109 * if this is the first file, so that stuff makes it to output.
1111 if (args->diff_format == D_IFDEF && oldfile) {
1112 long curpos = ftell(lb);
1113 /* print through if append (a>b), else to (nb: 0 vs 1 orig) */
1114 nc = f[a > b ? b : a - 1] - curpos;
1115 for (i = 0; i < nc; i++)
1116 diff_output(outfile, "%c", getc(lb));
1120 if (args->diff_format == D_IFDEF) {
1122 diff_output(outfile, "#else /* %s%s */\n",
1123 oldfile == 1 ? "!" : "", args->ifdefname);
1126 diff_output(outfile, "#ifndef %s\n", args->ifdefname);
1128 diff_output(outfile, "#ifdef %s\n", args->ifdefname);
1130 ds->inifdef = 1 + oldfile;
1132 for (i = a; i <= b; i++) {
1133 fseek(lb, f[i - 1], SEEK_SET);
1134 nc = f[i] - f[i - 1];
1135 if (args->diff_format != D_IFDEF && ch != '\0') {
1136 diff_output(outfile, "%c", ch);
1137 if (args->Tflag && (args->diff_format == D_NORMAL || args->diff_format == D_CONTEXT
1138 || args->diff_format == D_UNIFIED))
1139 diff_output(outfile, "\t");
1140 else if (args->diff_format != D_UNIFIED)
1141 diff_output(outfile, " ");
1144 for (j = 0, lastc = '\0'; j < nc; j++, lastc = c) {
1145 if ((c = getc(lb)) == EOF) {
1146 if (args->diff_format == D_EDIT || args->diff_format == D_REVERSE ||
1147 args->diff_format == D_NREVERSE)
1148 warnx("No newline at end of file");
1150 diff_output(outfile, "\n\\ No newline at end of "
1154 if (c == '\t' && (flags & D_EXPANDTABS)) {
1156 diff_output(outfile, " ");
1157 } while (++col & 7);
1159 if (args->diff_format == D_EDIT && j == 1 && c == '\n'
1162 * Don't print a bare "." line
1163 * since that will confuse ed(1).
1164 * Print ".." instead and return,
1165 * giving the caller an offset
1166 * from which to restart.
1168 diff_output(outfile, ".\n");
1171 diff_output(outfile, "%c", c);
1180 * Hash function taken from Robert Sedgewick, Algorithms in C, 3d ed., p 578.
1183 readhash(struct got_diff_state *ds, FILE *f, int flags)
1190 if ((flags & (D_FOLDBLANKS|D_IGNOREBLANKS)) == 0) {
1191 if (flags & D_IGNORECASE)
1192 for (i = 0; (t = getc(f)) != '\n'; i++) {
1198 sum = sum * 127 + ds->chrtran[t];
1201 for (i = 0; (t = getc(f)) != '\n'; i++) {
1207 sum = sum * 127 + t;
1211 switch (t = getc(f)) {
1220 if (space && (flags & D_IGNOREBLANKS) == 0) {
1224 sum = sum * 127 + ds->chrtran[t];
1238 * There is a remote possibility that we end up with a zero sum.
1239 * Zero is used as an EOF marker, so return 1 instead.
1241 return (sum == 0 ? 1 : sum);
1247 unsigned char buf[BUFSIZ];
1254 cnt = fread(buf, 1, sizeof(buf), f);
1255 return (memchr(buf, '\0', cnt) == NULL);
1258 #define begins_with(s, pre) (strncmp(s, pre, sizeof(pre)-1) == 0)
1261 match_function(struct got_diff_state *ds, const long *f, int pos, FILE *fp)
1263 unsigned char buf[FUNCTION_CONTEXT_SIZE];
1265 int last = ds->lastline;
1269 while (pos > last) {
1270 fseek(fp, f[pos - 1], SEEK_SET);
1271 nc = f[pos] - f[pos - 1];
1272 if (nc >= sizeof(buf))
1273 nc = sizeof(buf) - 1;
1274 nc = fread(buf, 1, nc, fp);
1277 buf[strcspn(buf, "\n")] = '\0';
1278 if (isalpha(buf[0]) || buf[0] == '_' || buf[0] == '$') {
1279 if (begins_with(buf, "private:")) {
1281 state = " (private)";
1282 } else if (begins_with(buf, "protected:")) {
1284 state = " (protected)";
1285 } else if (begins_with(buf, "public:")) {
1287 state = " (public)";
1289 strlcpy(ds->lastbuf, buf, sizeof ds->lastbuf);
1291 strlcat(ds->lastbuf, state,
1292 sizeof ds->lastbuf);
1293 ds->lastmatchline = pos;
1300 return ds->lastmatchline > 0 ? ds->lastbuf : NULL;
1303 /* dump accumulated "context" diff changes */
1305 dump_context_vec(FILE *outfile, struct got_diff_state *ds, struct got_diff_args *args,
1306 FILE *f1, FILE *f2, int flags)
1308 struct context_vec *cvp = ds->context_vec_start;
1309 int lowa, upb, lowc, upd, do_output;
1313 if (ds->context_vec_start > ds->context_vec_ptr)
1316 b = d = 0; /* gcc */
1317 lowa = MAXIMUM(1, cvp->a - args->diff_context);
1318 upb = MINIMUM(ds->len[0], ds->context_vec_ptr->b + args->diff_context);
1319 lowc = MAXIMUM(1, cvp->c - args->diff_context);
1320 upd = MINIMUM(ds->len[1], ds->context_vec_ptr->d + args->diff_context);
1322 diff_output(outfile, "***************");
1323 if ((flags & D_PROTOTYPE)) {
1324 f = match_function(ds, ds->ixold, lowa-1, f1);
1326 diff_output(outfile, " %s", f);
1328 diff_output(outfile, "\n*** ");
1329 range(outfile, lowa, upb, ",");
1330 diff_output(outfile, " ****\n");
1333 * Output changes to the "old" file. The first loop suppresses
1334 * output if there were no changes to the "old" file (we'll see
1335 * the "old" lines as context in the "new" list).
1338 for (; cvp <= ds->context_vec_ptr; cvp++)
1339 if (cvp->a <= cvp->b) {
1340 cvp = ds->context_vec_start;
1345 while (cvp <= ds->context_vec_ptr) {
1351 if (a <= b && c <= d)
1354 ch = (a <= b) ? 'd' : 'a';
1357 fetch(outfile, ds, args, ds->ixold, lowa, b, f1, ' ', 0, flags);
1359 fetch(outfile, ds, args, ds->ixold, lowa, a - 1, f1, ' ', 0, flags);
1360 fetch(outfile, ds, args, ds->ixold, a, b, f1,
1361 ch == 'c' ? '!' : '-', 0, flags);
1366 fetch(outfile, ds, args, ds->ixold, b + 1, upb, f1, ' ', 0, flags);
1368 /* output changes to the "new" file */
1369 diff_output(outfile, "--- ");
1370 range(outfile, lowc, upd, ",");
1371 diff_output(outfile, " ----\n");
1374 for (cvp = ds->context_vec_start; cvp <= ds->context_vec_ptr; cvp++)
1375 if (cvp->c <= cvp->d) {
1376 cvp = ds->context_vec_start;
1381 while (cvp <= ds->context_vec_ptr) {
1387 if (a <= b && c <= d)
1390 ch = (a <= b) ? 'd' : 'a';
1393 fetch(outfile, ds, args, ds->ixnew, lowc, d, f2, ' ', 0, flags);
1395 fetch(outfile, ds, args, ds->ixnew, lowc, c - 1, f2, ' ', 0, flags);
1396 fetch(outfile, ds, args, ds->ixnew, c, d, f2,
1397 ch == 'c' ? '!' : '+', 0, flags);
1402 fetch(outfile, ds, args, ds->ixnew, d + 1, upd, f2, ' ', 0, flags);
1404 ds->context_vec_ptr = ds->context_vec_start - 1;
1407 /* dump accumulated "unified" diff changes */
1409 dump_unified_vec(FILE *outfile, struct got_diff_state *ds, struct got_diff_args *args,
1410 FILE *f1, FILE *f2, int flags)
1412 struct context_vec *cvp = ds->context_vec_start;
1413 int lowa, upb, lowc, upd;
1417 if (ds->context_vec_start > ds->context_vec_ptr)
1420 b = d = 0; /* gcc */
1421 lowa = MAXIMUM(1, cvp->a - args->diff_context);
1422 upb = MINIMUM(ds->len[0], ds->context_vec_ptr->b + args->diff_context);
1423 lowc = MAXIMUM(1, cvp->c - args->diff_context);
1424 upd = MINIMUM(ds->len[1], ds->context_vec_ptr->d + args->diff_context);
1426 diff_output(outfile, "@@ -");
1427 uni_range(outfile, lowa, upb);
1428 diff_output(outfile, " +");
1429 uni_range(outfile, lowc, upd);
1430 diff_output(outfile, " @@");
1431 if ((flags & D_PROTOTYPE)) {
1432 f = match_function(ds, ds->ixold, lowa-1, f1);
1434 diff_output(outfile, " %s", f);
1436 diff_output(outfile, "\n");
1439 * Output changes in "unified" diff format--the old and new lines
1440 * are printed together.
1442 for (; cvp <= ds->context_vec_ptr; cvp++) {
1449 * c: both new and old changes
1450 * d: only changes in the old file
1451 * a: only changes in the new file
1453 if (a <= b && c <= d)
1456 ch = (a <= b) ? 'd' : 'a';
1460 fetch(outfile, ds, args, ds->ixold, lowa, a - 1, f1, ' ', 0, flags);
1461 fetch(outfile, ds, args, ds->ixold, a, b, f1, '-', 0, flags);
1462 fetch(outfile, ds, args, ds->ixnew, c, d, f2, '+', 0, flags);
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);
1469 fetch(outfile, ds, args, ds->ixnew, lowc, c - 1, f2, ' ', 0, flags);
1470 fetch(outfile, ds, args, ds->ixnew, c, d, f2, '+', 0, flags);
1476 fetch(outfile, ds, args, ds->ixnew, d + 1, upd, f2, ' ', 0, flags);
1478 ds->context_vec_ptr = ds->context_vec_start - 1;
1482 print_header(FILE *outfile, struct got_diff_state *ds, struct got_diff_args *args,
1483 const char *file1, const char *file2)
1485 if (args->label[0] != NULL)
1486 diff_output(outfile, "%s %s\n", args->diff_format == D_CONTEXT ? "***" : "---",
1489 diff_output(outfile, "%s %s\t%s", args->diff_format == D_CONTEXT ? "***" : "---",
1490 file1, ctime(&ds->stb1.st_mtime));
1491 if (args->label[1] != NULL)
1492 diff_output(outfile, "%s %s\n", args->diff_format == D_CONTEXT ? "---" : "+++",
1495 diff_output(outfile, "%s %s\t%s", args->diff_format == D_CONTEXT ? "---" : "+++",
1496 file2, ctime(&ds->stb2.st_mtime));