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