GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: usr.bin/rcs/diff.c Lines: 32 574 5.6 %
Date: 2017-11-13 Branches: 24 518 4.6 %

Line Branch Exec Source
1
/*	$OpenBSD: diff.c,v 1.39 2016/10/16 13:35:51 okan Exp $	*/
2
/*
3
 * Copyright (C) Caldera International Inc.  2001-2002.
4
 * All rights reserved.
5
 *
6
 * Redistribution and use in source and binary forms, with or without
7
 * modification, are permitted provided that the following conditions
8
 * are met:
9
 * 1. Redistributions of source code and documentation must retain the above
10
 *    copyright notice, this list of conditions and the following disclaimer.
11
 * 2. Redistributions in binary form must reproduce the above copyright
12
 *    notice, this list of conditions and the following disclaimer in the
13
 *    documentation and/or other materials provided with the distribution.
14
 * 3. All advertising materials mentioning features or use of this software
15
 *    must display the following acknowledgement:
16
 *	This product includes software developed or owned by Caldera
17
 *	International, Inc.
18
 * 4. Neither the name of Caldera International, Inc. nor the names of other
19
 *    contributors may be used to endorse or promote products derived from
20
 *    this software without specific prior written permission.
21
 *
22
 * USE OF THE SOFTWARE PROVIDED FOR UNDER THIS LICENSE BY CALDERA
23
 * INTERNATIONAL, INC. AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR
24
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
25
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
26
 * IN NO EVENT SHALL CALDERA INTERNATIONAL, INC. BE LIABLE FOR ANY DIRECT,
27
 * INDIRECT INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
28
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
29
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
31
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
32
 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
33
 * POSSIBILITY OF SUCH DAMAGE.
34
 */
35
/*-
36
 * Copyright (c) 1991, 1993
37
 *	The Regents of the University of California.  All rights reserved.
38
 * Copyright (c) 2004 Jean-Francois Brousseau.  All rights reserved.
39
 *
40
 * Redistribution and use in source and binary forms, with or without
41
 * modification, are permitted provided that the following conditions
42
 * are met:
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.
51
 *
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
62
 * SUCH DAMAGE.
63
 *
64
 *	@(#)diffreg.c   8.1 (Berkeley) 6/6/93
65
 */
66
67
#include <sys/stat.h>
68
69
#include <ctype.h>
70
#include <err.h>
71
#include <stdarg.h>
72
#include <stdint.h>
73
#include <stddef.h>
74
#include <stdio.h>
75
#include <stdlib.h>
76
#include <string.h>
77
#include <unistd.h>
78
#include <limits.h>
79
80
#include "buf.h"
81
#include "diff.h"
82
#include "xmalloc.h"
83
84
#define MINIMUM(a, b)	(((a) < (b)) ? (a) : (b))
85
#define MAXIMUM(a, b)	(((a) > (b)) ? (a) : (b))
86
87
/*
88
 * diff - compare two files.
89
 */
90
91
/*
92
 *	Uses an algorithm due to Harold Stone, which finds
93
 *	a pair of longest identical subsequences in the two
94
 *	files.
95
 *
96
 *	The major goal is to generate the match vector J.
97
 *	J[i] is the index of the line in file1 corresponding
98
 *	to line i file0. J[i] = 0 if there is no
99
 *	such line in file1.
100
 *
101
 *	Lines are hashed so as to work in core. All potential
102
 *	matches are located by sorting the lines of each file
103
 *	on the hash (called ``value''). In particular, this
104
 *	collects the equivalence classes in file1 together.
105
 *	Subroutine equiv replaces the value of each line in
106
 *	file0 by the index of the first element of its
107
 *	matching equivalence in (the reordered) file1.
108
 *	To save space equiv squeezes file1 into a single
109
 *	array member in which the equivalence classes
110
 *	are simply concatenated, except that their first
111
 *	members are flagged by changing sign.
112
 *
113
 *	Next the indices that point into member are unsorted into
114
 *	array class according to the original order of file0.
115
 *
116
 *	The cleverness lies in routine stone. This marches
117
 *	through the lines of file0, developing a vector klist
118
 *	of "k-candidates". At step i a k-candidate is a matched
119
 *	pair of lines x,y (x in file0 y in file1) such that
120
 *	there is a common subsequence of length k
121
 *	between the first i lines of file0 and the first y
122
 *	lines of file1, but there is no such subsequence for
123
 *	any smaller y. x is the earliest possible mate to y
124
 *	that occurs in such a subsequence.
125
 *
126
 *	Whenever any of the members of the equivalence class of
127
 *	lines in file1 matable to a line in file0 has serial number
128
 *	less than the y of some k-candidate, that k-candidate
129
 *	with the smallest such y is replaced. The new
130
 *	k-candidate is chained (via pred) to the current
131
 *	k-1 candidate so that the actual subsequence can
132
 *	be recovered. When a member has serial number greater
133
 *	that the y of all k-candidates, the klist is extended.
134
 *	At the end, the longest subsequence is pulled out
135
 *	and placed in the array J by unravel
136
 *
137
 *	With J in hand, the matches there recorded are
138
 *	check'ed against reality to assure that no spurious
139
 *	matches have crept in due to hashing. If they have,
140
 *	they are broken, and "jackpot" is recorded--a harmless
141
 *	matter except that a true match for a spuriously
142
 *	mated line may now be unnecessarily reported as a change.
143
 *
144
 *	Much of the complexity of the program comes simply
145
 *	from trying to minimize core utilization and
146
 *	maximize the range of doable problems by dynamically
147
 *	allocating what is needed and reusing what is not.
148
 *	The core requirements for problems larger than somewhat
149
 *	are (in words) 2*length(file0) + length(file1) +
150
 *	3*(number of k-candidates installed),  typically about
151
 *	6n words for files of length n.
152
 */
153
154
struct cand {
155
	int	x;
156
	int	y;
157
	int	pred;
158
};
159
160
struct line {
161
	int	serial;
162
	int	value;
163
} *file[2];
164
165
/*
166
 * The following struct is used to record change information when
167
 * doing a "context" or "unified" diff.  (see routine "change" to
168
 * understand the highly mnemonic field names)
169
 */
170
struct context_vec {
171
	int	a;		/* start line in old file */
172
	int	b;		/* end line in old file */
173
	int	c;		/* start line in new file */
174
	int	d;		/* end line in new file */
175
};
176
177
static void	 output(FILE *, FILE *, int);
178
static void	 check(FILE *, FILE *, int);
179
static void	 range(int, int, char *);
180
static void	 uni_range(int, int);
181
static void	 dump_context_vec(FILE *, FILE *, int);
182
static void	 dump_unified_vec(FILE *, FILE *, int);
183
static void	 prepare(int, FILE *, off_t, int);
184
static void	 prune(void);
185
static void	 equiv(struct line *, int, struct line *, int, int *);
186
static void	 unravel(int);
187
static void	 unsort(struct line *, int, int *);
188
static void	 change(FILE *, FILE *, int, int, int, int, int);
189
static void	 sort(struct line *, int);
190
static int	 ignoreline(char *);
191
static int	 asciifile(FILE *);
192
static void	 fetch(long *, int, int, FILE *, int, int, int);
193
static int	 newcand(int, int, int);
194
static int	 search(int *, int, int);
195
static int	 skipline(FILE *);
196
static int	 isqrt(int);
197
static int	 stone(int *, int, int *, int *, int);
198
static int	 readhash(FILE *, int);
199
static int	 files_differ(FILE *, FILE *);
200
static char	*match_function(const long *, int, FILE *);
201
static char	*preadline(int, size_t, off_t);
202
203
204
int diff_context = 3;
205
int diff_format = D_NORMAL;
206
char *diff_file = NULL;
207
RCSNUM *diff_rev1 = NULL;
208
RCSNUM *diff_rev2 = NULL;
209
char diffargs[512]; /* XXX */
210
static struct stat stb1, stb2;
211
static char *ifdefname;
212
regex_t *diff_ignore_re;
213
214
static int  *J;			/* will be overlaid on class */
215
static int  *class;		/* will be overlaid on file[0] */
216
static int  *klist;		/* will be overlaid on file[0] after class */
217
static int  *member;		/* will be overlaid on file[1] */
218
static int   clen;
219
static int   inifdef;		/* whether or not we are in a #ifdef block */
220
static int   len[2];
221
static int   pref, suff;	/* length of prefix and suffix */
222
static int   slen[2];
223
static int   anychange;
224
static long *ixnew;		/* will be overlaid on file[1] */
225
static long *ixold;		/* will be overlaid on klist */
226
static struct cand *clist;	/* merely a free storage pot for candidates */
227
static int   clistlen;		/* the length of clist */
228
static struct line *sfile[2];	/* shortened by pruning common prefix/suffix */
229
static u_char *chrtran;		/* translation table for case-folding */
230
static struct context_vec *context_vec_start;
231
static struct context_vec *context_vec_end;
232
static struct context_vec *context_vec_ptr;
233
234
#define FUNCTION_CONTEXT_SIZE	55
235
static char lastbuf[FUNCTION_CONTEXT_SIZE];
236
static int lastline;
237
static int lastmatchline;
238
BUF  *diffbuf = NULL;
239
240
241
/*
242
 * chrtran points to one of 2 translation tables: cup2low if folding upper to
243
 * lower case clow2low if not folding case
244
 */
245
u_char clow2low[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, 0x40, 0x41,
252
	0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49, 0x4a, 0x4b, 0x4c,
253
	0x4d, 0x4e, 0x4f, 0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57,
254
	0x58, 0x59, 0x5a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f, 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,
269
	0xfd, 0xfe, 0xff
270
};
271
272
u_char cup2low[256] = {
273
	0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a,
274
	0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15,
275
	0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20,
276
	0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b,
277
	0x2c, 0x2d, 0x2e, 0x2f, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36,
278
	0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, 0x60, 0x61,
279
	0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c,
280
	0x6d, 0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
281
	0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x60, 0x61, 0x62,
282
	0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d,
283
	0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78,
284
	0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x80, 0x81, 0x82, 0x83,
285
	0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e,
286
	0x8f, 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99,
287
	0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f, 0xa0, 0xa1, 0xa2, 0xa3, 0xa4,
288
	0xa5, 0xa6, 0xa7, 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
289
	0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba,
290
	0xbb, 0xbc, 0xbd, 0xbe, 0xbf, 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5,
291
	0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, 0xd0,
292
	0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, 0xdb,
293
	0xdc, 0xdd, 0xde, 0xdf, 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6,
294
	0xe7, 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef, 0xf0, 0xf1,
295
	0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, 0xf9, 0xfa, 0xfb, 0xfc,
296
	0xfd, 0xfe, 0xff
297
};
298
299
int
300
diffreg(const char *file1, const char *file2, BUF *out, int flags)
301
{
302
	FILE *f1, *f2;
303
	int i, rval;
304
305
	f1 = f2 = NULL;
306
	rval = D_SAME;
307
20
	anychange = 0;
308
10
	lastline = 0;
309
10
	lastmatchline = 0;
310
10
	context_vec_ptr = context_vec_start - 1;
311
10
	if (flags & D_IGNORECASE)
312
		chrtran = cup2low;
313
	else
314
		chrtran = clow2low;
315
10
	if (out != NULL)
316
10
		diffbuf = out;
317
318
10
	f1 = fopen(file1, "r");
319
10
	if (f1 == NULL) {
320
		warn("%s", file1);
321
		goto closem;
322
	}
323
324
10
	f2 = fopen(file2, "r");
325
10
	if (f2 == NULL) {
326
		warn("%s", file2);
327
		goto closem;
328
	}
329
330

30
	if (fstat(fileno(f1), &stb1) < 0) {
331
		warn("%s", file1);
332
		goto closem;
333
	}
334
335

30
	if (fstat(fileno(f2), &stb2) < 0) {
336
		warn("%s", file2);
337
		goto closem;
338
	}
339
340

10
	switch (files_differ(f1, f2)) {
341
	case 1:
342
		break;
343
	case -1:
344
		rval = D_ERROR;
345
		/* FALLTHROUGH */
346
	case 0:
347
		goto closem;
348
	default:
349
		errx(D_ERROR, "files_differ: invalid case");
350
	}
351
352
	if ((flags & D_FORCEASCII) == 0 &&
353
	    (!asciifile(f1) || !asciifile(f2))) {
354
		rval = D_ERROR;
355
		goto closem;
356
	}
357
358
	prepare(0, f1, stb1.st_size, flags);
359
	prepare(1, f2, stb2.st_size, flags);
360
361
	prune();
362
	sort(sfile[0], slen[0]);
363
	sort(sfile[1], slen[1]);
364
365
	member = (int *)file[1];
366
	equiv(sfile[0], slen[0], sfile[1], slen[1], member);
367
	member = xreallocarray(member, slen[1] + 2, sizeof(*member));
368
369
	class = (int *)file[0];
370
	unsort(sfile[0], slen[0], class);
371
	class = xreallocarray(class, slen[0] + 2, sizeof(*class));
372
373
	klist = xcalloc(slen[0] + 2, sizeof(*klist));
374
	clen = 0;
375
	clistlen = 100;
376
	clist = xcalloc(clistlen, sizeof(*clist));
377
	i = stone(class, slen[0], member, klist, flags);
378
	free(member);
379
	free(class);
380
381
	J = xreallocarray(J, len[0] + 2, sizeof(*J));
382
	unravel(klist[i]);
383
	free(clist);
384
	free(klist);
385
386
	ixold = xreallocarray(ixold, len[0] + 2, sizeof(*ixold));
387
	ixnew = xreallocarray(ixnew, len[1] + 2, sizeof(*ixnew));
388
	check(f1, f2, flags);
389
	output(f1, f2, flags);
390
391
closem:
392
20
	if (anychange) {
393
10
		if (rval == D_SAME)
394
			rval = D_DIFFER;
395
	}
396
10
	if (f1 != NULL)
397
10
		fclose(f1);
398
10
	if (f2 != NULL)
399
10
		fclose(f2);
400
401
10
	return (rval);
402
}
403
404
/*
405
 * Check to see if the given files differ.
406
 * Returns 0 if they are the same, 1 if different, and -1 on error.
407
 * XXX - could use code from cmp(1) [faster]
408
 */
409
static int
410
files_differ(FILE *f1, FILE *f2)
411
{
412
20
	char buf1[BUFSIZ], buf2[BUFSIZ];
413
	size_t i, j;
414
415
10
	if (stb1.st_size != stb2.st_size)
416
		return (1);
417
20
	for (;;) {
418
20
		i = fread(buf1, 1, sizeof(buf1), f1);
419
20
		j = fread(buf2, 1, sizeof(buf2), f2);
420




80
		if ((!i && ferror(f1)) || (!j && ferror(f2)))
421
			return (-1);
422
20
		if (i != j)
423
			return (1);
424
20
		if (i == 0)
425
10
			return (0);
426
10
		if (memcmp(buf1, buf2, i) != 0)
427
			return (1);
428
	}
429
10
}
430
431
static void
432
prepare(int i, FILE *fd, off_t filesize, int flags)
433
{
434
	struct line *p;
435
	int j, h;
436
	size_t sz;
437
438
	rewind(fd);
439
440
	sz = ((uintmax_t)filesize <= SIZE_MAX ? (size_t)filesize : SIZE_MAX) / 25;
441
	if (sz < 100)
442
		sz = 100;
443
444
	p = xcalloc(sz + 3, sizeof(*p));
445
	for (j = 0; (h = readhash(fd, flags));) {
446
		if ((size_t)j == sz) {
447
			sz = sz * 3 / 2;
448
			p = xreallocarray(p, sz + 3, sizeof(*p));
449
		}
450
		p[++j].value = h;
451
	}
452
	len[i] = j;
453
	file[i] = p;
454
}
455
456
static void
457
prune(void)
458
{
459
	int i, j;
460
461
	for (pref = 0; pref < len[0] && pref < len[1] &&
462
	    file[0][pref + 1].value == file[1][pref + 1].value;
463
	    pref++)
464
		;
465
	for (suff = 0; suff < len[0] - pref && suff < len[1] - pref &&
466
	    file[0][len[0] - suff].value == file[1][len[1] - suff].value;
467
	    suff++)
468
		;
469
	for (j = 0; j < 2; j++) {
470
		sfile[j] = file[j] + pref;
471
		slen[j] = len[j] - pref - suff;
472
		for (i = 0; i <= slen[j]; i++)
473
			sfile[j][i].serial = i;
474
	}
475
}
476
477
static void
478
equiv(struct line *a, int n, struct line *b, int m, int *c)
479
{
480
	int i, j;
481
482
	i = j = 1;
483
	while (i <= n && j <= m) {
484
		if (a[i].value < b[j].value)
485
			a[i++].value = 0;
486
		else if (a[i].value == b[j].value)
487
			a[i++].value = j;
488
		else
489
			j++;
490
	}
491
	while (i <= n)
492
		a[i++].value = 0;
493
	b[m + 1].value = 0;
494
	j = 0;
495
	while (++j <= m) {
496
		c[j] = -b[j].serial;
497
		while (b[j + 1].value == b[j].value) {
498
			j++;
499
			c[j] = b[j].serial;
500
		}
501
	}
502
	c[j] = -1;
503
}
504
505
/* Code taken from ping.c */
506
static int
507
isqrt(int n)
508
{
509
	int y, x = 1;
510
511
	if (n == 0)
512
		return (0);
513
514
	do { /* newton was a stinker */
515
		y = x;
516
		x = n / x;
517
		x += y;
518
		x /= 2;
519
	} while ((x - y) > 1 || (x - y) < -1);
520
521
	return (x);
522
}
523
524
static int
525
stone(int *a, int n, int *b, int *c, int flags)
526
{
527
	int i, k, y, j, l;
528
	int oldc, tc, oldl, sq;
529
	u_int numtries, bound;
530
531
	if (flags & D_MINIMAL)
532
		bound = UINT_MAX;
533
	else {
534
		sq = isqrt(n);
535
		bound = MAXIMUM(256, sq);
536
	}
537
538
	k = 0;
539
	c[0] = newcand(0, 0, 0);
540
	for (i = 1; i <= n; i++) {
541
		j = a[i];
542
		if (j == 0)
543
			continue;
544
		y = -b[j];
545
		oldl = 0;
546
		oldc = c[0];
547
		numtries = 0;
548
		do {
549
			if (y <= clist[oldc].y)
550
				continue;
551
			l = search(c, k, y);
552
			if (l != oldl + 1)
553
				oldc = c[l - 1];
554
			if (l <= k) {
555
				if (clist[c[l]].y <= y)
556
					continue;
557
				tc = c[l];
558
				c[l] = newcand(i, y, oldc);
559
				oldc = tc;
560
				oldl = l;
561
				numtries++;
562
			} else {
563
				c[l] = newcand(i, y, oldc);
564
				k++;
565
				break;
566
			}
567
		} while ((y = b[++j]) > 0 && numtries < bound);
568
	}
569
	return (k);
570
}
571
572
static int
573
newcand(int x, int y, int pred)
574
{
575
	struct cand *q;
576
577
	if (clen == clistlen) {
578
		clistlen = clistlen * 11 / 10;
579
		clist = xreallocarray(clist, clistlen, sizeof(*clist));
580
	}
581
	q = clist + clen;
582
	q->x = x;
583
	q->y = y;
584
	q->pred = pred;
585
	return (clen++);
586
}
587
588
static int
589
search(int *c, int k, int y)
590
{
591
	int i, j, l, t;
592
593
	if (clist[c[k]].y < y)	/* quick look for typical case */
594
		return (k + 1);
595
	i = 0;
596
	j = k + 1;
597
	for (;;) {
598
		l = (i + j) / 2;
599
		if (l <= i)
600
			break;
601
		t = clist[c[l]].y;
602
		if (t > y)
603
			j = l;
604
		else if (t < y)
605
			i = l;
606
		else
607
			return (l);
608
	}
609
	return (l + 1);
610
}
611
612
static void
613
unravel(int p)
614
{
615
	struct cand *q;
616
	int i;
617
618
	for (i = 0; i <= len[0]; i++)
619
		J[i] = i <= pref ? i :
620
		    i > len[0] - suff ? i + len[1] - len[0] : 0;
621
	for (q = clist + p; q->y != 0; q = clist + q->pred)
622
		J[q->x + pref] = q->y + pref;
623
}
624
625
/*
626
 * Check does double duty:
627
 *  1.	ferret out any fortuitous correspondences due
628
 *	to confounding by hashing (which result in "jackpot")
629
 *  2.  collect random access indexes to the two files
630
 */
631
static void
632
check(FILE *f1, FILE *f2, int flags)
633
{
634
	int i, j, jackpot, c, d;
635
	long ctold, ctnew;
636
637
	rewind(f1);
638
	rewind(f2);
639
	j = 1;
640
	ixold[0] = ixnew[0] = 0;
641
	jackpot = 0;
642
	ctold = ctnew = 0;
643
	for (i = 1; i <= len[0]; i++) {
644
		if (J[i] == 0) {
645
			ixold[i] = ctold += skipline(f1);
646
			continue;
647
		}
648
		while (j < J[i]) {
649
			ixnew[j] = ctnew += skipline(f2);
650
			j++;
651
		}
652
		if (flags & (D_FOLDBLANKS|D_IGNOREBLANKS|D_IGNORECASE)) {
653
			for (;;) {
654
				c = getc(f1);
655
				d = getc(f2);
656
				/*
657
				 * GNU diff ignores a missing newline
658
				 * in one file for -b or -w.
659
				 */
660
				if ((flags & (D_FOLDBLANKS|D_IGNOREBLANKS)) &&
661
				    ((c == EOF && d == '\n') ||
662
				    (c == '\n' && d == EOF))) {
663
					break;
664
				}
665
				ctold++;
666
				ctnew++;
667
				if ((flags & D_FOLDBLANKS) && isspace(c) &&
668
				    isspace(d)) {
669
					do {
670
						if (c == '\n')
671
							break;
672
						ctold++;
673
					} while (isspace(c = getc(f1)));
674
					do {
675
						if (d == '\n')
676
							break;
677
						ctnew++;
678
					} while (isspace(d = getc(f2)));
679
				} else if ((flags & D_IGNOREBLANKS)) {
680
					while (isspace(c) && c != '\n') {
681
						c = getc(f1);
682
						ctold++;
683
					}
684
					while (isspace(d) && d != '\n') {
685
						d = getc(f2);
686
						ctnew++;
687
					}
688
				}
689
				if (chrtran[c] != chrtran[d]) {
690
					jackpot++;
691
					J[i] = 0;
692
					if (c != '\n' && c != EOF)
693
						ctold += skipline(f1);
694
					if (d != '\n' && c != EOF)
695
						ctnew += skipline(f2);
696
					break;
697
				}
698
				if (c == '\n' || c == EOF)
699
					break;
700
			}
701
		} else {
702
			for (;;) {
703
				ctold++;
704
				ctnew++;
705
				if ((c = getc(f1)) != (d = getc(f2))) {
706
					/* jackpot++; */
707
					J[i] = 0;
708
					if (c != '\n' && c != EOF)
709
						ctold += skipline(f1);
710
					if (d != '\n' && c != EOF)
711
						ctnew += skipline(f2);
712
					break;
713
				}
714
				if (c == '\n' || c == EOF)
715
					break;
716
			}
717
		}
718
		ixold[i] = ctold;
719
		ixnew[j] = ctnew;
720
		j++;
721
	}
722
	for (; j <= len[1]; j++)
723
		ixnew[j] = ctnew += skipline(f2);
724
	/*
725
	 * if (jackpot)
726
	 *	fprintf(stderr, "jackpot\n");
727
	 */
728
}
729
730
/* shellsort CACM #201 */
731
static void
732
sort(struct line *a, int n)
733
{
734
	struct line *ai, *aim, w;
735
	int j, m = 0, k;
736
737
	if (n == 0)
738
		return;
739
	for (j = 1; j <= n; j *= 2)
740
		m = 2 * j - 1;
741
	for (m /= 2; m != 0; m /= 2) {
742
		k = n - m;
743
		for (j = 1; j <= k; j++) {
744
			for (ai = &a[j]; ai > a; ai -= m) {
745
				aim = &ai[m];
746
				if (aim < ai)
747
					break;	/* wraparound */
748
				if (aim->value > ai[0].value ||
749
				    (aim->value == ai[0].value &&
750
					aim->serial > ai[0].serial))
751
					break;
752
				w.value = ai[0].value;
753
				ai[0].value = aim->value;
754
				aim->value = w.value;
755
				w.serial = ai[0].serial;
756
				ai[0].serial = aim->serial;
757
				aim->serial = w.serial;
758
			}
759
		}
760
	}
761
}
762
763
static void
764
unsort(struct line *f, int l, int *b)
765
{
766
	int *a, i;
767
768
	a = xcalloc(l + 1, sizeof(*a));
769
	for (i = 1; i <= l; i++)
770
		a[f[i].serial] = f[i].value;
771
	for (i = 1; i <= l; i++)
772
		b[i] = a[i];
773
	free(a);
774
}
775
776
static int
777
skipline(FILE *f)
778
{
779
	int i, c;
780
781
	for (i = 1; (c = getc(f)) != '\n' && c != EOF; i++)
782
		continue;
783
	return (i);
784
}
785
786
static void
787
output(FILE *f1, FILE *f2, int flags)
788
{
789
	int m, i0, i1, j0, j1;
790
791
	rewind(f1);
792
	rewind(f2);
793
	m = len[0];
794
	J[0] = 0;
795
	J[m + 1] = len[1] + 1;
796
	for (i0 = 1; i0 <= m; i0 = i1 + 1) {
797
		while (i0 <= m && J[i0] == J[i0 - 1] + 1)
798
			i0++;
799
		j0 = J[i0 - 1] + 1;
800
		i1 = i0 - 1;
801
		while (i1 < m && J[i1 + 1] == 0)
802
			i1++;
803
		j1 = J[i1 + 1] - 1;
804
		J[i1] = j1;
805
		change(f1, f2, i0, i1, j0, j1, flags);
806
	}
807
	if (m == 0)
808
		change(f1, f2, 1, 0, 1, len[1], flags);
809
	if (diff_format == D_IFDEF) {
810
		for (;;) {
811
#define	c i0
812
			if ((c = getc(f1)) == EOF)
813
				return;
814
			diff_output("%c", c);
815
		}
816
#undef c
817
	}
818
	if (anychange != 0) {
819
		if (diff_format == D_CONTEXT)
820
			dump_context_vec(f1, f2, flags);
821
		else if (diff_format == D_UNIFIED)
822
			dump_unified_vec(f1, f2, flags);
823
	}
824
}
825
826
static void
827
range(int a, int b, char *separator)
828
{
829
	diff_output("%d", a > b ? b : a);
830
	if (a < b)
831
		diff_output("%s%d", separator, b);
832
}
833
834
static void
835
uni_range(int a, int b)
836
{
837
	if (a < b)
838
		diff_output("%d,%d", a, b - a + 1);
839
	else if (a == b)
840
		diff_output("%d", b);
841
	else
842
		diff_output("%d,0", b);
843
}
844
845
static char *
846
preadline(int fd, size_t rlen, off_t off)
847
{
848
	char *line;
849
	ssize_t nr;
850
851
	line = xmalloc(rlen + 1);
852
	if ((nr = pread(fd, line, rlen, off)) < 0)
853
		err(D_ERROR, "preadline");
854
	line[nr] = '\0';
855
	return (line);
856
}
857
858
static int
859
ignoreline(char *line)
860
{
861
	int ret;
862
863
	ret = regexec(diff_ignore_re, line, 0, NULL, 0);
864
	free(line);
865
	return (ret == 0);	/* if it matched, it should be ignored. */
866
}
867
868
/*
869
 * Indicate that there is a difference between lines a and b of the from file
870
 * to get to lines c to d of the to file.  If a is greater then b then there
871
 * are no lines in the from file involved and this means that there were
872
 * lines appended (beginning at b).  If c is greater than d then there are
873
 * lines missing from the to file.
874
 */
875
static void
876
change(FILE *f1, FILE *f2, int a, int b, int c, int d, int flags)
877
{
878
	static size_t max_context = 64;
879
	char buf[64];
880
	struct tm *t;
881
	int i;
882
883
	if (diff_format != D_IFDEF && a > b && c > d)
884
		return;
885
	if (diff_ignore_re != NULL) {
886
		char *line;
887
		/*
888
		 * All lines in the change, insert, or delete must
889
		 * match an ignore pattern for the change to be
890
		 * ignored.
891
		 */
892
		if (a <= b) {		/* Changes and deletes. */
893
			for (i = a; i <= b; i++) {
894
				line = preadline(fileno(f1),
895
				    ixold[i] - ixold[i - 1], ixold[i - 1]);
896
				if (!ignoreline(line))
897
					goto proceed;
898
			}
899
		}
900
		if (a > b || c <= d) {	/* Changes and inserts. */
901
			for (i = c; i <= d; i++) {
902
				line = preadline(fileno(f2),
903
				    ixnew[i] - ixnew[i - 1], ixnew[i - 1]);
904
				if (!ignoreline(line))
905
					goto proceed;
906
			}
907
		}
908
		return;
909
	}
910
proceed:
911
	if (diff_format == D_CONTEXT || diff_format == D_UNIFIED) {
912
		/*
913
		 * Allocate change records as needed.
914
		 */
915
		if (context_vec_ptr == context_vec_end - 1) {
916
			ptrdiff_t offset = context_vec_ptr - context_vec_start;
917
			max_context <<= 1;
918
			context_vec_start = xreallocarray(context_vec_start,
919
			    max_context, sizeof(*context_vec_start));
920
			context_vec_end = context_vec_start + max_context;
921
			context_vec_ptr = context_vec_start + offset;
922
		}
923
		if (anychange == 0) {
924
			/*
925
			 * Print the context/unidiff header first time through.
926
			 */
927
			t = localtime(&stb1.st_mtime);
928
			(void)strftime(buf, sizeof(buf),
929
			    "%Y/%m/%d %H:%M:%S", t);
930
931
			diff_output("%s %s	%s",
932
			    diff_format == D_CONTEXT ? "***" : "---", diff_file,
933
			    buf);
934
935
			if (diff_rev1 != NULL) {
936
				rcsnum_tostr(diff_rev1, buf, sizeof(buf));
937
				diff_output("\t%s", buf);
938
			}
939
940
			printf("\n");
941
942
			t = localtime(&stb2.st_mtime);
943
			(void)strftime(buf, sizeof(buf),
944
			    "%Y/%m/%d %H:%M:%S", t);
945
946
			diff_output("%s %s	%s",
947
			    diff_format == D_CONTEXT ? "---" : "+++", diff_file,
948
			    buf);
949
950
			if (diff_rev2 != NULL) {
951
				rcsnum_tostr(diff_rev2, buf, sizeof(buf));
952
				diff_output("\t%s", buf);
953
			}
954
955
			printf("\n");
956
			anychange = 1;
957
		} else if (a > context_vec_ptr->b + (2 * diff_context) + 1 &&
958
		    c > context_vec_ptr->d + (2 * diff_context) + 1) {
959
			/*
960
			 * If this change is more than 'diff_context' lines from the
961
			 * previous change, dump the record and reset it.
962
			 */
963
			if (diff_format == D_CONTEXT)
964
				dump_context_vec(f1, f2, flags);
965
			else
966
				dump_unified_vec(f1, f2, flags);
967
		}
968
		context_vec_ptr++;
969
		context_vec_ptr->a = a;
970
		context_vec_ptr->b = b;
971
		context_vec_ptr->c = c;
972
		context_vec_ptr->d = d;
973
		return;
974
	}
975
	if (anychange == 0)
976
		anychange = 1;
977
	switch (diff_format) {
978
	case D_BRIEF:
979
		return;
980
	case D_NORMAL:
981
		range(a, b, ",");
982
		diff_output("%c", a > b ? 'a' : c > d ? 'd' : 'c');
983
		if (diff_format == D_NORMAL)
984
			range(c, d, ",");
985
		diff_output("\n");
986
		break;
987
	case D_RCSDIFF:
988
		if (a > b)
989
			diff_output("a%d %d\n", b, d - c + 1);
990
		else {
991
			diff_output("d%d %d\n", a, b - a + 1);
992
993
			if (!(c > d))	/* add changed lines */
994
				diff_output("a%d %d\n", b, d - c + 1);
995
		}
996
		break;
997
	}
998
	if (diff_format == D_NORMAL || diff_format == D_IFDEF) {
999
		fetch(ixold, a, b, f1, '<', 1, flags);
1000
		if (a <= b && c <= d && diff_format == D_NORMAL)
1001
			diff_output("---\n");
1002
	}
1003
	fetch(ixnew, c, d, f2, diff_format == D_NORMAL ? '>' : '\0', 0, flags);
1004
	if (inifdef) {
1005
		diff_output("#endif /* %s */\n", ifdefname);
1006
		inifdef = 0;
1007
	}
1008
}
1009
1010
static void
1011
fetch(long *f, int a, int b, FILE *lb, int ch, int oldfile, int flags)
1012
{
1013
	long j, nc;
1014
	int i, c, col;
1015
1016
	/*
1017
	 * When doing #ifdef's, copy down to current line
1018
	 * if this is the first file, so that stuff makes it to output.
1019
	 */
1020
	if (diff_format == D_IFDEF && oldfile) {
1021
		long curpos = ftell(lb);
1022
		/* print through if append (a>b), else to (nb: 0 vs 1 orig) */
1023
		nc = f[a > b ? b : a - 1] - curpos;
1024
		for (i = 0; i < nc; i++)
1025
			diff_output("%c", getc(lb));
1026
	}
1027
	if (a > b)
1028
		return;
1029
	if (diff_format == D_IFDEF) {
1030
		if (inifdef) {
1031
			diff_output("#else /* %s%s */\n",
1032
			    oldfile == 1 ? "!" : "", ifdefname);
1033
		} else {
1034
			if (oldfile)
1035
				diff_output("#ifndef %s\n", ifdefname);
1036
			else
1037
				diff_output("#ifdef %s\n", ifdefname);
1038
		}
1039
		inifdef = 1 + oldfile;
1040
	}
1041
	for (i = a; i <= b; i++) {
1042
		fseek(lb, f[i - 1], SEEK_SET);
1043
		nc = f[i] - f[i - 1];
1044
		if (diff_format != D_IFDEF && ch != '\0') {
1045
			diff_output("%c", ch);
1046
			if (diff_format != D_UNIFIED)
1047
				diff_output(" ");
1048
		}
1049
		col = 0;
1050
		for (j = 0; j < nc; j++) {
1051
			if ((c = getc(lb)) == EOF) {
1052
				if (diff_format == D_RCSDIFF)
1053
					warnx("No newline at end of file");
1054
				else
1055
					diff_output("\n\\ No newline at end of "
1056
					    "file");
1057
				return;
1058
			}
1059
			if (c == '\t' && (flags & D_EXPANDTABS)) {
1060
				do {
1061
					diff_output(" ");
1062
				} while (++col & 7);
1063
			} else {
1064
				diff_output("%c", c);
1065
				col++;
1066
			}
1067
		}
1068
	}
1069
}
1070
1071
/*
1072
 * Hash function taken from Robert Sedgewick, Algorithms in C, 3d ed., p 578.
1073
 */
1074
static int
1075
readhash(FILE *f, int flags)
1076
{
1077
	int i, t, space;
1078
	int sum;
1079
1080
	sum = 1;
1081
	space = 0;
1082
	if ((flags & (D_FOLDBLANKS|D_IGNOREBLANKS)) == 0) {
1083
		if (flags & D_IGNORECASE)
1084
			for (i = 0; (t = getc(f)) != '\n'; i++) {
1085
				if (t == EOF) {
1086
					if (i == 0)
1087
						return (0);
1088
					break;
1089
				}
1090
				sum = sum * 127 + chrtran[t];
1091
			}
1092
		else
1093
			for (i = 0; (t = getc(f)) != '\n'; i++) {
1094
				if (t == EOF) {
1095
					if (i == 0)
1096
						return (0);
1097
					break;
1098
				}
1099
				sum = sum * 127 + t;
1100
			}
1101
	} else {
1102
		for (i = 0;;) {
1103
			switch (t = getc(f)) {
1104
			case '\t':
1105
			case '\r':
1106
			case '\v':
1107
			case '\f':
1108
			case ' ':
1109
				space++;
1110
				continue;
1111
			default:
1112
				if (space && (flags & D_IGNOREBLANKS) == 0) {
1113
					i++;
1114
					space = 0;
1115
				}
1116
				sum = sum * 127 + chrtran[t];
1117
				i++;
1118
				continue;
1119
			case EOF:
1120
				if (i == 0)
1121
					return (0);
1122
				/* FALLTHROUGH */
1123
			case '\n':
1124
				break;
1125
			}
1126
			break;
1127
		}
1128
	}
1129
	/*
1130
	 * There is a remote possibility that we end up with a zero sum.
1131
	 * Zero is used as an EOF marker, so return 1 instead.
1132
	 */
1133
	return (sum == 0 ? 1 : sum);
1134
}
1135
1136
static int
1137
asciifile(FILE *f)
1138
{
1139
	unsigned char buf[BUFSIZ];
1140
	size_t cnt;
1141
1142
	if (f == NULL)
1143
		return (1);
1144
1145
	rewind(f);
1146
	cnt = fread(buf, 1, sizeof(buf), f);
1147
	return (memchr(buf, '\0', cnt) == NULL);
1148
}
1149
1150
#define begins_with(s, pre) (strncmp(s, pre, sizeof(pre)-1) == 0)
1151
1152
static char *
1153
match_function(const long *f, int pos, FILE *fp)
1154
{
1155
	unsigned char buf[FUNCTION_CONTEXT_SIZE];
1156
	size_t nc;
1157
	int last = lastline;
1158
	char *state = NULL;
1159
1160
	lastline = pos;
1161
	while (pos > last) {
1162
		fseek(fp, f[pos - 1], SEEK_SET);
1163
		nc = f[pos] - f[pos - 1];
1164
		if (nc >= sizeof(buf))
1165
			nc = sizeof(buf) - 1;
1166
		nc = fread(buf, 1, nc, fp);
1167
		if (nc > 0) {
1168
			buf[nc] = '\0';
1169
			buf[strcspn(buf, "\n")] = '\0';
1170
			if (isalpha(buf[0]) || buf[0] == '_' || buf[0] == '$') {
1171
				if (begins_with(buf, "private:")) {
1172
					if (!state)
1173
						state = " (private)";
1174
				} else if (begins_with(buf, "protected:")) {
1175
					if (!state)
1176
						state = " (protected)";
1177
				} else if (begins_with(buf, "public:")) {
1178
					if (!state)
1179
						state = " (public)";
1180
				} else {
1181
					if (strlcpy(lastbuf, buf,
1182
					    sizeof(lastbuf)) >= sizeof(lastbuf))
1183
						errx(1,
1184
						    "match_function: strlcpy");
1185
					lastmatchline = pos;
1186
					return lastbuf;
1187
				}
1188
			}
1189
		}
1190
		pos--;
1191
	}
1192
	return lastmatchline > 0 ? lastbuf : NULL;
1193
}
1194
1195
/* dump accumulated "context" diff changes */
1196
static void
1197
dump_context_vec(FILE *f1, FILE *f2, int flags)
1198
{
1199
	struct context_vec *cvp = context_vec_start;
1200
	int lowa, upb, lowc, upd, do_output;
1201
	int a, b, c, d;
1202
	char ch, *f;
1203
1204
	if (context_vec_start > context_vec_ptr)
1205
		return;
1206
1207
	b = d = 0;		/* gcc */
1208
	lowa = MAXIMUM(1, cvp->a - diff_context);
1209
	upb = MINIMUM(len[0], context_vec_ptr->b + diff_context);
1210
	lowc = MAXIMUM(1, cvp->c - diff_context);
1211
	upd = MINIMUM(len[1], context_vec_ptr->d + diff_context);
1212
1213
	diff_output("***************");
1214
	if ((flags & D_PROTOTYPE)) {
1215
		f = match_function(ixold, lowa-1, f1);
1216
		if (f != NULL)
1217
			diff_output(" %s", f);
1218
	}
1219
	diff_output("\n*** ");
1220
	range(lowa, upb, ",");
1221
	diff_output(" ****\n");
1222
1223
	/*
1224
	 * Output changes to the "old" file.  The first loop suppresses
1225
	 * output if there were no changes to the "old" file (we'll see
1226
	 * the "old" lines as context in the "new" list).
1227
	 */
1228
	do_output = 0;
1229
	for (; cvp <= context_vec_ptr; cvp++)
1230
		if (cvp->a <= cvp->b) {
1231
			cvp = context_vec_start;
1232
			do_output++;
1233
			break;
1234
		}
1235
	if (do_output) {
1236
		while (cvp <= context_vec_ptr) {
1237
			a = cvp->a;
1238
			b = cvp->b;
1239
			c = cvp->c;
1240
			d = cvp->d;
1241
1242
			if (a <= b && c <= d)
1243
				ch = 'c';
1244
			else
1245
				ch = (a <= b) ? 'd' : 'a';
1246
1247
			if (ch == 'a')
1248
				fetch(ixold, lowa, b, f1, ' ', 0, flags);
1249
			else {
1250
				fetch(ixold, lowa, a - 1, f1, ' ', 0, flags);
1251
				fetch(ixold, a, b, f1,
1252
				    ch == 'c' ? '!' : '-', 0, flags);
1253
			}
1254
			lowa = b + 1;
1255
			cvp++;
1256
		}
1257
		fetch(ixold, b + 1, upb, f1, ' ', 0, flags);
1258
	}
1259
	/* output changes to the "new" file */
1260
	diff_output("--- ");
1261
	range(lowc, upd, ",");
1262
	diff_output(" ----\n");
1263
1264
	do_output = 0;
1265
	for (cvp = context_vec_start; cvp <= context_vec_ptr; cvp++)
1266
		if (cvp->c <= cvp->d) {
1267
			cvp = context_vec_start;
1268
			do_output++;
1269
			break;
1270
		}
1271
	if (do_output) {
1272
		while (cvp <= context_vec_ptr) {
1273
			a = cvp->a;
1274
			b = cvp->b;
1275
			c = cvp->c;
1276
			d = cvp->d;
1277
1278
			if (a <= b && c <= d)
1279
				ch = 'c';
1280
			else
1281
				ch = (a <= b) ? 'd' : 'a';
1282
1283
			if (ch == 'd')
1284
				fetch(ixnew, lowc, d, f2, ' ', 0, flags);
1285
			else {
1286
				fetch(ixnew, lowc, c - 1, f2, ' ', 0, flags);
1287
				fetch(ixnew, c, d, f2,
1288
				    ch == 'c' ? '!' : '+', 0, flags);
1289
			}
1290
			lowc = d + 1;
1291
			cvp++;
1292
		}
1293
		fetch(ixnew, d + 1, upd, f2, ' ', 0, flags);
1294
	}
1295
	context_vec_ptr = context_vec_start - 1;
1296
}
1297
1298
/* dump accumulated "unified" diff changes */
1299
static void
1300
dump_unified_vec(FILE *f1, FILE *f2, int flags)
1301
{
1302
	struct context_vec *cvp = context_vec_start;
1303
	int lowa, upb, lowc, upd;
1304
	int a, b, c, d;
1305
	char ch, *f;
1306
1307
	if (context_vec_start > context_vec_ptr)
1308
		return;
1309
1310
	d = 0; /* gcc */
1311
	lowa = MAXIMUM(1, cvp->a - diff_context);
1312
	upb = MINIMUM(len[0], context_vec_ptr->b + diff_context);
1313
	lowc = MAXIMUM(1, cvp->c - diff_context);
1314
	upd = MINIMUM(len[1], context_vec_ptr->d + diff_context);
1315
1316
	diff_output("@@ -");
1317
	uni_range(lowa, upb);
1318
	diff_output(" +");
1319
	uni_range(lowc, upd);
1320
	diff_output(" @@");
1321
	if ((flags & D_PROTOTYPE)) {
1322
		f = match_function(ixold, lowa-1, f1);
1323
		if (f != NULL)
1324
			diff_output(" %s", f);
1325
	}
1326
	diff_output("\n");
1327
1328
	/*
1329
	 * Output changes in "unified" diff format--the old and new lines
1330
	 * are printed together.
1331
	 */
1332
	for (; cvp <= context_vec_ptr; cvp++) {
1333
		a = cvp->a;
1334
		b = cvp->b;
1335
		c = cvp->c;
1336
		d = cvp->d;
1337
1338
		/*
1339
		 * c: both new and old changes
1340
		 * d: only changes in the old file
1341
		 * a: only changes in the new file
1342
		 */
1343
		if (a <= b && c <= d)
1344
			ch = 'c';
1345
		else
1346
			ch = (a <= b) ? 'd' : 'a';
1347
1348
		switch (ch) {
1349
		case 'c':
1350
			fetch(ixold, lowa, a - 1, f1, ' ', 0, flags);
1351
			fetch(ixold, a, b, f1, '-', 0, flags);
1352
			fetch(ixnew, c, d, f2, '+', 0, flags);
1353
			break;
1354
		case 'd':
1355
			fetch(ixold, lowa, a - 1, f1, ' ', 0, flags);
1356
			fetch(ixold, a, b, f1, '-', 0, flags);
1357
			break;
1358
		case 'a':
1359
			fetch(ixnew, lowc, c - 1, f2, ' ', 0, flags);
1360
			fetch(ixnew, c, d, f2, '+', 0, flags);
1361
			break;
1362
		}
1363
		lowa = b + 1;
1364
		lowc = d + 1;
1365
	}
1366
	fetch(ixnew, d + 1, upd, f2, ' ', 0, flags);
1367
1368
	context_vec_ptr = context_vec_start - 1;
1369
}
1370
1371
void
1372
diff_output(const char *fmt, ...)
1373
{
1374
	va_list vap;
1375
	int i;
1376
	char *str;
1377
1378
	va_start(vap, fmt);
1379
	i = vasprintf(&str, fmt, vap);
1380
	va_end(vap);
1381
	if (i == -1)
1382
		err(1, "diff_output");
1383
	if (diffbuf != NULL)
1384
		buf_append(diffbuf, str, strlen(str));
1385
	else
1386
		printf("%s", str);
1387
	free(str);
1388
}