GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: usr.bin/cvs/diff_internals.c Lines: 0 620 0.0 %
Date: 2017-11-13 Branches: 0 538 0.0 %

Line Branch Exec Source
1
/*	$OpenBSD: diff_internals.c,v 1.39 2016/10/15 22:20:17 millert 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/types.h>
68
#include <sys/stat.h>
69
70
#include <ctype.h>
71
#include <errno.h>
72
#include <regex.h>
73
#include <stddef.h>
74
#include <stdint.h>
75
#include <stdio.h>
76
#include <stdlib.h>
77
#include <string.h>
78
#include <time.h>
79
#include <unistd.h>
80
81
#include "cvs.h"
82
#include "diff.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	 diff_head(void);
189
static void	 rdiff_head(void);
190
static void	 change(FILE *, FILE *, int, int, int, int, int);
191
static void	 sort(struct line *, int);
192
static int	 ignoreline(char *);
193
static int	 asciifile(FILE *);
194
static void	 fetch(long *, int, int, FILE *, int, int, int);
195
static int	 newcand(int, int, int);
196
static int	 search(int *, int, int);
197
static int	 skipline(FILE *);
198
static int	 isqrt(int);
199
static int	 stone(int *, int, int *, int *, int);
200
static int	 readhash(FILE *, int);
201
static int	 files_differ(FILE *, FILE *);
202
static char	*match_function(const long *, int, FILE *);
203
static char	*preadline(int, size_t, off_t);
204
205
static int Tflag;
206
int diff_context = 3;
207
int diff_format = D_NORMAL;
208
const char *diff_file1 = NULL;
209
const char *diff_file2 = NULL;
210
RCSNUM *diff_rev1 = NULL;
211
RCSNUM *diff_rev2 = NULL;
212
char diffargs[512];
213
static struct stat stb1, stb2;
214
static char *ifdefname, *ignore_pats;
215
regex_t ignore_re;
216
217
static int  *J;			/* will be overlaid on class */
218
static int  *class;		/* will be overlaid on file[0] */
219
static int  *klist;		/* will be overlaid on file[0] after class */
220
static int  *member;		/* will be overlaid on file[1] */
221
static int   clen;
222
static int   inifdef;		/* whether or not we are in a #ifdef block */
223
static int   len[2];
224
static int   pref, suff;	/* length of prefix and suffix */
225
static int   slen[2];
226
static int   anychange;
227
static long *ixnew;		/* will be overlaid on file[1] */
228
static long *ixold;		/* will be overlaid on klist */
229
static struct cand *clist;	/* merely a free storage pot for candidates */
230
static int   clistlen;		/* the length of clist */
231
static struct line *sfile[2];	/* shortened by pruning common prefix/suffix */
232
static u_char *chrtran;		/* translation table for case-folding */
233
static struct context_vec *context_vec_start;
234
static struct context_vec *context_vec_end;
235
static struct context_vec *context_vec_ptr;
236
237
#define FUNCTION_CONTEXT_SIZE	55
238
static char lastbuf[FUNCTION_CONTEXT_SIZE];
239
static int lastline;
240
static int lastmatchline;
241
BUF  *diffbuf = NULL;
242
243
244
/*
245
 * chrtran points to one of 2 translation tables: cup2low if folding upper to
246
 * lower case clow2low if not folding case
247
 */
248
u_char clow2low[256] = {
249
	0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a,
250
	0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15,
251
	0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20,
252
	0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b,
253
	0x2c, 0x2d, 0x2e, 0x2f, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36,
254
	0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, 0x40, 0x41,
255
	0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49, 0x4a, 0x4b, 0x4c,
256
	0x4d, 0x4e, 0x4f, 0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57,
257
	0x58, 0x59, 0x5a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f, 0x60, 0x61, 0x62,
258
	0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d,
259
	0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78,
260
	0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x80, 0x81, 0x82, 0x83,
261
	0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e,
262
	0x8f, 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99,
263
	0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f, 0xa0, 0xa1, 0xa2, 0xa3, 0xa4,
264
	0xa5, 0xa6, 0xa7, 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
265
	0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba,
266
	0xbb, 0xbc, 0xbd, 0xbe, 0xbf, 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5,
267
	0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, 0xd0,
268
	0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, 0xdb,
269
	0xdc, 0xdd, 0xde, 0xdf, 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6,
270
	0xe7, 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef, 0xf0, 0xf1,
271
	0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, 0xf9, 0xfa, 0xfb, 0xfc,
272
	0xfd, 0xfe, 0xff
273
};
274
275
u_char cup2low[256] = {
276
	0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a,
277
	0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15,
278
	0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20,
279
	0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b,
280
	0x2c, 0x2d, 0x2e, 0x2f, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36,
281
	0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, 0x60, 0x61,
282
	0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c,
283
	0x6d, 0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
284
	0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x60, 0x61, 0x62,
285
	0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d,
286
	0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78,
287
	0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x80, 0x81, 0x82, 0x83,
288
	0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e,
289
	0x8f, 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99,
290
	0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f, 0xa0, 0xa1, 0xa2, 0xa3, 0xa4,
291
	0xa5, 0xa6, 0xa7, 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
292
	0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba,
293
	0xbb, 0xbc, 0xbd, 0xbe, 0xbf, 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5,
294
	0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, 0xd0,
295
	0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, 0xdb,
296
	0xdc, 0xdd, 0xde, 0xdf, 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6,
297
	0xe7, 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef, 0xf0, 0xf1,
298
	0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, 0xf9, 0xfa, 0xfb, 0xfc,
299
	0xfd, 0xfe, 0xff
300
};
301
302
int
303
diffreg(const char *file1, const char *file2, int _fd1, int _fd2,
304
    BUF *out, int flags)
305
{
306
	FILE *f1, *f2;
307
	int i, rval, fd1, fd2;
308
309
	diff_file1 = file1;
310
	diff_file2 = file2;
311
	f1 = f2 = NULL;
312
	rval = D_SAME;
313
	anychange = 0;
314
	lastline = 0;
315
	lastmatchline = 0;
316
	context_vec_ptr = context_vec_start - 1;
317
	if (flags & D_IGNORECASE)
318
		chrtran = cup2low;
319
	else
320
		chrtran = clow2low;
321
	if (out != NULL)
322
		diffbuf = out;
323
324
	fd1 = dup(_fd1);
325
	if (fd1 == -1)
326
		fatal("diffreg: dup: %s", strerror(errno));
327
328
	fd2 = dup(_fd2);
329
	if (fd2 == -1)
330
		fatal("diffreg: dup: %s", strerror(errno));
331
332
	if (lseek(fd1, 0, SEEK_SET) < 0)
333
		fatal("diffreg: lseek: %s", strerror(errno));
334
335
	f1 = fdopen(fd1, "r");
336
	if (f1 == NULL) {
337
		cvs_log(LP_ERR, "%s", file1);
338
		goto closem;
339
	}
340
341
	if (lseek(fd2, 0, SEEK_SET) < 0)
342
		fatal("diffreg: lseek: %s", strerror(errno));
343
344
	f2 = fdopen(fd2, "r");
345
	if (f2 == NULL) {
346
		cvs_log(LP_ERR, "%s", file2);
347
		goto closem;
348
	}
349
350
	if (fstat(fd1, &stb1) < 0) {
351
		cvs_log(LP_ERR, "%s", file1);
352
		goto closem;
353
	}
354
355
	if (fstat(fd2, &stb2) < 0) {
356
		cvs_log(LP_ERR, "%s", file2);
357
		goto closem;
358
	}
359
360
	switch (files_differ(f1, f2)) {
361
	case 0:
362
		goto closem;
363
	case 1:
364
		break;
365
	default:
366
		/* error */
367
		goto closem;
368
	}
369
370
	if ((flags & D_FORCEASCII) == 0 &&
371
	    (!asciifile(f1) || !asciifile(f2))) {
372
		rval = D_BINARY;
373
		goto closem;
374
	}
375
376
	prepare(0, f1, stb1.st_size, flags);
377
	prepare(1, f2, stb2.st_size, flags);
378
379
	prune();
380
	sort(sfile[0], slen[0]);
381
	sort(sfile[1], slen[1]);
382
383
	member = (int *)file[1];
384
	equiv(sfile[0], slen[0], sfile[1], slen[1], member);
385
	member = xreallocarray(member, slen[1] + 2, sizeof(*member));
386
387
	class = (int *)file[0];
388
	unsort(sfile[0], slen[0], class);
389
	class = xreallocarray(class, slen[0] + 2, sizeof(*class));
390
391
	klist = xcalloc(slen[0] + 2, sizeof(*klist));
392
	clen = 0;
393
	clistlen = 100;
394
	clist = xcalloc(clistlen, sizeof(*clist));
395
	i = stone(class, slen[0], member, klist, flags);
396
	free(member);
397
	free(class);
398
399
	J = xreallocarray(J, len[0] + 2, sizeof(*J));
400
	unravel(klist[i]);
401
	free(clist);
402
	free(klist);
403
404
	ixold = xreallocarray(ixold, len[0] + 2, sizeof(*ixold));
405
	ixnew = xreallocarray(ixnew, len[1] + 2, sizeof(*ixnew));
406
	check(f1, f2, flags);
407
	output(f1, f2, flags);
408
409
closem:
410
	if (anychange) {
411
		if (rval == D_SAME)
412
			rval = D_DIFFER;
413
	}
414
	if (f1 != NULL)
415
		fclose(f1);
416
	if (f2 != NULL)
417
		fclose(f2);
418
419
	return (rval);
420
}
421
422
/*
423
 * Check to see if the given files differ.
424
 * Returns 0 if they are the same, 1 if different, and -1 on error.
425
 * XXX - could use code from cmp(1) [faster]
426
 */
427
static int
428
files_differ(FILE *f1, FILE *f2)
429
{
430
	char buf1[BUFSIZ], buf2[BUFSIZ];
431
	size_t i, j;
432
433
	if (stb1.st_size != stb2.st_size)
434
		return (1);
435
	for (;;) {
436
		i = fread(buf1, 1, sizeof(buf1), f1);
437
		j = fread(buf2, 1, sizeof(buf2), f2);
438
		if ((!i && ferror(f1)) || (!j && ferror(f2)))
439
			return (-1);
440
		if (i != j)
441
			return (1);
442
		if (i == 0)
443
			return (0);
444
		if (memcmp(buf1, buf2, i) != 0)
445
			return (1);
446
	}
447
}
448
449
static void
450
prepare(int i, FILE *fd, off_t filesize, int flags)
451
{
452
	struct line *p;
453
	int j, h;
454
	size_t sz;
455
456
	rewind(fd);
457
458
	sz = ((uintmax_t)filesize <= SIZE_MAX ? (size_t)filesize : SIZE_MAX) / 25;
459
	if (sz < 100)
460
		sz = 100;
461
462
	p = xcalloc(sz + 3, sizeof(*p));
463
	for (j = 0; (h = readhash(fd, flags));) {
464
		if ((size_t)j == sz) {
465
			sz = sz * 3 / 2;
466
			p = xreallocarray(p, sz + 3, sizeof(*p));
467
		}
468
		p[++j].value = h;
469
	}
470
	len[i] = j;
471
	file[i] = p;
472
}
473
474
static void
475
prune(void)
476
{
477
	int i, j;
478
479
	for (pref = 0; pref < len[0] && pref < len[1] &&
480
	    file[0][pref + 1].value == file[1][pref + 1].value;
481
	    pref++)
482
		;
483
	for (suff = 0; suff < len[0] - pref && suff < len[1] - pref &&
484
	    file[0][len[0] - suff].value == file[1][len[1] - suff].value;
485
	    suff++)
486
		;
487
	for (j = 0; j < 2; j++) {
488
		sfile[j] = file[j] + pref;
489
		slen[j] = len[j] - pref - suff;
490
		for (i = 0; i <= slen[j]; i++)
491
			sfile[j][i].serial = i;
492
	}
493
}
494
495
static void
496
equiv(struct line *a, int n, struct line *b, int m, int *c)
497
{
498
	int i, j;
499
500
	i = j = 1;
501
	while (i <= n && j <= m) {
502
		if (a[i].value < b[j].value)
503
			a[i++].value = 0;
504
		else if (a[i].value == b[j].value)
505
			a[i++].value = j;
506
		else
507
			j++;
508
	}
509
	while (i <= n)
510
		a[i++].value = 0;
511
	b[m + 1].value = 0;
512
	j = 0;
513
	while (++j <= m) {
514
		c[j] = -b[j].serial;
515
		while (b[j + 1].value == b[j].value) {
516
			j++;
517
			c[j] = b[j].serial;
518
		}
519
	}
520
	c[j] = -1;
521
}
522
523
/* Code taken from ping.c */
524
static int
525
isqrt(int n)
526
{
527
	int y, x = 1;
528
529
	if (n == 0)
530
		return (0);
531
532
	do { /* newton was a stinker */
533
		y = x;
534
		x = n / x;
535
		x += y;
536
		x /= 2;
537
	} while ((x - y) > 1 || (x - y) < -1);
538
539
	return (x);
540
}
541
542
static int
543
stone(int *a, int n, int *b, int *c, int flags)
544
{
545
	int i, k, y, j, l;
546
	int oldc, tc, oldl, sq;
547
	u_int numtries, bound;
548
549
	if (flags & D_MINIMAL)
550
		bound = UINT_MAX;
551
	else {
552
		sq = isqrt(n);
553
		bound = MAXIMUM(256, sq);
554
	}
555
556
	k = 0;
557
	c[0] = newcand(0, 0, 0);
558
	for (i = 1; i <= n; i++) {
559
		j = a[i];
560
		if (j == 0)
561
			continue;
562
		y = -b[j];
563
		oldl = 0;
564
		oldc = c[0];
565
		numtries = 0;
566
		do {
567
			if (y <= clist[oldc].y)
568
				continue;
569
			l = search(c, k, y);
570
			if (l != oldl + 1)
571
				oldc = c[l - 1];
572
			if (l <= k) {
573
				if (clist[c[l]].y <= y)
574
					continue;
575
				tc = c[l];
576
				c[l] = newcand(i, y, oldc);
577
				oldc = tc;
578
				oldl = l;
579
				numtries++;
580
			} else {
581
				c[l] = newcand(i, y, oldc);
582
				k++;
583
				break;
584
			}
585
		} while ((y = b[++j]) > 0 && numtries < bound);
586
	}
587
	return (k);
588
}
589
590
static int
591
newcand(int x, int y, int pred)
592
{
593
	struct cand *q;
594
595
	if (clen == clistlen) {
596
		clistlen = clistlen * 11 / 10;
597
		clist = xreallocarray(clist, clistlen, sizeof(*clist));
598
	}
599
	q = clist + clen;
600
	q->x = x;
601
	q->y = y;
602
	q->pred = pred;
603
	return (clen++);
604
}
605
606
static int
607
search(int *c, int k, int y)
608
{
609
	int i, j, l, t;
610
611
	if (clist[c[k]].y < y)	/* quick look for typical case */
612
		return (k + 1);
613
	i = 0;
614
	j = k + 1;
615
	for (;;) {
616
		l = (i + j) / 2;
617
		if (l <= i)
618
			break;
619
		t = clist[c[l]].y;
620
		if (t > y)
621
			j = l;
622
		else if (t < y)
623
			i = l;
624
		else
625
			return (l);
626
	}
627
	return (l + 1);
628
}
629
630
static void
631
unravel(int p)
632
{
633
	struct cand *q;
634
	int i;
635
636
	for (i = 0; i <= len[0]; i++)
637
		J[i] = i <= pref ? i :
638
		    i > len[0] - suff ? i + len[1] - len[0] : 0;
639
	for (q = clist + p; q->y != 0; q = clist + q->pred)
640
		J[q->x + pref] = q->y + pref;
641
}
642
643
/*
644
 * Check does double duty:
645
 *  1.	ferret out any fortuitous correspondences due
646
 *	to confounding by hashing (which result in "jackpot")
647
 *  2.  collect random access indexes to the two files
648
 */
649
static void
650
check(FILE *f1, FILE *f2, int flags)
651
{
652
	int i, j, jackpot, c, d;
653
	long ctold, ctnew;
654
655
	rewind(f1);
656
	rewind(f2);
657
	j = 1;
658
	ixold[0] = ixnew[0] = 0;
659
	jackpot = 0;
660
	ctold = ctnew = 0;
661
	for (i = 1; i <= len[0]; i++) {
662
		if (J[i] == 0) {
663
			ixold[i] = ctold += skipline(f1);
664
			continue;
665
		}
666
		while (j < J[i]) {
667
			ixnew[j] = ctnew += skipline(f2);
668
			j++;
669
		}
670
		if (flags & (D_FOLDBLANKS|D_IGNOREBLANKS|D_IGNORECASE)) {
671
			for (;;) {
672
				c = getc(f1);
673
				d = getc(f2);
674
				/*
675
				 * GNU diff ignores a missing newline
676
				 * in one file for -b or -w.
677
				 */
678
				if ((flags & (D_FOLDBLANKS|D_IGNOREBLANKS)) &&
679
				    ((c == EOF && d == '\n') ||
680
				    (c == '\n' && d == EOF))) {
681
					break;
682
				}
683
				ctold++;
684
				ctnew++;
685
				if ((flags & D_FOLDBLANKS) && isspace(c) &&
686
				    isspace(d)) {
687
					do {
688
						if (c == '\n')
689
							break;
690
						ctold++;
691
					} while (isspace(c = getc(f1)));
692
					do {
693
						if (d == '\n')
694
							break;
695
						ctnew++;
696
					} while (isspace(d = getc(f2)));
697
				} else if ((flags & D_IGNOREBLANKS)) {
698
					while (isspace(c) && c != '\n') {
699
						c = getc(f1);
700
						ctold++;
701
					}
702
					while (isspace(d) && d != '\n') {
703
						d = getc(f2);
704
						ctnew++;
705
					}
706
				}
707
				if (chrtran[c] != chrtran[d]) {
708
					jackpot++;
709
					J[i] = 0;
710
					if (c != '\n' && c != EOF)
711
						ctold += skipline(f1);
712
					if (d != '\n' && c != EOF)
713
						ctnew += skipline(f2);
714
					break;
715
				}
716
				if (c == '\n' || c == EOF)
717
					break;
718
			}
719
		} else {
720
			for (;;) {
721
				ctold++;
722
				ctnew++;
723
				if ((c = getc(f1)) != (d = getc(f2))) {
724
					/* jackpot++; */
725
					J[i] = 0;
726
					if (c != '\n' && c != EOF)
727
						ctold += skipline(f1);
728
					if (d != '\n' && c != EOF)
729
						ctnew += skipline(f2);
730
					break;
731
				}
732
				if (c == '\n' || c == EOF)
733
					break;
734
			}
735
		}
736
		ixold[i] = ctold;
737
		ixnew[j] = ctnew;
738
		j++;
739
	}
740
	for (; j <= len[1]; j++)
741
		ixnew[j] = ctnew += skipline(f2);
742
	/*
743
	 * if (jackpot)
744
	 *	fprintf(stderr, "jackpot\n");
745
	 */
746
}
747
748
/* shellsort CACM #201 */
749
static void
750
sort(struct line *a, int n)
751
{
752
	struct line *ai, *aim, w;
753
	int j, m = 0, k;
754
755
	if (n == 0)
756
		return;
757
	for (j = 1; j <= n; j *= 2)
758
		m = 2 * j - 1;
759
	for (m /= 2; m != 0; m /= 2) {
760
		k = n - m;
761
		for (j = 1; j <= k; j++) {
762
			for (ai = &a[j]; ai > a; ai -= m) {
763
				aim = &ai[m];
764
				if (aim < ai)
765
					break;	/* wraparound */
766
				if (aim->value > ai[0].value ||
767
				    (aim->value == ai[0].value &&
768
					aim->serial > ai[0].serial))
769
					break;
770
				w.value = ai[0].value;
771
				ai[0].value = aim->value;
772
				aim->value = w.value;
773
				w.serial = ai[0].serial;
774
				ai[0].serial = aim->serial;
775
				aim->serial = w.serial;
776
			}
777
		}
778
	}
779
}
780
781
static void
782
unsort(struct line *f, int l, int *b)
783
{
784
	int *a, i;
785
786
	a = xcalloc(l + 1, sizeof(*a));
787
	for (i = 1; i <= l; i++)
788
		a[f[i].serial] = f[i].value;
789
	for (i = 1; i <= l; i++)
790
		b[i] = a[i];
791
	free(a);
792
}
793
794
static int
795
skipline(FILE *f)
796
{
797
	int i, c;
798
799
	for (i = 1; (c = getc(f)) != '\n' && c != EOF; i++)
800
		continue;
801
	return (i);
802
}
803
804
static void
805
output(FILE *f1, FILE *f2, int flags)
806
{
807
	int m, i0, i1, j0, j1;
808
809
	rewind(f1);
810
	rewind(f2);
811
	m = len[0];
812
	J[0] = 0;
813
	J[m + 1] = len[1] + 1;
814
	for (i0 = 1; i0 <= m; i0 = i1 + 1) {
815
		while (i0 <= m && J[i0] == J[i0 - 1] + 1)
816
			i0++;
817
		j0 = J[i0 - 1] + 1;
818
		i1 = i0 - 1;
819
		while (i1 < m && J[i1 + 1] == 0)
820
			i1++;
821
		j1 = J[i1 + 1] - 1;
822
		J[i1] = j1;
823
		change(f1, f2, i0, i1, j0, j1, flags);
824
	}
825
	if (m == 0)
826
		change(f1, f2, 1, 0, 1, len[1], flags);
827
	if (diff_format == D_IFDEF) {
828
		for (;;) {
829
#define	c i0
830
			if ((c = getc(f1)) == EOF)
831
				return;
832
			diff_output("%c", c);
833
		}
834
#undef c
835
	}
836
	if (anychange != 0) {
837
		if (diff_format == D_CONTEXT)
838
			dump_context_vec(f1, f2, flags);
839
		else if (diff_format == D_UNIFIED)
840
			dump_unified_vec(f1, f2, flags);
841
	}
842
}
843
844
static void
845
range(int a, int b, char *separator)
846
{
847
	diff_output("%d", a > b ? b : a);
848
	if (a < b)
849
		diff_output("%s%d", separator, b);
850
}
851
852
static void
853
uni_range(int a, int b)
854
{
855
	if (a < b)
856
		diff_output("%d,%d", a, b - a + 1);
857
	else if (a == b)
858
		diff_output("%d", b);
859
	else
860
		diff_output("%d,0", b);
861
}
862
863
static char *
864
preadline(int fd, size_t rlen, off_t off)
865
{
866
	char *line;
867
	ssize_t nr;
868
869
	line = xmalloc(rlen + 1);
870
	if ((nr = pread(fd, line, rlen, off)) < 0)
871
		fatal("preadline: %s", strerror(errno));
872
	line[nr] = '\0';
873
	return (line);
874
}
875
876
static int
877
ignoreline(char *line)
878
{
879
	int ret;
880
881
	ret = regexec(&ignore_re, line, 0, NULL, 0);
882
	free(line);
883
	return (ret == 0);	/* if it matched, it should be ignored. */
884
}
885
886
static void
887
diff_head(void)
888
{
889
	char buf[64];
890
	struct tm t;
891
	time_t curr_time;
892
893
	if (diff_rev1 != NULL) {
894
		gmtime_r(&stb1.st_mtime, &t);
895
	} else {
896
		time(&curr_time);
897
		localtime_r(&curr_time, &t);
898
	}
899
900
	(void)strftime(buf, sizeof(buf), "%b %G %H:%M:%S -0000", &t);
901
	diff_output("%s %s	%d %s", diff_format == D_CONTEXT ?
902
	    "***" : "---", diff_file1, t.tm_mday, buf);
903
904
	if (diff_rev1 != NULL) {
905
		rcsnum_tostr(diff_rev1, buf, sizeof(buf));
906
		diff_output("\t%s", buf);
907
	}
908
909
	diff_output("\n");
910
911
	gmtime_r(&stb2.st_mtime, &t);
912
913
	(void)strftime(buf, sizeof(buf), "%b %G %H:%M:%S -0000", &t);
914
	diff_output("%s %s	%d %s", diff_format == D_CONTEXT ?
915
	    "---" : "+++", diff_file2, t.tm_mday, buf);
916
917
	if (diff_rev2 != NULL) {
918
		rcsnum_tostr(diff_rev2, buf, sizeof(buf));
919
		diff_output("\t%s", buf);
920
	}
921
922
	diff_output("\n");
923
}
924
925
static void
926
rdiff_head(void)
927
{
928
	char buf[64];
929
	struct tm t;
930
	time_t curr_time;
931
932
	diff_output("%s ", diff_format == D_CONTEXT ? "***" : "---");
933
934
	if (diff_rev1 == NULL) {
935
		diff_output("%s", CVS_PATH_DEVNULL);
936
		gmtime_r(&stb1.st_atime, &t);
937
	} else {
938
		rcsnum_tostr(diff_rev1, buf, sizeof(buf));
939
		diff_output("%s:%s", diff_file1, buf);
940
		localtime_r(&stb1.st_mtime, &t);
941
	}
942
943
	(void)strftime(buf, sizeof(buf), "%a %b %e %H:%M:%S %G", &t);
944
	diff_output("\t%s\n", buf);
945
946
	if (diff_rev2 != NULL) {
947
		localtime_r(&stb2.st_mtime, &t);
948
	} else {
949
		time(&curr_time);
950
		localtime_r(&curr_time, &t);
951
	}
952
953
	(void)strftime(buf, sizeof(buf), "%a %b %e %H:%M:%S %G", &t);
954
955
	diff_output("%s %s	%s\n", diff_format == D_CONTEXT ? "---" : "+++",
956
	    diff_file2, buf);
957
}
958
959
/*
960
 * Indicate that there is a difference between lines a and b of the from file
961
 * to get to lines c to d of the to file.  If a is greater then b then there
962
 * are no lines in the from file involved and this means that there were
963
 * lines appended (beginning at b).  If c is greater than d then there are
964
 * lines missing from the to file.
965
 */
966
static void
967
change(FILE *f1, FILE *f2, int a, int b, int c, int d, int flags)
968
{
969
	static size_t max_context = 64;
970
	int i;
971
972
	if (diff_format != D_IFDEF && a > b && c > d)
973
		return;
974
	if (ignore_pats != NULL) {
975
		char *line;
976
		/*
977
		 * All lines in the change, insert, or delete must
978
		 * match an ignore pattern for the change to be
979
		 * ignored.
980
		 */
981
		if (a <= b) {		/* Changes and deletes. */
982
			for (i = a; i <= b; i++) {
983
				line = preadline(fileno(f1),
984
				    ixold[i] - ixold[i - 1], ixold[i - 1]);
985
				if (!ignoreline(line))
986
					goto proceed;
987
			}
988
		}
989
		if (a > b || c <= d) {	/* Changes and inserts. */
990
			for (i = c; i <= d; i++) {
991
				line = preadline(fileno(f2),
992
				    ixnew[i] - ixnew[i - 1], ixnew[i - 1]);
993
				if (!ignoreline(line))
994
					goto proceed;
995
			}
996
		}
997
		return;
998
	}
999
proceed:
1000
	if (diff_format == D_CONTEXT || diff_format == D_UNIFIED) {
1001
		/*
1002
		 * Allocate change records as needed.
1003
		 */
1004
		if (context_vec_ptr == context_vec_end - 1) {
1005
			ptrdiff_t offset = context_vec_ptr - context_vec_start;
1006
			max_context <<= 1;
1007
			context_vec_start = xreallocarray(context_vec_start,
1008
			    max_context, sizeof(*context_vec_start));
1009
			context_vec_end = context_vec_start + max_context;
1010
			context_vec_ptr = context_vec_start + offset;
1011
		}
1012
		if (anychange == 0) {
1013
			/*
1014
			 * Print the context/unidiff header first time through.
1015
			 */
1016
			if (cvs_cmdop == CVS_OP_RDIFF)
1017
				rdiff_head();
1018
			else
1019
				diff_head();
1020
1021
			anychange = 1;
1022
		} else if (a > context_vec_ptr->b + (2 * diff_context) + 1 &&
1023
		    c > context_vec_ptr->d + (2 * diff_context) + 1) {
1024
			/*
1025
			 * If this change is more than 'context' lines from the
1026
			 * previous change, dump the record and reset it.
1027
			 */
1028
			if (diff_format == D_CONTEXT)
1029
				dump_context_vec(f1, f2, flags);
1030
			else
1031
				dump_unified_vec(f1, f2, flags);
1032
		}
1033
		context_vec_ptr++;
1034
		context_vec_ptr->a = a;
1035
		context_vec_ptr->b = b;
1036
		context_vec_ptr->c = c;
1037
		context_vec_ptr->d = d;
1038
		return;
1039
	}
1040
	if (anychange == 0)
1041
		anychange = 1;
1042
	switch (diff_format) {
1043
	case D_BRIEF:
1044
		return;
1045
	case D_NORMAL:
1046
		range(a, b, ",");
1047
		diff_output("%c", a > b ? 'a' : c > d ? 'd' : 'c');
1048
		if (diff_format == D_NORMAL)
1049
			range(c, d, ",");
1050
		diff_output("\n");
1051
		break;
1052
	case D_RCSDIFF:
1053
		if (a > b)
1054
			diff_output("a%d %d\n", b, d - c + 1);
1055
		else {
1056
			diff_output("d%d %d\n", a, b - a + 1);
1057
1058
			if (!(c > d))	/* add changed lines */
1059
				diff_output("a%d %d\n", b, d - c + 1);
1060
		}
1061
		break;
1062
	}
1063
	if (diff_format == D_NORMAL || diff_format == D_IFDEF) {
1064
		fetch(ixold, a, b, f1, '<', 1, flags);
1065
		if (a <= b && c <= d && diff_format == D_NORMAL)
1066
			diff_output("---\n");
1067
	}
1068
	fetch(ixnew, c, d, f2, diff_format == D_NORMAL ? '>' : '\0', 0, flags);
1069
	if (inifdef) {
1070
		diff_output("#endif /* %s */\n", ifdefname);
1071
		inifdef = 0;
1072
	}
1073
}
1074
1075
static void
1076
fetch(long *f, int a, int b, FILE *lb, int ch, int oldfile, int flags)
1077
{
1078
	long j, nc;
1079
	int i, c, col;
1080
1081
	/*
1082
	 * When doing #ifdef's, copy down to current line
1083
	 * if this is the first file, so that stuff makes it to output.
1084
	 */
1085
	if (diff_format == D_IFDEF && oldfile) {
1086
		long curpos = ftell(lb);
1087
		/* print through if append (a>b), else to (nb: 0 vs 1 orig) */
1088
		nc = f[a > b ? b : a - 1] - curpos;
1089
		for (i = 0; i < nc; i++)
1090
			diff_output("%c", getc(lb));
1091
	}
1092
	if (a > b)
1093
		return;
1094
	if (diff_format == D_IFDEF) {
1095
		if (inifdef) {
1096
			diff_output("#else /* %s%s */\n",
1097
			    oldfile == 1 ? "!" : "", ifdefname);
1098
		} else {
1099
			if (oldfile)
1100
				diff_output("#ifndef %s\n", ifdefname);
1101
			else
1102
				diff_output("#ifdef %s\n", ifdefname);
1103
		}
1104
		inifdef = 1 + oldfile;
1105
	}
1106
	for (i = a; i <= b; i++) {
1107
		fseek(lb, f[i - 1], SEEK_SET);
1108
		nc = f[i] - f[i - 1];
1109
		if (diff_format != D_IFDEF && ch != '\0') {
1110
			diff_output("%c", ch);
1111
			if (Tflag == 1 && (diff_format == D_NORMAL ||
1112
			    diff_format == D_CONTEXT ||
1113
			    diff_format == D_UNIFIED))
1114
				diff_output("\t");
1115
			else if (diff_format != D_UNIFIED)
1116
				diff_output(" ");
1117
		}
1118
		col = 0;
1119
		for (j = 0; j < nc; j++) {
1120
			if ((c = getc(lb)) == EOF) {
1121
				if (diff_format == D_RCSDIFF)
1122
					cvs_log(LP_ERR,
1123
					    "No newline at end of file");
1124
				else
1125
					diff_output("\n\\ No newline at end of "
1126
					    "file\n");
1127
				return;
1128
			}
1129
			if (c == '\t' && (flags & D_EXPANDTABS)) {
1130
				do {
1131
					diff_output(" ");
1132
				} while (++col & 7);
1133
			} else {
1134
				diff_output("%c", c);
1135
				col++;
1136
			}
1137
		}
1138
	}
1139
}
1140
1141
/*
1142
 * Hash function taken from Robert Sedgewick, Algorithms in C, 3d ed., p 578.
1143
 */
1144
static int
1145
readhash(FILE *f, int flags)
1146
{
1147
	int i, t, space;
1148
	int sum;
1149
1150
	sum = 1;
1151
	space = 0;
1152
	if ((flags & (D_FOLDBLANKS|D_IGNOREBLANKS)) == 0) {
1153
		if (flags & D_IGNORECASE)
1154
			for (i = 0; (t = getc(f)) != '\n'; i++) {
1155
				if (t == EOF) {
1156
					if (i == 0)
1157
						return (0);
1158
					break;
1159
				}
1160
				sum = sum * 127 + chrtran[t];
1161
			}
1162
		else
1163
			for (i = 0; (t = getc(f)) != '\n'; i++) {
1164
				if (t == EOF) {
1165
					if (i == 0)
1166
						return (0);
1167
					break;
1168
				}
1169
				sum = sum * 127 + t;
1170
			}
1171
	} else {
1172
		for (i = 0;;) {
1173
			switch (t = getc(f)) {
1174
			case '\t':
1175
			case '\r':
1176
			case '\v':
1177
			case '\f':
1178
			case ' ':
1179
				space++;
1180
				continue;
1181
			default:
1182
				if (space && (flags & D_IGNOREBLANKS) == 0) {
1183
					i++;
1184
					space = 0;
1185
				}
1186
				sum = sum * 127 + chrtran[t];
1187
				i++;
1188
				continue;
1189
			case EOF:
1190
				if (i == 0)
1191
					return (0);
1192
				/* FALLTHROUGH */
1193
			case '\n':
1194
				break;
1195
			}
1196
			break;
1197
		}
1198
	}
1199
	/*
1200
	 * There is a remote possibility that we end up with a zero sum.
1201
	 * Zero is used as an EOF marker, so return 1 instead.
1202
	 */
1203
	return (sum == 0 ? 1 : sum);
1204
}
1205
1206
static int
1207
asciifile(FILE *f)
1208
{
1209
	unsigned char buf[BUFSIZ];
1210
	size_t i, cnt;
1211
1212
	if (f == NULL)
1213
		return (1);
1214
1215
	rewind(f);
1216
	cnt = fread(buf, 1, sizeof(buf), f);
1217
	for (i = 0; i < cnt; i++)
1218
		if (!isprint(buf[i]) && !isspace(buf[i]))
1219
			return (0);
1220
	return (1);
1221
}
1222
1223
#define begins_with(s, pre) (strncmp(s, pre, sizeof(pre)-1) == 0)
1224
1225
static char *
1226
match_function(const long *f, int pos, FILE *fp)
1227
{
1228
	unsigned char buf[FUNCTION_CONTEXT_SIZE];
1229
	size_t nc;
1230
	int last = lastline;
1231
	char *state = NULL;
1232
1233
	lastline = pos;
1234
	while (pos > last) {
1235
		fseek(fp, f[pos - 1], SEEK_SET);
1236
		nc = f[pos] - f[pos - 1];
1237
		if (nc >= sizeof(buf))
1238
			nc = sizeof(buf) - 1;
1239
		nc = fread(buf, 1, nc, fp);
1240
		if (nc > 0) {
1241
			buf[nc] = '\0';
1242
			buf[strcspn(buf, "\n")] = '\0';
1243
			if (isalpha(buf[0]) || buf[0] == '_' || buf[0] == '$') {
1244
				if (begins_with(buf, "private:")) {
1245
					if (!state)
1246
						state = " (private)";
1247
				} else if (begins_with(buf, "protected:")) {
1248
					if (!state)
1249
						state = " (protected)";
1250
				} else if (begins_with(buf, "public:")) {
1251
					if (!state)
1252
						state = " (public)";
1253
				} else {
1254
					strlcpy(lastbuf, buf, sizeof lastbuf);
1255
					if (state)
1256
						strlcat(lastbuf, state,
1257
						    sizeof lastbuf);
1258
					lastmatchline = pos;
1259
					return lastbuf;
1260
				}
1261
			}
1262
		}
1263
		pos--;
1264
	}
1265
	return lastmatchline > 0 ? lastbuf : NULL;
1266
}
1267
1268
/* dump accumulated "context" diff changes */
1269
static void
1270
dump_context_vec(FILE *f1, FILE *f2, int flags)
1271
{
1272
	struct context_vec *cvp = context_vec_start;
1273
	int lowa, upb, lowc, upd, do_output;
1274
	int a, b, c, d;
1275
	char ch, *f;
1276
1277
	if (context_vec_start > context_vec_ptr)
1278
		return;
1279
1280
	b = d = 0;		/* gcc */
1281
	lowa = MAXIMUM(1, cvp->a - diff_context);
1282
	upb = MINIMUM(len[0], context_vec_ptr->b + diff_context);
1283
	lowc = MAXIMUM(1, cvp->c - diff_context);
1284
	upd = MINIMUM(len[1], context_vec_ptr->d + diff_context);
1285
1286
	diff_output("***************");
1287
	if ((flags & D_PROTOTYPE)) {
1288
		f = match_function(ixold, lowa-1, f1);
1289
		if (f != NULL)
1290
			diff_output(" %s", f);
1291
	}
1292
	diff_output("\n*** ");
1293
	range(lowa, upb, ",");
1294
	diff_output(" ****\n");
1295
1296
	/*
1297
	 * Output changes to the "old" file.  The first loop suppresses
1298
	 * output if there were no changes to the "old" file (we'll see
1299
	 * the "old" lines as context in the "new" list).
1300
	 */
1301
	do_output = 0;
1302
	for (; cvp <= context_vec_ptr; cvp++)
1303
		if (cvp->a <= cvp->b) {
1304
			cvp = context_vec_start;
1305
			do_output++;
1306
			break;
1307
		}
1308
	if (do_output) {
1309
		while (cvp <= context_vec_ptr) {
1310
			a = cvp->a;
1311
			b = cvp->b;
1312
			c = cvp->c;
1313
			d = cvp->d;
1314
1315
			if (a <= b && c <= d)
1316
				ch = 'c';
1317
			else
1318
				ch = (a <= b) ? 'd' : 'a';
1319
1320
			if (ch == 'a')
1321
				fetch(ixold, lowa, b, f1, ' ', 0, flags);
1322
			else {
1323
				fetch(ixold, lowa, a - 1, f1, ' ', 0, flags);
1324
				fetch(ixold, a, b, f1,
1325
				    ch == 'c' ? '!' : '-', 0, flags);
1326
			}
1327
			lowa = b + 1;
1328
			cvp++;
1329
		}
1330
		fetch(ixold, b + 1, upb, f1, ' ', 0, flags);
1331
	}
1332
	/* output changes to the "new" file */
1333
	diff_output("--- ");
1334
	range(lowc, upd, ",");
1335
	diff_output(" ----\n");
1336
1337
	do_output = 0;
1338
	for (cvp = context_vec_start; cvp <= context_vec_ptr; cvp++)
1339
		if (cvp->c <= cvp->d) {
1340
			cvp = context_vec_start;
1341
			do_output++;
1342
			break;
1343
		}
1344
	if (do_output) {
1345
		while (cvp <= context_vec_ptr) {
1346
			a = cvp->a;
1347
			b = cvp->b;
1348
			c = cvp->c;
1349
			d = cvp->d;
1350
1351
			if (a <= b && c <= d)
1352
				ch = 'c';
1353
			else
1354
				ch = (a <= b) ? 'd' : 'a';
1355
1356
			if (ch == 'd')
1357
				fetch(ixnew, lowc, d, f2, ' ', 0, flags);
1358
			else {
1359
				fetch(ixnew, lowc, c - 1, f2, ' ', 0, flags);
1360
				fetch(ixnew, c, d, f2,
1361
				    ch == 'c' ? '!' : '+', 0, flags);
1362
			}
1363
			lowc = d + 1;
1364
			cvp++;
1365
		}
1366
		fetch(ixnew, d + 1, upd, f2, ' ', 0, flags);
1367
	}
1368
	context_vec_ptr = context_vec_start - 1;
1369
}
1370
1371
/* dump accumulated "unified" diff changes */
1372
static void
1373
dump_unified_vec(FILE *f1, FILE *f2, int flags)
1374
{
1375
	struct context_vec *cvp = context_vec_start;
1376
	int lowa, upb, lowc, upd;
1377
	int a, b, c, d;
1378
	char ch, *f;
1379
1380
	if (context_vec_start > context_vec_ptr)
1381
		return;
1382
1383
	b = d = 0;		/* gcc */
1384
	lowa = MAXIMUM(1, cvp->a - diff_context);
1385
	upb = MINIMUM(len[0], context_vec_ptr->b + diff_context);
1386
	lowc = MAXIMUM(1, cvp->c - diff_context);
1387
	upd = MINIMUM(len[1], context_vec_ptr->d + diff_context);
1388
1389
	diff_output("@@ -");
1390
	uni_range(lowa, upb);
1391
	diff_output(" +");
1392
	uni_range(lowc, upd);
1393
	diff_output(" @@");
1394
	if ((flags & D_PROTOTYPE)) {
1395
		f = match_function(ixold, lowa-1, f1);
1396
		if (f != NULL)
1397
			diff_output(" %s", f);
1398
	}
1399
	diff_output("\n");
1400
1401
	/*
1402
	 * Output changes in "unified" diff format--the old and new lines
1403
	 * are printed together.
1404
	 */
1405
	for (; cvp <= context_vec_ptr; cvp++) {
1406
		a = cvp->a;
1407
		b = cvp->b;
1408
		c = cvp->c;
1409
		d = cvp->d;
1410
1411
		/*
1412
		 * c: both new and old changes
1413
		 * d: only changes in the old file
1414
		 * a: only changes in the new file
1415
		 */
1416
		if (a <= b && c <= d)
1417
			ch = 'c';
1418
		else
1419
			ch = (a <= b) ? 'd' : 'a';
1420
1421
		switch (ch) {
1422
		case 'c':
1423
			fetch(ixold, lowa, a - 1, f1, ' ', 0, flags);
1424
			fetch(ixold, a, b, f1, '-', 0, flags);
1425
			fetch(ixnew, c, d, f2, '+', 0, flags);
1426
			break;
1427
		case 'd':
1428
			fetch(ixold, lowa, a - 1, f1, ' ', 0, flags);
1429
			fetch(ixold, a, b, f1, '-', 0, flags);
1430
			break;
1431
		case 'a':
1432
			fetch(ixnew, lowc, c - 1, f2, ' ', 0, flags);
1433
			fetch(ixnew, c, d, f2, '+', 0, flags);
1434
			break;
1435
		}
1436
		lowa = b + 1;
1437
		lowc = d + 1;
1438
	}
1439
	fetch(ixnew, d + 1, upd, f2, ' ', 0, flags);
1440
1441
	context_vec_ptr = context_vec_start - 1;
1442
}
1443
1444
void
1445
diff_output(const char *fmt, ...)
1446
{
1447
	va_list vap;
1448
	int i;
1449
	char *str;
1450
1451
	va_start(vap, fmt);
1452
	i = vasprintf(&str, fmt, vap);
1453
	va_end(vap);
1454
	if (i == -1)
1455
		fatal("diff_output: could not allocate memory");
1456
	if (diffbuf != NULL)
1457
		buf_puts(diffbuf, str);
1458
	else
1459
		cvs_printf("%s", str);
1460
	free(str);
1461
}