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