1 /* $OpenBSD: diffreg.c,v 1.93 2019/06/28 13:35:00 deraadt Exp $ */
2
3 /*-
4 * SPDX-License-Identifier: BSD-4-Clause
5 *
6 * Copyright (C) Caldera International Inc. 2001-2002.
7 * All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 * 1. Redistributions of source code and documentation must retain the above
13 * copyright notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in the
16 * documentation and/or other materials provided with the distribution.
17 * 3. All advertising materials mentioning features or use of this software
18 * must display the following acknowledgement:
19 * This product includes software developed or owned by Caldera
20 * International, Inc.
21 * 4. Neither the name of Caldera International, Inc. nor the names of other
22 * contributors may be used to endorse or promote products derived from
23 * this software without specific prior written permission.
24 *
25 * USE OF THE SOFTWARE PROVIDED FOR UNDER THIS LICENSE BY CALDERA
26 * INTERNATIONAL, INC. AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR
27 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
28 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
29 * IN NO EVENT SHALL CALDERA INTERNATIONAL, INC. BE LIABLE FOR ANY DIRECT,
30 * INDIRECT INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
31 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
32 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
33 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
34 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
35 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
36 * POSSIBILITY OF SUCH DAMAGE.
37 */
38 /*-
39 * Copyright (c) 1991, 1993
40 * The Regents of the University of California. All rights reserved.
41 *
42 * Redistribution and use in source and binary forms, with or without
43 * modification, are permitted provided that the following conditions
44 * are met:
45 * 1. Redistributions of source code must retain the above copyright
46 * notice, this list of conditions and the following disclaimer.
47 * 2. Redistributions in binary form must reproduce the above copyright
48 * notice, this list of conditions and the following disclaimer in the
49 * documentation and/or other materials provided with the distribution.
50 * 3. Neither the name of the University nor the names of its contributors
51 * may be used to endorse or promote products derived from this software
52 * without specific prior written permission.
53 *
54 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
55 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
56 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
57 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
58 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
59 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
60 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
61 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
62 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
63 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
64 * SUCH DAMAGE.
65 *
66 * @(#)diffreg.c 8.1 (Berkeley) 6/6/93
67 */
68
69 #include <sys/cdefs.h>
70 __FBSDID("$FreeBSD$");
71
72 #include <sys/capsicum.h>
73 #include <sys/stat.h>
74
75 #include <capsicum_helpers.h>
76 #include <ctype.h>
77 #include <err.h>
78 #include <errno.h>
79 #include <fcntl.h>
80 #include <paths.h>
81 #include <regex.h>
82 #include <stdbool.h>
83 #include <stddef.h>
84 #include <stdint.h>
85 #include <stdio.h>
86 #include <stdlib.h>
87 #include <string.h>
88
89 #include "pr.h"
90 #include "diff.h"
91 #include "xmalloc.h"
92
93 /*
94 * diff - compare two files.
95 */
96
97 /*
98 * Uses an algorithm due to Harold Stone, which finds
99 * a pair of longest identical subsequences in the two
100 * files.
101 *
102 * The major goal is to generate the match vector J.
103 * J[i] is the index of the line in file1 corresponding
104 * to line i file0. J[i] = 0 if there is no
105 * such line in file1.
106 *
107 * Lines are hashed so as to work in core. All potential
108 * matches are located by sorting the lines of each file
109 * on the hash (called ``value''). In particular, this
110 * collects the equivalence classes in file1 together.
111 * Subroutine equiv replaces the value of each line in
112 * file0 by the index of the first element of its
113 * matching equivalence in (the reordered) file1.
114 * To save space equiv squeezes file1 into a single
115 * array member in which the equivalence classes
116 * are simply concatenated, except that their first
117 * members are flagged by changing sign.
118 *
119 * Next the indices that point into member are unsorted into
120 * array class according to the original order of file0.
121 *
122 * The cleverness lies in routine stone. This marches
123 * through the lines of file0, developing a vector klist
124 * of "k-candidates". At step i a k-candidate is a matched
125 * pair of lines x,y (x in file0 y in file1) such that
126 * there is a common subsequence of length k
127 * between the first i lines of file0 and the first y
128 * lines of file1, but there is no such subsequence for
129 * any smaller y. x is the earliest possible mate to y
130 * that occurs in such a subsequence.
131 *
132 * Whenever any of the members of the equivalence class of
133 * lines in file1 matable to a line in file0 has serial number
134 * less than the y of some k-candidate, that k-candidate
135 * with the smallest such y is replaced. The new
136 * k-candidate is chained (via pred) to the current
137 * k-1 candidate so that the actual subsequence can
138 * be recovered. When a member has serial number greater
139 * that the y of all k-candidates, the klist is extended.
140 * At the end, the longest subsequence is pulled out
141 * and placed in the array J by unravel
142 *
143 * With J in hand, the matches there recorded are
144 * check'ed against reality to assure that no spurious
145 * matches have crept in due to hashing. If they have,
146 * they are broken, and "jackpot" is recorded--a harmless
147 * matter except that a true match for a spuriously
148 * mated line may now be unnecessarily reported as a change.
149 *
150 * Much of the complexity of the program comes simply
151 * from trying to minimize core utilization and
152 * maximize the range of doable problems by dynamically
153 * allocating what is needed and reusing what is not.
154 * The core requirements for problems larger than somewhat
155 * are (in words) 2*length(file0) + length(file1) +
156 * 3*(number of k-candidates installed), typically about
157 * 6n words for files of length n.
158 */
159
160 struct cand {
161 int x;
162 int y;
163 int pred;
164 };
165
166 static struct line {
167 int serial;
168 int value;
169 } *file[2];
170
171 /*
172 * The following struct is used to record change information when
173 * doing a "context" or "unified" diff. (see routine "change" to
174 * understand the highly mnemonic field names)
175 */
176 struct context_vec {
177 int a; /* start line in old file */
178 int b; /* end line in old file */
179 int c; /* start line in new file */
180 int d; /* end line in new file */
181 };
182
183 enum readhash { RH_BINARY, RH_OK, RH_EOF };
184
185 #define MIN_PAD 1
186 static FILE *opentemp(const char *);
187 static void output(char *, FILE *, char *, FILE *, int);
188 static void check(FILE *, FILE *, int);
189 static void range(int, int, const char *);
190 static void uni_range(int, int);
191 static void dump_context_vec(FILE *, FILE *, int);
192 static void dump_unified_vec(FILE *, FILE *, int);
193 static bool prepare(int, FILE *, size_t, int);
194 static void prune(void);
195 static void equiv(struct line *, int, struct line *, int, int *);
196 static void unravel(int);
197 static void unsort(struct line *, int, int *);
198 static void change(char *, FILE *, char *, FILE *, int, int, int, int, int *);
199 static void sort(struct line *, int);
200 static void print_header(const char *, const char *);
201 static void print_space(int, int, int);
202 static bool ignoreline_pattern(char *);
203 static bool ignoreline(char *, bool);
204 static int asciifile(FILE *);
205 static int fetch(long *, int, int, FILE *, int, int, int);
206 static int newcand(int, int, int);
207 static int search(int *, int, int);
208 static int skipline(FILE *);
209 static int isqrt(int);
210 static int stone(int *, int, int *, int *, int);
211 static enum readhash readhash(FILE *, int, unsigned *);
212 static int files_differ(FILE *, FILE *, int);
213 static char *match_function(const long *, int, FILE *);
214 static char *preadline(int, size_t, off_t);
215
216 static int *J; /* will be overlaid on class */
217 static int *class; /* will be overlaid on file[0] */
218 static int *klist; /* will be overlaid on file[0] after class */
219 static int *member; /* will be overlaid on file[1] */
220 static int clen;
221 static int inifdef; /* whether or not we are in a #ifdef block */
222 static int len[2];
223 static int pref, suff; /* length of prefix and suffix */
224 static int slen[2];
225 static int anychange;
226 static int hw, padding; /* half width and padding */
227 static int edoffset;
228 static long *ixnew; /* will be overlaid on file[1] */
229 static long *ixold; /* will be overlaid on klist */
230 static struct cand *clist; /* merely a free storage pot for candidates */
231 static int clistlen; /* the length of clist */
232 static struct line *sfile[2]; /* shortened by pruning common prefix/suffix */
233 static int (*chrtran)(int); /* translation table for case-folding */
234 static struct context_vec *context_vec_start;
235 static struct context_vec *context_vec_end;
236 static struct context_vec *context_vec_ptr;
237
238 #define FUNCTION_CONTEXT_SIZE 55
239 static char lastbuf[FUNCTION_CONTEXT_SIZE];
240 static int lastline;
241 static int lastmatchline;
242
243 static int
clow2low(int c)244 clow2low(int c)
245 {
246
247 return (c);
248 }
249
250 static int
cup2low(int c)251 cup2low(int c)
252 {
253
254 return tolower(c);
255 }
256
257 int
diffreg(char * file1,char * file2,int flags,int capsicum)258 diffreg(char *file1, char *file2, int flags, int capsicum)
259 {
260 FILE *f1, *f2;
261 int i, rval;
262 struct pr *pr = NULL;
263 cap_rights_t rights_ro;
264
265 f1 = f2 = NULL;
266 rval = D_SAME;
267 anychange = 0;
268 lastline = 0;
269 lastmatchline = 0;
270 context_vec_ptr = context_vec_start - 1;
271
272 /*
273 * hw excludes padding and make sure when -t is not used,
274 * the second column always starts from the closest tab stop
275 */
276 if (diff_format == D_SIDEBYSIDE) {
277 hw = width >> 1;
278 padding = tabsize - (hw % tabsize);
279 if ((flags & D_EXPANDTABS) != 0 || (padding % tabsize == 0))
280 padding = MIN_PAD;
281
282 hw = (width >> 1) -
283 ((padding == MIN_PAD) ? (padding << 1) : padding) - 1;
284 }
285
286
287 if (flags & D_IGNORECASE)
288 chrtran = cup2low;
289 else
290 chrtran = clow2low;
291 if (S_ISDIR(stb1.st_mode) != S_ISDIR(stb2.st_mode))
292 return (S_ISDIR(stb1.st_mode) ? D_MISMATCH1 : D_MISMATCH2);
293 if (strcmp(file1, "-") == 0 && strcmp(file2, "-") == 0)
294 goto closem;
295
296 if (flags & D_EMPTY1)
297 f1 = fopen(_PATH_DEVNULL, "r");
298 else {
299 if (!S_ISREG(stb1.st_mode)) {
300 if ((f1 = opentemp(file1)) == NULL ||
301 fstat(fileno(f1), &stb1) == -1) {
302 warn("%s", file1);
303 rval = D_ERROR;
304 status |= 2;
305 goto closem;
306 }
307 } else if (strcmp(file1, "-") == 0)
308 f1 = stdin;
309 else
310 f1 = fopen(file1, "r");
311 }
312 if (f1 == NULL) {
313 warn("%s", file1);
314 rval = D_ERROR;
315 status |= 2;
316 goto closem;
317 }
318
319 if (flags & D_EMPTY2)
320 f2 = fopen(_PATH_DEVNULL, "r");
321 else {
322 if (!S_ISREG(stb2.st_mode)) {
323 if ((f2 = opentemp(file2)) == NULL ||
324 fstat(fileno(f2), &stb2) == -1) {
325 warn("%s", file2);
326 rval = D_ERROR;
327 status |= 2;
328 goto closem;
329 }
330 } else if (strcmp(file2, "-") == 0)
331 f2 = stdin;
332 else
333 f2 = fopen(file2, "r");
334 }
335 if (f2 == NULL) {
336 warn("%s", file2);
337 rval = D_ERROR;
338 status |= 2;
339 goto closem;
340 }
341
342 if (lflag)
343 pr = start_pr(file1, file2);
344
345 if (capsicum) {
346 cap_rights_init(&rights_ro, CAP_READ, CAP_FSTAT, CAP_SEEK);
347 if (caph_rights_limit(fileno(f1), &rights_ro) < 0)
348 err(2, "unable to limit rights on: %s", file1);
349 if (caph_rights_limit(fileno(f2), &rights_ro) < 0)
350 err(2, "unable to limit rights on: %s", file2);
351 if (fileno(f1) == STDIN_FILENO || fileno(f2) == STDIN_FILENO) {
352 /* stdin has already been limited */
353 if (caph_limit_stderr() == -1)
354 err(2, "unable to limit stderr");
355 if (caph_limit_stdout() == -1)
356 err(2, "unable to limit stdout");
357 } else if (caph_limit_stdio() == -1)
358 err(2, "unable to limit stdio");
359
360 caph_cache_catpages();
361 caph_cache_tzdata();
362 if (caph_enter() < 0)
363 err(2, "unable to enter capability mode");
364 }
365
366 switch (files_differ(f1, f2, flags)) {
367 case 0:
368 goto closem;
369 case 1:
370 break;
371 default:
372 /* error */
373 rval = D_ERROR;
374 status |= 2;
375 goto closem;
376 }
377
378 if (diff_format == D_BRIEF && ignore_pats == NULL &&
379 (flags & (D_FOLDBLANKS|D_IGNOREBLANKS|D_IGNORECASE|D_STRIPCR)) == 0)
380 {
381 rval = D_DIFFER;
382 status |= 1;
383 goto closem;
384 }
385 if ((flags & D_FORCEASCII) != 0) {
386 (void)prepare(0, f1, stb1.st_size, flags);
387 (void)prepare(1, f2, stb2.st_size, flags);
388 } else if (!asciifile(f1) || !asciifile(f2) ||
389 !prepare(0, f1, stb1.st_size, flags) ||
390 !prepare(1, f2, stb2.st_size, flags)) {
391 rval = D_BINARY;
392 status |= 1;
393 goto closem;
394 }
395
396 prune();
397 sort(sfile[0], slen[0]);
398 sort(sfile[1], slen[1]);
399
400 member = (int *)file[1];
401 equiv(sfile[0], slen[0], sfile[1], slen[1], member);
402 member = xreallocarray(member, slen[1] + 2, sizeof(*member));
403
404 class = (int *)file[0];
405 unsort(sfile[0], slen[0], class);
406 class = xreallocarray(class, slen[0] + 2, sizeof(*class));
407
408 klist = xcalloc(slen[0] + 2, sizeof(*klist));
409 clen = 0;
410 clistlen = 100;
411 clist = xcalloc(clistlen, sizeof(*clist));
412 i = stone(class, slen[0], member, klist, flags);
413 free(member);
414 free(class);
415
416 J = xreallocarray(J, len[0] + 2, sizeof(*J));
417 unravel(klist[i]);
418 free(clist);
419 free(klist);
420
421 ixold = xreallocarray(ixold, len[0] + 2, sizeof(*ixold));
422 ixnew = xreallocarray(ixnew, len[1] + 2, sizeof(*ixnew));
423 check(f1, f2, flags);
424 output(file1, f1, file2, f2, flags);
425
426 closem:
427 if (pr != NULL)
428 stop_pr(pr);
429 if (anychange) {
430 status |= 1;
431 if (rval == D_SAME)
432 rval = D_DIFFER;
433 }
434 if (f1 != NULL)
435 fclose(f1);
436 if (f2 != NULL)
437 fclose(f2);
438
439 return (rval);
440 }
441
442 /*
443 * Check to see if the given files differ.
444 * Returns 0 if they are the same, 1 if different, and -1 on error.
445 * XXX - could use code from cmp(1) [faster]
446 */
447 static int
files_differ(FILE * f1,FILE * f2,int flags)448 files_differ(FILE *f1, FILE *f2, int flags)
449 {
450 char buf1[BUFSIZ], buf2[BUFSIZ];
451 size_t i, j;
452
453 if ((flags & (D_EMPTY1|D_EMPTY2)) || stb1.st_size != stb2.st_size ||
454 (stb1.st_mode & S_IFMT) != (stb2.st_mode & S_IFMT))
455 return (1);
456 for (;;) {
457 i = fread(buf1, 1, sizeof(buf1), f1);
458 j = fread(buf2, 1, sizeof(buf2), f2);
459 if ((!i && ferror(f1)) || (!j && ferror(f2)))
460 return (-1);
461 if (i != j)
462 return (1);
463 if (i == 0)
464 return (0);
465 if (memcmp(buf1, buf2, i) != 0)
466 return (1);
467 }
468 }
469
470 static FILE *
opentemp(const char * f)471 opentemp(const char *f)
472 {
473 char buf[BUFSIZ], tempfile[PATH_MAX];
474 ssize_t nread;
475 int ifd, ofd;
476
477 if (strcmp(f, "-") == 0)
478 ifd = STDIN_FILENO;
479 else if ((ifd = open(f, O_RDONLY, 0644)) == -1)
480 return (NULL);
481
482 (void)strlcpy(tempfile, _PATH_TMP "/diff.XXXXXXXX", sizeof(tempfile));
483
484 if ((ofd = mkstemp(tempfile)) == -1) {
485 close(ifd);
486 return (NULL);
487 }
488 unlink(tempfile);
489 while ((nread = read(ifd, buf, BUFSIZ)) > 0) {
490 if (write(ofd, buf, nread) != nread) {
491 close(ifd);
492 close(ofd);
493 return (NULL);
494 }
495 }
496 close(ifd);
497 lseek(ofd, (off_t)0, SEEK_SET);
498 return (fdopen(ofd, "r"));
499 }
500
501 char *
splice(char * dir,char * path)502 splice(char *dir, char *path)
503 {
504 char *tail, *buf;
505 size_t dirlen;
506
507 dirlen = strlen(dir);
508 while (dirlen != 0 && dir[dirlen - 1] == '/')
509 dirlen--;
510 if ((tail = strrchr(path, '/')) == NULL)
511 tail = path;
512 else
513 tail++;
514 xasprintf(&buf, "%.*s/%s", (int)dirlen, dir, tail);
515 return (buf);
516 }
517
518 static bool
prepare(int i,FILE * fd,size_t filesize,int flags)519 prepare(int i, FILE *fd, size_t filesize, int flags)
520 {
521 struct line *p;
522 unsigned h;
523 size_t sz, j = 0;
524 enum readhash r;
525
526 rewind(fd);
527
528 sz = MIN(filesize, SIZE_MAX) / 25;
529 if (sz < 100)
530 sz = 100;
531
532 p = xcalloc(sz + 3, sizeof(*p));
533 while ((r = readhash(fd, flags, &h)) != RH_EOF)
534 switch (r) {
535 case RH_EOF: /* otherwise clang complains */
536 case RH_BINARY:
537 return (false);
538 case RH_OK:
539 if (j == sz) {
540 sz = sz * 3 / 2;
541 p = xreallocarray(p, sz + 3, sizeof(*p));
542 }
543 p[++j].value = h;
544 }
545
546 len[i] = j;
547 file[i] = p;
548
549 return (true);
550 }
551
552 static void
prune(void)553 prune(void)
554 {
555 int i, j;
556
557 for (pref = 0; pref < len[0] && pref < len[1] &&
558 file[0][pref + 1].value == file[1][pref + 1].value;
559 pref++)
560 ;
561 for (suff = 0; suff < len[0] - pref && suff < len[1] - pref &&
562 file[0][len[0] - suff].value == file[1][len[1] - suff].value;
563 suff++)
564 ;
565 for (j = 0; j < 2; j++) {
566 sfile[j] = file[j] + pref;
567 slen[j] = len[j] - pref - suff;
568 for (i = 0; i <= slen[j]; i++)
569 sfile[j][i].serial = i;
570 }
571 }
572
573 static void
equiv(struct line * a,int n,struct line * b,int m,int * c)574 equiv(struct line *a, int n, struct line *b, int m, int *c)
575 {
576 int i, j;
577
578 i = j = 1;
579 while (i <= n && j <= m) {
580 if (a[i].value < b[j].value)
581 a[i++].value = 0;
582 else if (a[i].value == b[j].value)
583 a[i++].value = j;
584 else
585 j++;
586 }
587 while (i <= n)
588 a[i++].value = 0;
589 b[m + 1].value = 0;
590 j = 0;
591 while (++j <= m) {
592 c[j] = -b[j].serial;
593 while (b[j + 1].value == b[j].value) {
594 j++;
595 c[j] = b[j].serial;
596 }
597 }
598 c[j] = -1;
599 }
600
601 /* Code taken from ping.c */
602 static int
isqrt(int n)603 isqrt(int n)
604 {
605 int y, x = 1;
606
607 if (n == 0)
608 return (0);
609
610 do { /* newton was a stinker */
611 y = x;
612 x = n / x;
613 x += y;
614 x /= 2;
615 } while ((x - y) > 1 || (x - y) < -1);
616
617 return (x);
618 }
619
620 static int
stone(int * a,int n,int * b,int * c,int flags)621 stone(int *a, int n, int *b, int *c, int flags)
622 {
623 int i, k, y, j, l;
624 int oldc, tc, oldl, sq;
625 u_int numtries, bound;
626
627 if (flags & D_MINIMAL)
628 bound = UINT_MAX;
629 else {
630 sq = isqrt(n);
631 bound = MAX(256, sq);
632 }
633
634 k = 0;
635 c[0] = newcand(0, 0, 0);
636 for (i = 1; i <= n; i++) {
637 j = a[i];
638 if (j == 0)
639 continue;
640 y = -b[j];
641 oldl = 0;
642 oldc = c[0];
643 numtries = 0;
644 do {
645 if (y <= clist[oldc].y)
646 continue;
647 l = search(c, k, y);
648 if (l != oldl + 1)
649 oldc = c[l - 1];
650 if (l <= k) {
651 if (clist[c[l]].y <= y)
652 continue;
653 tc = c[l];
654 c[l] = newcand(i, y, oldc);
655 oldc = tc;
656 oldl = l;
657 numtries++;
658 } else {
659 c[l] = newcand(i, y, oldc);
660 k++;
661 break;
662 }
663 } while ((y = b[++j]) > 0 && numtries < bound);
664 }
665 return (k);
666 }
667
668 static int
newcand(int x,int y,int pred)669 newcand(int x, int y, int pred)
670 {
671 struct cand *q;
672
673 if (clen == clistlen) {
674 clistlen = clistlen * 11 / 10;
675 clist = xreallocarray(clist, clistlen, sizeof(*clist));
676 }
677 q = clist + clen;
678 q->x = x;
679 q->y = y;
680 q->pred = pred;
681 return (clen++);
682 }
683
684 static int
search(int * c,int k,int y)685 search(int *c, int k, int y)
686 {
687 int i, j, l, t;
688
689 if (clist[c[k]].y < y) /* quick look for typical case */
690 return (k + 1);
691 i = 0;
692 j = k + 1;
693 for (;;) {
694 l = (i + j) / 2;
695 if (l <= i)
696 break;
697 t = clist[c[l]].y;
698 if (t > y)
699 j = l;
700 else if (t < y)
701 i = l;
702 else
703 return (l);
704 }
705 return (l + 1);
706 }
707
708 static void
unravel(int p)709 unravel(int p)
710 {
711 struct cand *q;
712 int i;
713
714 for (i = 0; i <= len[0]; i++)
715 J[i] = i <= pref ? i :
716 i > len[0] - suff ? i + len[1] - len[0] : 0;
717 for (q = clist + p; q->y != 0; q = clist + q->pred)
718 J[q->x + pref] = q->y + pref;
719 }
720
721 /*
722 * Check does double duty:
723 * 1. ferret out any fortuitous correspondences due
724 * to confounding by hashing (which result in "jackpot")
725 * 2. collect random access indexes to the two files
726 */
727 static void
check(FILE * f1,FILE * f2,int flags)728 check(FILE *f1, FILE *f2, int flags)
729 {
730 int i, j, jackpot, c, d;
731 long ctold, ctnew;
732
733 rewind(f1);
734 rewind(f2);
735 j = 1;
736 ixold[0] = ixnew[0] = 0;
737 jackpot = 0;
738 ctold = ctnew = 0;
739 for (i = 1; i <= len[0]; i++) {
740 if (J[i] == 0) {
741 ixold[i] = ctold += skipline(f1);
742 continue;
743 }
744 while (j < J[i]) {
745 ixnew[j] = ctnew += skipline(f2);
746 j++;
747 }
748 if (flags & (D_FOLDBLANKS|D_IGNOREBLANKS|D_IGNORECASE|D_STRIPCR)) {
749 for (;;) {
750 c = getc(f1);
751 d = getc(f2);
752 /*
753 * GNU diff ignores a missing newline
754 * in one file for -b or -w.
755 */
756 if (flags & (D_FOLDBLANKS|D_IGNOREBLANKS)) {
757 if (c == EOF && d == '\n') {
758 ctnew++;
759 break;
760 } else if (c == '\n' && d == EOF) {
761 ctold++;
762 break;
763 }
764 }
765 ctold++;
766 ctnew++;
767 if (flags & D_STRIPCR && (c == '\r' || d == '\r')) {
768 if (c == '\r') {
769 if ((c = getc(f1)) == '\n') {
770 ctold++;
771 } else {
772 ungetc(c, f1);
773 }
774 }
775 if (d == '\r') {
776 if ((d = getc(f2)) == '\n') {
777 ctnew++;
778 } else {
779 ungetc(d, f2);
780 }
781 }
782 break;
783 }
784 if ((flags & D_FOLDBLANKS) && isspace(c) &&
785 isspace(d)) {
786 do {
787 if (c == '\n')
788 break;
789 ctold++;
790 } while (isspace(c = getc(f1)));
791 do {
792 if (d == '\n')
793 break;
794 ctnew++;
795 } while (isspace(d = getc(f2)));
796 } else if ((flags & D_IGNOREBLANKS)) {
797 while (isspace(c) && c != '\n') {
798 c = getc(f1);
799 ctold++;
800 }
801 while (isspace(d) && d != '\n') {
802 d = getc(f2);
803 ctnew++;
804 }
805 }
806 if (chrtran(c) != chrtran(d)) {
807 jackpot++;
808 J[i] = 0;
809 if (c != '\n' && c != EOF)
810 ctold += skipline(f1);
811 if (d != '\n' && c != EOF)
812 ctnew += skipline(f2);
813 break;
814 }
815 if (c == '\n' || c == EOF)
816 break;
817 }
818 } else {
819 for (;;) {
820 ctold++;
821 ctnew++;
822 if ((c = getc(f1)) != (d = getc(f2))) {
823 /* jackpot++; */
824 J[i] = 0;
825 if (c != '\n' && c != EOF)
826 ctold += skipline(f1);
827 if (d != '\n' && c != EOF)
828 ctnew += skipline(f2);
829 break;
830 }
831 if (c == '\n' || c == EOF)
832 break;
833 }
834 }
835 ixold[i] = ctold;
836 ixnew[j] = ctnew;
837 j++;
838 }
839 for (; j <= len[1]; j++) {
840 ixnew[j] = ctnew += skipline(f2);
841 }
842 /*
843 * if (jackpot)
844 * fprintf(stderr, "jackpot\n");
845 */
846 }
847
848 /* shellsort CACM #201 */
849 static void
sort(struct line * a,int n)850 sort(struct line *a, int n)
851 {
852 struct line *ai, *aim, w;
853 int j, m = 0, k;
854
855 if (n == 0)
856 return;
857 for (j = 1; j <= n; j *= 2)
858 m = 2 * j - 1;
859 for (m /= 2; m != 0; m /= 2) {
860 k = n - m;
861 for (j = 1; j <= k; j++) {
862 for (ai = &a[j]; ai > a; ai -= m) {
863 aim = &ai[m];
864 if (aim < ai)
865 break; /* wraparound */
866 if (aim->value > ai[0].value ||
867 (aim->value == ai[0].value &&
868 aim->serial > ai[0].serial))
869 break;
870 w.value = ai[0].value;
871 ai[0].value = aim->value;
872 aim->value = w.value;
873 w.serial = ai[0].serial;
874 ai[0].serial = aim->serial;
875 aim->serial = w.serial;
876 }
877 }
878 }
879 }
880
881 static void
unsort(struct line * f,int l,int * b)882 unsort(struct line *f, int l, int *b)
883 {
884 int *a, i;
885
886 a = xcalloc(l + 1, sizeof(*a));
887 for (i = 1; i <= l; i++)
888 a[f[i].serial] = f[i].value;
889 for (i = 1; i <= l; i++)
890 b[i] = a[i];
891 free(a);
892 }
893
894 static int
skipline(FILE * f)895 skipline(FILE *f)
896 {
897 int i, c;
898
899 for (i = 1; (c = getc(f)) != '\n' && c != EOF; i++)
900 continue;
901 return (i);
902 }
903
904 static void
output(char * file1,FILE * f1,char * file2,FILE * f2,int flags)905 output(char *file1, FILE *f1, char *file2, FILE *f2, int flags)
906 {
907 int i, j, m, i0, i1, j0, j1, nc;
908
909 rewind(f1);
910 rewind(f2);
911 m = len[0];
912 J[0] = 0;
913 J[m + 1] = len[1] + 1;
914 if (diff_format != D_EDIT) {
915 for (i0 = 1; i0 <= m; i0 = i1 + 1) {
916 while (i0 <= m && J[i0] == J[i0 - 1] + 1){
917 if (diff_format == D_SIDEBYSIDE &&
918 suppress_common != 1) {
919 nc = fetch(ixold, i0, i0, f1, '\0',
920 1, flags);
921 print_space(nc,
922 (hw - nc) + (padding << 1) + 1,
923 flags);
924 fetch(ixnew, J[i0], J[i0], f2, '\0',
925 0, flags);
926 printf("\n");
927 }
928 i0++;
929 }
930 j0 = J[i0 - 1] + 1;
931 i1 = i0 - 1;
932 while (i1 < m && J[i1 + 1] == 0)
933 i1++;
934 j1 = J[i1 + 1] - 1;
935 J[i1] = j1;
936
937 /*
938 * When using side-by-side, lines from both of the
939 * files are printed. The algorithm used by diff(1)
940 * identifies the ranges in which two files differ.
941 * See the change() function below.
942 * The for loop below consumes the shorter range,
943 * whereas one of the while loops deals with the
944 * longer one.
945 */
946 if (diff_format == D_SIDEBYSIDE) {
947 for (i=i0, j=j0; i<=i1 && j<=j1; i++, j++)
948 change(file1, f1, file2, f2, i, i,
949 j, j, &flags);
950
951 while (i <= i1) {
952 change(file1, f1, file2, f2,
953 i, i, j+1, j, &flags);
954 i++;
955 }
956
957 while (j <= j1) {
958 change(file1, f1, file2, f2,
959 i+1, i, j, j, &flags);
960 j++;
961 }
962 } else
963 change(file1, f1, file2, f2, i0, i1, j0,
964 j1, &flags);
965 }
966 } else {
967 for (i0 = m; i0 >= 1; i0 = i1 - 1) {
968 while (i0 >= 1 && J[i0] == J[i0 + 1] - 1 && J[i0] != 0)
969 i0--;
970 j0 = J[i0 + 1] - 1;
971 i1 = i0 + 1;
972 while (i1 > 1 && J[i1 - 1] == 0)
973 i1--;
974 j1 = J[i1 - 1] + 1;
975 J[i1] = j1;
976 change(file1, f1, file2, f2, i1, i0, j1, j0, &flags);
977 }
978 }
979 if (m == 0)
980 change(file1, f1, file2, f2, 1, 0, 1, len[1], &flags);
981 if (diff_format == D_IFDEF || diff_format == D_GFORMAT) {
982 for (;;) {
983 #define c i0
984 if ((c = getc(f1)) == EOF)
985 return;
986 printf("%c", c);
987 }
988 #undef c
989 }
990 if (anychange != 0) {
991 if (diff_format == D_CONTEXT)
992 dump_context_vec(f1, f2, flags);
993 else if (diff_format == D_UNIFIED)
994 dump_unified_vec(f1, f2, flags);
995 }
996 }
997
998 static void
range(int a,int b,const char * separator)999 range(int a, int b, const char *separator)
1000 {
1001 printf("%d", a > b ? b : a);
1002 if (a < b)
1003 printf("%s%d", separator, b);
1004 }
1005
1006 static void
uni_range(int a,int b)1007 uni_range(int a, int b)
1008 {
1009 if (a < b)
1010 printf("%d,%d", a, b - a + 1);
1011 else if (a == b)
1012 printf("%d", b);
1013 else
1014 printf("%d,0", b);
1015 }
1016
1017 static char *
preadline(int fd,size_t rlen,off_t off)1018 preadline(int fd, size_t rlen, off_t off)
1019 {
1020 char *line;
1021 ssize_t nr;
1022
1023 line = xmalloc(rlen + 1);
1024 if ((nr = pread(fd, line, rlen, off)) == -1)
1025 err(2, "preadline");
1026 if (nr > 0 && line[nr-1] == '\n')
1027 nr--;
1028 line[nr] = '\0';
1029 return (line);
1030 }
1031
1032 static bool
ignoreline_pattern(char * line)1033 ignoreline_pattern(char *line)
1034 {
1035 int ret;
1036
1037 ret = regexec(&ignore_re, line, 0, NULL, 0);
1038 free(line);
1039 return (ret == 0); /* if it matched, it should be ignored. */
1040 }
1041
1042 static bool
ignoreline(char * line,bool skip_blanks)1043 ignoreline(char *line, bool skip_blanks)
1044 {
1045
1046 if (ignore_pats != NULL && skip_blanks)
1047 return (ignoreline_pattern(line) || *line == '\0');
1048 if (ignore_pats != NULL)
1049 return (ignoreline_pattern(line));
1050 if (skip_blanks)
1051 return (*line == '\0');
1052 /* No ignore criteria specified */
1053 return (false);
1054 }
1055
1056 /*
1057 * Indicate that there is a difference between lines a and b of the from file
1058 * to get to lines c to d of the to file. If a is greater then b then there
1059 * are no lines in the from file involved and this means that there were
1060 * lines appended (beginning at b). If c is greater than d then there are
1061 * lines missing from the to file.
1062 */
1063 static void
change(char * file1,FILE * f1,char * file2,FILE * f2,int a,int b,int c,int d,int * pflags)1064 change(char *file1, FILE *f1, char *file2, FILE *f2, int a, int b, int c, int d,
1065 int *pflags)
1066 {
1067 static size_t max_context = 64;
1068 long curpos;
1069 int i, nc;
1070 const char *walk;
1071 bool skip_blanks;
1072
1073 skip_blanks = (*pflags & D_SKIPBLANKLINES);
1074 restart:
1075 if ((diff_format != D_IFDEF || diff_format == D_GFORMAT) &&
1076 a > b && c > d)
1077 return;
1078 if (ignore_pats != NULL || skip_blanks) {
1079 char *line;
1080 /*
1081 * All lines in the change, insert, or delete must
1082 * match an ignore pattern for the change to be
1083 * ignored.
1084 */
1085 if (a <= b) { /* Changes and deletes. */
1086 for (i = a; i <= b; i++) {
1087 line = preadline(fileno(f1),
1088 ixold[i] - ixold[i - 1], ixold[i - 1]);
1089 if (!ignoreline(line, skip_blanks))
1090 goto proceed;
1091 }
1092 }
1093 if (a > b || c <= d) { /* Changes and inserts. */
1094 for (i = c; i <= d; i++) {
1095 line = preadline(fileno(f2),
1096 ixnew[i] - ixnew[i - 1], ixnew[i - 1]);
1097 if (!ignoreline(line, skip_blanks))
1098 goto proceed;
1099 }
1100 }
1101 return;
1102 }
1103 proceed:
1104 if (*pflags & D_HEADER && diff_format != D_BRIEF) {
1105 printf("%s %s %s\n", diffargs, file1, file2);
1106 *pflags &= ~D_HEADER;
1107 }
1108 if (diff_format == D_CONTEXT || diff_format == D_UNIFIED) {
1109 /*
1110 * Allocate change records as needed.
1111 */
1112 if (context_vec_ptr == context_vec_end - 1) {
1113 ptrdiff_t offset = context_vec_ptr - context_vec_start;
1114 max_context <<= 1;
1115 context_vec_start = xreallocarray(context_vec_start,
1116 max_context, sizeof(*context_vec_start));
1117 context_vec_end = context_vec_start + max_context;
1118 context_vec_ptr = context_vec_start + offset;
1119 }
1120 if (anychange == 0) {
1121 /*
1122 * Print the context/unidiff header first time through.
1123 */
1124 print_header(file1, file2);
1125 anychange = 1;
1126 } else if (a > context_vec_ptr->b + (2 * diff_context) + 1 &&
1127 c > context_vec_ptr->d + (2 * diff_context) + 1) {
1128 /*
1129 * If this change is more than 'diff_context' lines from the
1130 * previous change, dump the record and reset it.
1131 */
1132 if (diff_format == D_CONTEXT)
1133 dump_context_vec(f1, f2, *pflags);
1134 else
1135 dump_unified_vec(f1, f2, *pflags);
1136 }
1137 context_vec_ptr++;
1138 context_vec_ptr->a = a;
1139 context_vec_ptr->b = b;
1140 context_vec_ptr->c = c;
1141 context_vec_ptr->d = d;
1142 return;
1143 }
1144 if (anychange == 0)
1145 anychange = 1;
1146 switch (diff_format) {
1147 case D_BRIEF:
1148 return;
1149 case D_NORMAL:
1150 case D_EDIT:
1151 range(a, b, ",");
1152 printf("%c", a > b ? 'a' : c > d ? 'd' : 'c');
1153 if (diff_format == D_NORMAL)
1154 range(c, d, ",");
1155 printf("\n");
1156 break;
1157 case D_REVERSE:
1158 printf("%c", a > b ? 'a' : c > d ? 'd' : 'c');
1159 range(a, b, " ");
1160 printf("\n");
1161 break;
1162 case D_NREVERSE:
1163 if (a > b)
1164 printf("a%d %d\n", b, d - c + 1);
1165 else {
1166 printf("d%d %d\n", a, b - a + 1);
1167 if (!(c > d))
1168 /* add changed lines */
1169 printf("a%d %d\n", b, d - c + 1);
1170 }
1171 break;
1172 }
1173 if (diff_format == D_GFORMAT) {
1174 curpos = ftell(f1);
1175 /* print through if append (a>b), else to (nb: 0 vs 1 orig) */
1176 nc = ixold[a > b ? b : a - 1] - curpos;
1177 for (i = 0; i < nc; i++)
1178 printf("%c", getc(f1));
1179 for (walk = group_format; *walk != '\0'; walk++) {
1180 if (*walk == '%') {
1181 walk++;
1182 switch (*walk) {
1183 case '<':
1184 fetch(ixold, a, b, f1, '<', 1, *pflags);
1185 break;
1186 case '>':
1187 fetch(ixnew, c, d, f2, '>', 0, *pflags);
1188 break;
1189 default:
1190 printf("%%%c", *walk);
1191 break;
1192 }
1193 continue;
1194 }
1195 printf("%c", *walk);
1196 }
1197 }
1198 if (diff_format == D_SIDEBYSIDE) {
1199 if (a > b) {
1200 print_space(0, hw + padding , *pflags);
1201 } else {
1202 nc = fetch(ixold, a, b, f1, '\0', 1, *pflags);
1203 print_space(nc, hw - nc + padding, *pflags);
1204 }
1205 printf("%c", (a>b)? '>' : ((c>d)? '<' : '|'));
1206 print_space(hw + padding + 1 , padding, *pflags);
1207 fetch(ixnew, c, d, f2, '\0', 0, *pflags);
1208 printf("\n");
1209 }
1210 if (diff_format == D_NORMAL || diff_format == D_IFDEF) {
1211 fetch(ixold, a, b, f1, '<', 1, *pflags);
1212 if (a <= b && c <= d && diff_format == D_NORMAL)
1213 printf("---\n");
1214 }
1215 if (diff_format != D_GFORMAT && diff_format != D_SIDEBYSIDE)
1216 fetch(ixnew, c, d, f2, diff_format == D_NORMAL ? '>' : '\0', 0, *pflags);
1217 if (edoffset != 0 && diff_format == D_EDIT) {
1218 /*
1219 * A non-zero edoffset value for D_EDIT indicates that the
1220 * last line printed was a bare dot (".") that has been
1221 * escaped as ".." to prevent ed(1) from misinterpreting
1222 * it. We have to add a substitute command to change this
1223 * back and restart where we left off.
1224 */
1225 printf(".\n");
1226 printf("%ds/.//\n", a + edoffset - 1);
1227 b = a + edoffset - 1;
1228 a = b + 1;
1229 c += edoffset;
1230 goto restart;
1231 }
1232 if ((diff_format == D_EDIT || diff_format == D_REVERSE) && c <= d)
1233 printf(".\n");
1234 if (inifdef) {
1235 printf("#endif /* %s */\n", ifdefname);
1236 inifdef = 0;
1237 }
1238 }
1239
1240 static int
fetch(long * f,int a,int b,FILE * lb,int ch,int oldfile,int flags)1241 fetch(long *f, int a, int b, FILE *lb, int ch, int oldfile, int flags)
1242 {
1243 int i, j, c, lastc, col, nc, newcol;
1244
1245 edoffset = 0;
1246 nc = 0;
1247 /*
1248 * When doing #ifdef's, copy down to current line
1249 * if this is the first file, so that stuff makes it to output.
1250 */
1251 if ((diff_format == D_IFDEF) && oldfile) {
1252 long curpos = ftell(lb);
1253 /* print through if append (a>b), else to (nb: 0 vs 1 orig) */
1254 nc = f[a > b ? b : a - 1] - curpos;
1255 for (i = 0; i < nc; i++)
1256 printf("%c", getc(lb));
1257 }
1258 if (a > b)
1259 return (0);
1260 if (diff_format == D_IFDEF) {
1261 if (inifdef) {
1262 printf("#else /* %s%s */\n",
1263 oldfile == 1 ? "!" : "", ifdefname);
1264 } else {
1265 if (oldfile)
1266 printf("#ifndef %s\n", ifdefname);
1267 else
1268 printf("#ifdef %s\n", ifdefname);
1269 }
1270 inifdef = 1 + oldfile;
1271 }
1272 for (i = a; i <= b; i++) {
1273 fseek(lb, f[i - 1], SEEK_SET);
1274 nc = (f[i] - f[i - 1]);
1275 if (diff_format == D_SIDEBYSIDE && hw < nc)
1276 nc = hw;
1277 if ((diff_format != D_IFDEF && diff_format != D_GFORMAT) &&
1278 ch != '\0') {
1279 printf("%c", ch);
1280 if (Tflag && (diff_format == D_NORMAL ||
1281 diff_format == D_CONTEXT ||
1282 diff_format == D_UNIFIED))
1283 printf("\t");
1284 else if (diff_format != D_UNIFIED)
1285 printf(" ");
1286 }
1287 col = 0;
1288 for (j = 0, lastc = '\0'; j < nc; j++, lastc = c) {
1289 c = getc(lb);
1290 if (flags & D_STRIPCR && c == '\r') {
1291 if ((c = getc(lb)) == '\n')
1292 j++;
1293 else {
1294 ungetc(c, lb);
1295 c = '\r';
1296 }
1297 }
1298 if (c == EOF) {
1299 if (diff_format == D_EDIT ||
1300 diff_format == D_REVERSE ||
1301 diff_format == D_NREVERSE)
1302 warnx("No newline at end of file");
1303 else
1304 printf("\n\\ No newline at end of "
1305 "file\n");
1306 return col;
1307 }
1308 /*
1309 * when using --side-by-side, col needs to be increased
1310 * in any case to keep the columns aligned
1311 */
1312 if (c == '\t') {
1313 if (flags & D_EXPANDTABS) {
1314 newcol = ((col/tabsize)+1)*tabsize;
1315 do {
1316 if (diff_format == D_SIDEBYSIDE)
1317 j++;
1318 printf(" ");
1319 } while (++col < newcol && j < nc);
1320 } else {
1321 if (diff_format == D_SIDEBYSIDE) {
1322 if ((j + tabsize) > nc) {
1323 printf("%*s",
1324 nc - j,"");
1325 j = col = nc;
1326 } else {
1327 printf("\t");
1328 col += tabsize - 1;
1329 j += tabsize - 1;
1330 }
1331 } else {
1332 printf("\t");
1333 col++;
1334 }
1335 }
1336 } else {
1337 if (diff_format == D_EDIT && j == 1 && c == '\n'
1338 && lastc == '.') {
1339 /*
1340 * Don't print a bare "." line
1341 * since that will confuse ed(1).
1342 * Print ".." instead and set the,
1343 * global variable edoffset to an
1344 * offset from which to restart.
1345 * The caller must check the value
1346 * of edoffset
1347 */
1348 printf(".\n");
1349 edoffset = i - a + 1;
1350 return edoffset;
1351 }
1352 /* when side-by-side, do not print a newline */
1353 if (diff_format != D_SIDEBYSIDE || c != '\n') {
1354 printf("%c", c);
1355 col++;
1356 }
1357 }
1358 }
1359 }
1360 return col;
1361 }
1362
1363 /*
1364 * Hash function taken from Robert Sedgewick, Algorithms in C, 3d ed., p 578.
1365 */
1366 static enum readhash
readhash(FILE * f,int flags,unsigned * hash)1367 readhash(FILE *f, int flags, unsigned *hash)
1368 {
1369 int i, t, space;
1370 unsigned sum;
1371
1372 sum = 1;
1373 space = 0;
1374 for (i = 0;;) {
1375 switch (t = getc(f)) {
1376 case '\0':
1377 if ((flags & D_FORCEASCII) == 0)
1378 return (RH_BINARY);
1379 case '\r':
1380 if (flags & D_STRIPCR) {
1381 t = getc(f);
1382 if (t == '\n')
1383 break;
1384 ungetc(t, f);
1385 }
1386 /* FALLTHROUGH */
1387 case '\t':
1388 case '\v':
1389 case '\f':
1390 case ' ':
1391 if ((flags & (D_FOLDBLANKS|D_IGNOREBLANKS)) != 0) {
1392 space++;
1393 continue;
1394 }
1395 /* FALLTHROUGH */
1396 default:
1397 if (space && (flags & D_IGNOREBLANKS) == 0) {
1398 i++;
1399 space = 0;
1400 }
1401 sum = sum * 127 + chrtran(t);
1402 i++;
1403 continue;
1404 case EOF:
1405 if (i == 0)
1406 return (RH_EOF);
1407 /* FALLTHROUGH */
1408 case '\n':
1409 break;
1410 }
1411 break;
1412 }
1413 *hash = sum;
1414 return (RH_OK);
1415 }
1416
1417 static int
asciifile(FILE * f)1418 asciifile(FILE *f)
1419 {
1420 unsigned char buf[BUFSIZ];
1421 size_t cnt;
1422
1423 if (f == NULL)
1424 return (1);
1425
1426 rewind(f);
1427 cnt = fread(buf, 1, sizeof(buf), f);
1428 return (memchr(buf, '\0', cnt) == NULL);
1429 }
1430
1431 #define begins_with(s, pre) (strncmp(s, pre, sizeof(pre)-1) == 0)
1432
1433 static char *
match_function(const long * f,int pos,FILE * fp)1434 match_function(const long *f, int pos, FILE *fp)
1435 {
1436 unsigned char buf[FUNCTION_CONTEXT_SIZE];
1437 size_t nc;
1438 int last = lastline;
1439 const char *state = NULL;
1440
1441 lastline = pos;
1442 while (pos > last) {
1443 fseek(fp, f[pos - 1], SEEK_SET);
1444 nc = f[pos] - f[pos - 1];
1445 if (nc >= sizeof(buf))
1446 nc = sizeof(buf) - 1;
1447 nc = fread(buf, 1, nc, fp);
1448 if (nc > 0) {
1449 buf[nc] = '\0';
1450 buf[strcspn(buf, "\n")] = '\0';
1451 if (isalpha(buf[0]) || buf[0] == '_' || buf[0] == '$') {
1452 if (begins_with(buf, "private:")) {
1453 if (!state)
1454 state = " (private)";
1455 } else if (begins_with(buf, "protected:")) {
1456 if (!state)
1457 state = " (protected)";
1458 } else if (begins_with(buf, "public:")) {
1459 if (!state)
1460 state = " (public)";
1461 } else {
1462 strlcpy(lastbuf, buf, sizeof lastbuf);
1463 if (state)
1464 strlcat(lastbuf, state,
1465 sizeof lastbuf);
1466 lastmatchline = pos;
1467 return lastbuf;
1468 }
1469 }
1470 }
1471 pos--;
1472 }
1473 return lastmatchline > 0 ? lastbuf : NULL;
1474 }
1475
1476 /* dump accumulated "context" diff changes */
1477 static void
dump_context_vec(FILE * f1,FILE * f2,int flags)1478 dump_context_vec(FILE *f1, FILE *f2, int flags)
1479 {
1480 struct context_vec *cvp = context_vec_start;
1481 int lowa, upb, lowc, upd, do_output;
1482 int a, b, c, d;
1483 char ch, *f;
1484
1485 if (context_vec_start > context_vec_ptr)
1486 return;
1487
1488 b = d = 0; /* gcc */
1489 lowa = MAX(1, cvp->a - diff_context);
1490 upb = MIN(len[0], context_vec_ptr->b + diff_context);
1491 lowc = MAX(1, cvp->c - diff_context);
1492 upd = MIN(len[1], context_vec_ptr->d + diff_context);
1493
1494 printf("***************");
1495 if ((flags & D_PROTOTYPE)) {
1496 f = match_function(ixold, lowa-1, f1);
1497 if (f != NULL)
1498 printf(" %s", f);
1499 }
1500 printf("\n*** ");
1501 range(lowa, upb, ",");
1502 printf(" ****\n");
1503
1504 /*
1505 * Output changes to the "old" file. The first loop suppresses
1506 * output if there were no changes to the "old" file (we'll see
1507 * the "old" lines as context in the "new" list).
1508 */
1509 do_output = 0;
1510 for (; cvp <= context_vec_ptr; cvp++)
1511 if (cvp->a <= cvp->b) {
1512 cvp = context_vec_start;
1513 do_output++;
1514 break;
1515 }
1516 if (do_output) {
1517 while (cvp <= context_vec_ptr) {
1518 a = cvp->a;
1519 b = cvp->b;
1520 c = cvp->c;
1521 d = cvp->d;
1522
1523 if (a <= b && c <= d)
1524 ch = 'c';
1525 else
1526 ch = (a <= b) ? 'd' : 'a';
1527
1528 if (ch == 'a')
1529 fetch(ixold, lowa, b, f1, ' ', 0, flags);
1530 else {
1531 fetch(ixold, lowa, a - 1, f1, ' ', 0, flags);
1532 fetch(ixold, a, b, f1,
1533 ch == 'c' ? '!' : '-', 0, flags);
1534 }
1535 lowa = b + 1;
1536 cvp++;
1537 }
1538 fetch(ixold, b + 1, upb, f1, ' ', 0, flags);
1539 }
1540 /* output changes to the "new" file */
1541 printf("--- ");
1542 range(lowc, upd, ",");
1543 printf(" ----\n");
1544
1545 do_output = 0;
1546 for (cvp = context_vec_start; cvp <= context_vec_ptr; cvp++)
1547 if (cvp->c <= cvp->d) {
1548 cvp = context_vec_start;
1549 do_output++;
1550 break;
1551 }
1552 if (do_output) {
1553 while (cvp <= context_vec_ptr) {
1554 a = cvp->a;
1555 b = cvp->b;
1556 c = cvp->c;
1557 d = cvp->d;
1558
1559 if (a <= b && c <= d)
1560 ch = 'c';
1561 else
1562 ch = (a <= b) ? 'd' : 'a';
1563
1564 if (ch == 'd')
1565 fetch(ixnew, lowc, d, f2, ' ', 0, flags);
1566 else {
1567 fetch(ixnew, lowc, c - 1, f2, ' ', 0, flags);
1568 fetch(ixnew, c, d, f2,
1569 ch == 'c' ? '!' : '+', 0, flags);
1570 }
1571 lowc = d + 1;
1572 cvp++;
1573 }
1574 fetch(ixnew, d + 1, upd, f2, ' ', 0, flags);
1575 }
1576 context_vec_ptr = context_vec_start - 1;
1577 }
1578
1579 /* dump accumulated "unified" diff changes */
1580 static void
dump_unified_vec(FILE * f1,FILE * f2,int flags)1581 dump_unified_vec(FILE *f1, FILE *f2, int flags)
1582 {
1583 struct context_vec *cvp = context_vec_start;
1584 int lowa, upb, lowc, upd;
1585 int a, b, c, d;
1586 char ch, *f;
1587
1588 if (context_vec_start > context_vec_ptr)
1589 return;
1590
1591 b = d = 0; /* gcc */
1592 lowa = MAX(1, cvp->a - diff_context);
1593 upb = MIN(len[0], context_vec_ptr->b + diff_context);
1594 lowc = MAX(1, cvp->c - diff_context);
1595 upd = MIN(len[1], context_vec_ptr->d + diff_context);
1596
1597 printf("@@ -");
1598 uni_range(lowa, upb);
1599 printf(" +");
1600 uni_range(lowc, upd);
1601 printf(" @@");
1602 if ((flags & D_PROTOTYPE)) {
1603 f = match_function(ixold, lowa-1, f1);
1604 if (f != NULL)
1605 printf(" %s", f);
1606 }
1607 printf("\n");
1608
1609 /*
1610 * Output changes in "unified" diff format--the old and new lines
1611 * are printed together.
1612 */
1613 for (; cvp <= context_vec_ptr; cvp++) {
1614 a = cvp->a;
1615 b = cvp->b;
1616 c = cvp->c;
1617 d = cvp->d;
1618
1619 /*
1620 * c: both new and old changes
1621 * d: only changes in the old file
1622 * a: only changes in the new file
1623 */
1624 if (a <= b && c <= d)
1625 ch = 'c';
1626 else
1627 ch = (a <= b) ? 'd' : 'a';
1628
1629 switch (ch) {
1630 case 'c':
1631 fetch(ixold, lowa, a - 1, f1, ' ', 0, flags);
1632 fetch(ixold, a, b, f1, '-', 0, flags);
1633 fetch(ixnew, c, d, f2, '+', 0, flags);
1634 break;
1635 case 'd':
1636 fetch(ixold, lowa, a - 1, f1, ' ', 0, flags);
1637 fetch(ixold, a, b, f1, '-', 0, flags);
1638 break;
1639 case 'a':
1640 fetch(ixnew, lowc, c - 1, f2, ' ', 0, flags);
1641 fetch(ixnew, c, d, f2, '+', 0, flags);
1642 break;
1643 }
1644 lowa = b + 1;
1645 lowc = d + 1;
1646 }
1647 fetch(ixnew, d + 1, upd, f2, ' ', 0, flags);
1648
1649 context_vec_ptr = context_vec_start - 1;
1650 }
1651
1652 static void
print_header(const char * file1,const char * file2)1653 print_header(const char *file1, const char *file2)
1654 {
1655 const char *time_format;
1656 char buf1[256];
1657 char buf2[256];
1658 char end1[10];
1659 char end2[10];
1660 struct tm tm1, tm2, *tm_ptr1, *tm_ptr2;
1661 int nsec1 = stb1.st_mtim.tv_nsec;
1662 int nsec2 = stb2.st_mtim.tv_nsec;
1663
1664 time_format = "%Y-%m-%d %H:%M:%S";
1665
1666 if (cflag)
1667 time_format = "%c";
1668 tm_ptr1 = localtime_r(&stb1.st_mtime, &tm1);
1669 tm_ptr2 = localtime_r(&stb2.st_mtime, &tm2);
1670 strftime(buf1, 256, time_format, tm_ptr1);
1671 strftime(buf2, 256, time_format, tm_ptr2);
1672 if (!cflag) {
1673 strftime(end1, 10, "%z", tm_ptr1);
1674 strftime(end2, 10, "%z", tm_ptr2);
1675 sprintf(buf1, "%s.%.9d %s", buf1, nsec1, end1);
1676 sprintf(buf2, "%s.%.9d %s", buf2, nsec2, end2);
1677 }
1678 if (label[0] != NULL)
1679 printf("%s %s\n", diff_format == D_CONTEXT ? "***" : "---",
1680 label[0]);
1681 else
1682 printf("%s %s\t%s\n", diff_format == D_CONTEXT ? "***" : "---",
1683 file1, buf1);
1684 if (label[1] != NULL)
1685 printf("%s %s\n", diff_format == D_CONTEXT ? "---" : "+++",
1686 label[1]);
1687 else
1688 printf("%s %s\t%s\n", diff_format == D_CONTEXT ? "---" : "+++",
1689 file2, buf2);
1690 }
1691
1692 /*
1693 * Prints n number of space characters either by using tab
1694 * or single space characters.
1695 * nc is the preceding number of characters
1696 */
1697 static void
print_space(int nc,int n,int flags)1698 print_space(int nc, int n, int flags) {
1699 int i, col;
1700
1701 col = n;
1702 if ((flags & D_EXPANDTABS) == 0) {
1703 /* first tabstop may be closer than tabsize */
1704 i = tabsize - (nc % tabsize);
1705 while (col >= tabsize) {
1706 printf("\t");
1707 col -= i;
1708 i = tabsize;
1709 }
1710 }
1711 printf("%*s", col, "");
1712 }
1713