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