1 /* $OpenBSD: diff.c,v 1.35 2014/10/10 08:15:25 otto 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 cnt; 1136 1137 if (f == NULL) 1138 return (1); 1139 1140 rewind(f); 1141 cnt = fread(buf, 1, sizeof(buf), f); 1142 return (memchr(buf, '\0', cnt) == NULL); 1143 } 1144 1145 #define begins_with(s, pre) (strncmp(s, pre, sizeof(pre)-1) == 0) 1146 1147 static char * 1148 match_function(const long *f, int pos, FILE *fp) 1149 { 1150 unsigned char buf[FUNCTION_CONTEXT_SIZE]; 1151 size_t nc; 1152 int last = lastline; 1153 char *state = NULL; 1154 1155 lastline = pos; 1156 while (pos > last) { 1157 fseek(fp, f[pos - 1], SEEK_SET); 1158 nc = f[pos] - f[pos - 1]; 1159 if (nc >= sizeof(buf)) 1160 nc = sizeof(buf) - 1; 1161 nc = fread(buf, 1, nc, fp); 1162 if (nc > 0) { 1163 buf[nc] = '\0'; 1164 buf[strcspn(buf, "\n")] = '\0'; 1165 if (isalpha(buf[0]) || buf[0] == '_' || buf[0] == '$') { 1166 if (begins_with(buf, "private:")) { 1167 if (!state) 1168 state = " (private)"; 1169 } else if (begins_with(buf, "protected:")) { 1170 if (!state) 1171 state = " (protected)"; 1172 } else if (begins_with(buf, "public:")) { 1173 if (!state) 1174 state = " (public)"; 1175 } else { 1176 if (strlcpy(lastbuf, buf, 1177 sizeof(lastbuf)) >= sizeof(lastbuf)) 1178 errx(1, 1179 "match_function: strlcpy"); 1180 lastmatchline = pos; 1181 return lastbuf; 1182 } 1183 } 1184 } 1185 pos--; 1186 } 1187 return lastmatchline > 0 ? lastbuf : NULL; 1188 } 1189 1190 /* dump accumulated "context" diff changes */ 1191 static void 1192 dump_context_vec(FILE *f1, FILE *f2, int flags) 1193 { 1194 struct context_vec *cvp = context_vec_start; 1195 int lowa, upb, lowc, upd, do_output; 1196 int a, b, c, d; 1197 char ch, *f; 1198 1199 if (context_vec_start > context_vec_ptr) 1200 return; 1201 1202 b = d = 0; /* gcc */ 1203 lowa = MAX(1, cvp->a - diff_context); 1204 upb = MIN(len[0], context_vec_ptr->b + diff_context); 1205 lowc = MAX(1, cvp->c - diff_context); 1206 upd = MIN(len[1], context_vec_ptr->d + diff_context); 1207 1208 diff_output("***************"); 1209 if ((flags & D_PROTOTYPE)) { 1210 f = match_function(ixold, lowa-1, f1); 1211 if (f != NULL) 1212 diff_output(" %s", f); 1213 } 1214 diff_output("\n*** "); 1215 range(lowa, upb, ","); 1216 diff_output(" ****\n"); 1217 1218 /* 1219 * Output changes to the "old" file. The first loop suppresses 1220 * output if there were no changes to the "old" file (we'll see 1221 * the "old" lines as context in the "new" list). 1222 */ 1223 do_output = 0; 1224 for (; cvp <= context_vec_ptr; cvp++) 1225 if (cvp->a <= cvp->b) { 1226 cvp = context_vec_start; 1227 do_output++; 1228 break; 1229 } 1230 if (do_output) { 1231 while (cvp <= context_vec_ptr) { 1232 a = cvp->a; 1233 b = cvp->b; 1234 c = cvp->c; 1235 d = cvp->d; 1236 1237 if (a <= b && c <= d) 1238 ch = 'c'; 1239 else 1240 ch = (a <= b) ? 'd' : 'a'; 1241 1242 if (ch == 'a') 1243 fetch(ixold, lowa, b, f1, ' ', 0, flags); 1244 else { 1245 fetch(ixold, lowa, a - 1, f1, ' ', 0, flags); 1246 fetch(ixold, a, b, f1, 1247 ch == 'c' ? '!' : '-', 0, flags); 1248 } 1249 lowa = b + 1; 1250 cvp++; 1251 } 1252 fetch(ixold, b + 1, upb, f1, ' ', 0, flags); 1253 } 1254 /* output changes to the "new" file */ 1255 diff_output("--- "); 1256 range(lowc, upd, ","); 1257 diff_output(" ----\n"); 1258 1259 do_output = 0; 1260 for (cvp = context_vec_start; cvp <= context_vec_ptr; cvp++) 1261 if (cvp->c <= cvp->d) { 1262 cvp = context_vec_start; 1263 do_output++; 1264 break; 1265 } 1266 if (do_output) { 1267 while (cvp <= context_vec_ptr) { 1268 a = cvp->a; 1269 b = cvp->b; 1270 c = cvp->c; 1271 d = cvp->d; 1272 1273 if (a <= b && c <= d) 1274 ch = 'c'; 1275 else 1276 ch = (a <= b) ? 'd' : 'a'; 1277 1278 if (ch == 'd') 1279 fetch(ixnew, lowc, d, f2, ' ', 0, flags); 1280 else { 1281 fetch(ixnew, lowc, c - 1, f2, ' ', 0, flags); 1282 fetch(ixnew, c, d, f2, 1283 ch == 'c' ? '!' : '+', 0, flags); 1284 } 1285 lowc = d + 1; 1286 cvp++; 1287 } 1288 fetch(ixnew, d + 1, upd, f2, ' ', 0, flags); 1289 } 1290 context_vec_ptr = context_vec_start - 1; 1291 } 1292 1293 /* dump accumulated "unified" diff changes */ 1294 static void 1295 dump_unified_vec(FILE *f1, FILE *f2, int flags) 1296 { 1297 struct context_vec *cvp = context_vec_start; 1298 int lowa, upb, lowc, upd; 1299 int a, b, c, d; 1300 char ch, *f; 1301 1302 if (context_vec_start > context_vec_ptr) 1303 return; 1304 1305 d = 0; /* gcc */ 1306 lowa = MAX(1, cvp->a - diff_context); 1307 upb = MIN(len[0], context_vec_ptr->b + diff_context); 1308 lowc = MAX(1, cvp->c - diff_context); 1309 upd = MIN(len[1], context_vec_ptr->d + diff_context); 1310 1311 diff_output("@@ -"); 1312 uni_range(lowa, upb); 1313 diff_output(" +"); 1314 uni_range(lowc, upd); 1315 diff_output(" @@"); 1316 if ((flags & D_PROTOTYPE)) { 1317 f = match_function(ixold, lowa-1, f1); 1318 if (f != NULL) 1319 diff_output(" %s", f); 1320 } 1321 diff_output("\n"); 1322 1323 /* 1324 * Output changes in "unified" diff format--the old and new lines 1325 * are printed together. 1326 */ 1327 for (; cvp <= context_vec_ptr; cvp++) { 1328 a = cvp->a; 1329 b = cvp->b; 1330 c = cvp->c; 1331 d = cvp->d; 1332 1333 /* 1334 * c: both new and old changes 1335 * d: only changes in the old file 1336 * a: only changes in the new file 1337 */ 1338 if (a <= b && c <= d) 1339 ch = 'c'; 1340 else 1341 ch = (a <= b) ? 'd' : 'a'; 1342 1343 switch (ch) { 1344 case 'c': 1345 fetch(ixold, lowa, a - 1, f1, ' ', 0, flags); 1346 fetch(ixold, a, b, f1, '-', 0, flags); 1347 fetch(ixnew, c, d, f2, '+', 0, flags); 1348 break; 1349 case 'd': 1350 fetch(ixold, lowa, a - 1, f1, ' ', 0, flags); 1351 fetch(ixold, a, b, f1, '-', 0, flags); 1352 break; 1353 case 'a': 1354 fetch(ixnew, lowc, c - 1, f2, ' ', 0, flags); 1355 fetch(ixnew, c, d, f2, '+', 0, flags); 1356 break; 1357 } 1358 lowa = b + 1; 1359 lowc = d + 1; 1360 } 1361 fetch(ixnew, d + 1, upd, f2, ' ', 0, flags); 1362 1363 context_vec_ptr = context_vec_start - 1; 1364 } 1365 1366 void 1367 diff_output(const char *fmt, ...) 1368 { 1369 va_list vap; 1370 int i; 1371 char *str; 1372 1373 va_start(vap, fmt); 1374 i = vasprintf(&str, fmt, vap); 1375 va_end(vap); 1376 if (i == -1) 1377 err(1, "diff_output"); 1378 if (diffbuf != NULL) 1379 buf_append(diffbuf, str, strlen(str)); 1380 else 1381 printf("%s", str); 1382 xfree(str); 1383 } 1384