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