1 /* $OpenBSD: diff.c,v 1.28 2010/07/15 18:19:18 ray 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; 525 u_int numtries; 526 527 /* XXX move the isqrt() out of the macro to avoid multiple calls */ 528 const u_int bound = (flags & D_MINIMAL) ? UINT_MAX : 529 MAX(256, isqrt(n)); 530 531 k = 0; 532 c[0] = newcand(0, 0, 0); 533 for (i = 1; i <= n; i++) { 534 j = a[i]; 535 if (j == 0) 536 continue; 537 y = -b[j]; 538 oldl = 0; 539 oldc = c[0]; 540 numtries = 0; 541 do { 542 if (y <= clist[oldc].y) 543 continue; 544 l = search(c, k, y); 545 if (l != oldl + 1) 546 oldc = c[l - 1]; 547 if (l <= k) { 548 if (clist[c[l]].y <= y) 549 continue; 550 tc = c[l]; 551 c[l] = newcand(i, y, oldc); 552 oldc = tc; 553 oldl = l; 554 numtries++; 555 } else { 556 c[l] = newcand(i, y, oldc); 557 k++; 558 break; 559 } 560 } while ((y = b[++j]) > 0 && numtries < bound); 561 } 562 return (k); 563 } 564 565 static int 566 newcand(int x, int y, int pred) 567 { 568 struct cand *q; 569 570 if (clen == clistlen) { 571 clistlen = clistlen * 11 / 10; 572 clist = xrealloc(clist, clistlen, sizeof(*clist)); 573 } 574 q = clist + clen; 575 q->x = x; 576 q->y = y; 577 q->pred = pred; 578 return (clen++); 579 } 580 581 static int 582 search(int *c, int k, int y) 583 { 584 int i, j, l, t; 585 586 if (clist[c[k]].y < y) /* quick look for typical case */ 587 return (k + 1); 588 i = 0; 589 j = k + 1; 590 for (;;) { 591 l = (i + j) / 2; 592 if (l <= i) 593 break; 594 t = clist[c[l]].y; 595 if (t > y) 596 j = l; 597 else if (t < y) 598 i = l; 599 else 600 return (l); 601 } 602 return (l + 1); 603 } 604 605 static void 606 unravel(int p) 607 { 608 struct cand *q; 609 int i; 610 611 for (i = 0; i <= len[0]; i++) 612 J[i] = i <= pref ? i : 613 i > len[0] - suff ? i + len[1] - len[0] : 0; 614 for (q = clist + p; q->y != 0; q = clist + q->pred) 615 J[q->x + pref] = q->y + pref; 616 } 617 618 /* 619 * Check does double duty: 620 * 1. ferret out any fortuitous correspondences due 621 * to confounding by hashing (which result in "jackpot") 622 * 2. collect random access indexes to the two files 623 */ 624 static void 625 check(FILE *f1, FILE *f2, int flags) 626 { 627 int i, j, jackpot, c, d; 628 long ctold, ctnew; 629 630 rewind(f1); 631 rewind(f2); 632 j = 1; 633 ixold[0] = ixnew[0] = 0; 634 jackpot = 0; 635 ctold = ctnew = 0; 636 for (i = 1; i <= len[0]; i++) { 637 if (J[i] == 0) { 638 ixold[i] = ctold += skipline(f1); 639 continue; 640 } 641 while (j < J[i]) { 642 ixnew[j] = ctnew += skipline(f2); 643 j++; 644 } 645 if (flags & (D_FOLDBLANKS|D_IGNOREBLANKS|D_IGNORECASE)) { 646 for (;;) { 647 c = getc(f1); 648 d = getc(f2); 649 /* 650 * GNU diff ignores a missing newline 651 * in one file for -b or -w. 652 */ 653 if ((flags & (D_FOLDBLANKS|D_IGNOREBLANKS)) && 654 ((c == EOF && d == '\n') || 655 (c == '\n' && d == EOF))) { 656 break; 657 } 658 ctold++; 659 ctnew++; 660 if ((flags & D_FOLDBLANKS) && isspace(c) && 661 isspace(d)) { 662 do { 663 if (c == '\n') 664 break; 665 ctold++; 666 } while (isspace(c = getc(f1))); 667 do { 668 if (d == '\n') 669 break; 670 ctnew++; 671 } while (isspace(d = getc(f2))); 672 } else if ((flags & D_IGNOREBLANKS)) { 673 while (isspace(c) && c != '\n') { 674 c = getc(f1); 675 ctold++; 676 } 677 while (isspace(d) && d != '\n') { 678 d = getc(f2); 679 ctnew++; 680 } 681 } 682 if (chrtran[c] != chrtran[d]) { 683 jackpot++; 684 J[i] = 0; 685 if (c != '\n' && c != EOF) 686 ctold += skipline(f1); 687 if (d != '\n' && c != EOF) 688 ctnew += skipline(f2); 689 break; 690 } 691 if (c == '\n' || c == EOF) 692 break; 693 } 694 } else { 695 for (;;) { 696 ctold++; 697 ctnew++; 698 if ((c = getc(f1)) != (d = getc(f2))) { 699 /* jackpot++; */ 700 J[i] = 0; 701 if (c != '\n' && c != EOF) 702 ctold += skipline(f1); 703 if (d != '\n' && c != EOF) 704 ctnew += skipline(f2); 705 break; 706 } 707 if (c == '\n' || c == EOF) 708 break; 709 } 710 } 711 ixold[i] = ctold; 712 ixnew[j] = ctnew; 713 j++; 714 } 715 for (; j <= len[1]; j++) 716 ixnew[j] = ctnew += skipline(f2); 717 /* 718 * if (jackpot) 719 * fprintf(stderr, "jackpot\n"); 720 */ 721 } 722 723 /* shellsort CACM #201 */ 724 static void 725 sort(struct line *a, int n) 726 { 727 struct line *ai, *aim, w; 728 int j, m = 0, k; 729 730 if (n == 0) 731 return; 732 for (j = 1; j <= n; j *= 2) 733 m = 2 * j - 1; 734 for (m /= 2; m != 0; m /= 2) { 735 k = n - m; 736 for (j = 1; j <= k; j++) { 737 for (ai = &a[j]; ai > a; ai -= m) { 738 aim = &ai[m]; 739 if (aim < ai) 740 break; /* wraparound */ 741 if (aim->value > ai[0].value || 742 (aim->value == ai[0].value && 743 aim->serial > ai[0].serial)) 744 break; 745 w.value = ai[0].value; 746 ai[0].value = aim->value; 747 aim->value = w.value; 748 w.serial = ai[0].serial; 749 ai[0].serial = aim->serial; 750 aim->serial = w.serial; 751 } 752 } 753 } 754 } 755 756 static void 757 unsort(struct line *f, int l, int *b) 758 { 759 int *a, i; 760 761 a = xcalloc(l + 1, sizeof(*a)); 762 for (i = 1; i <= l; i++) 763 a[f[i].serial] = f[i].value; 764 for (i = 1; i <= l; i++) 765 b[i] = a[i]; 766 xfree(a); 767 } 768 769 static int 770 skipline(FILE *f) 771 { 772 int i, c; 773 774 for (i = 1; (c = getc(f)) != '\n' && c != EOF; i++) 775 continue; 776 return (i); 777 } 778 779 static void 780 output(FILE *f1, FILE *f2, int flags) 781 { 782 int m, i0, i1, j0, j1; 783 784 rewind(f1); 785 rewind(f2); 786 m = len[0]; 787 J[0] = 0; 788 J[m + 1] = len[1] + 1; 789 for (i0 = 1; i0 <= m; i0 = i1 + 1) { 790 while (i0 <= m && J[i0] == J[i0 - 1] + 1) 791 i0++; 792 j0 = J[i0 - 1] + 1; 793 i1 = i0 - 1; 794 while (i1 < m && J[i1 + 1] == 0) 795 i1++; 796 j1 = J[i1 + 1] - 1; 797 J[i1] = j1; 798 change(f1, f2, i0, i1, j0, j1, flags); 799 } 800 if (m == 0) 801 change(f1, f2, 1, 0, 1, len[1], flags); 802 if (diff_format == D_IFDEF) { 803 for (;;) { 804 #define c i0 805 if ((c = getc(f1)) == EOF) 806 return; 807 diff_output("%c", c); 808 } 809 #undef c 810 } 811 if (anychange != 0) { 812 if (diff_format == D_CONTEXT) 813 dump_context_vec(f1, f2, flags); 814 else if (diff_format == D_UNIFIED) 815 dump_unified_vec(f1, f2, flags); 816 } 817 } 818 819 static void 820 range(int a, int b, char *separator) 821 { 822 diff_output("%d", a > b ? b : a); 823 if (a < b) 824 diff_output("%s%d", separator, b); 825 } 826 827 static void 828 uni_range(int a, int b) 829 { 830 if (a < b) 831 diff_output("%d,%d", a, b - a + 1); 832 else if (a == b) 833 diff_output("%d", b); 834 else 835 diff_output("%d,0", b); 836 } 837 838 static char * 839 preadline(int fd, size_t rlen, off_t off) 840 { 841 char *line; 842 ssize_t nr; 843 844 line = xmalloc(rlen + 1); 845 if ((nr = pread(fd, line, rlen, off)) < 0) { 846 warn("preadline failed"); 847 xfree(line); 848 return (NULL); 849 } 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(" "); 1217 diff_output("%s", f); 1218 } 1219 } 1220 diff_output("\n*** "); 1221 range(lowa, upb, ","); 1222 diff_output(" ****\n"); 1223 1224 /* 1225 * Output changes to the "old" file. The first loop suppresses 1226 * output if there were no changes to the "old" file (we'll see 1227 * the "old" lines as context in the "new" list). 1228 */ 1229 do_output = 0; 1230 for (; cvp <= context_vec_ptr; cvp++) 1231 if (cvp->a <= cvp->b) { 1232 cvp = context_vec_start; 1233 do_output++; 1234 break; 1235 } 1236 if (do_output) { 1237 while (cvp <= context_vec_ptr) { 1238 a = cvp->a; 1239 b = cvp->b; 1240 c = cvp->c; 1241 d = cvp->d; 1242 1243 if (a <= b && c <= d) 1244 ch = 'c'; 1245 else 1246 ch = (a <= b) ? 'd' : 'a'; 1247 1248 if (ch == 'a') 1249 fetch(ixold, lowa, b, f1, ' ', 0, flags); 1250 else { 1251 fetch(ixold, lowa, a - 1, f1, ' ', 0, flags); 1252 fetch(ixold, a, b, f1, 1253 ch == 'c' ? '!' : '-', 0, flags); 1254 } 1255 lowa = b + 1; 1256 cvp++; 1257 } 1258 fetch(ixold, b + 1, upb, f1, ' ', 0, flags); 1259 } 1260 /* output changes to the "new" file */ 1261 diff_output("--- "); 1262 range(lowc, upd, ","); 1263 diff_output(" ----\n"); 1264 1265 do_output = 0; 1266 for (cvp = context_vec_start; cvp <= context_vec_ptr; cvp++) 1267 if (cvp->c <= cvp->d) { 1268 cvp = context_vec_start; 1269 do_output++; 1270 break; 1271 } 1272 if (do_output) { 1273 while (cvp <= context_vec_ptr) { 1274 a = cvp->a; 1275 b = cvp->b; 1276 c = cvp->c; 1277 d = cvp->d; 1278 1279 if (a <= b && c <= d) 1280 ch = 'c'; 1281 else 1282 ch = (a <= b) ? 'd' : 'a'; 1283 1284 if (ch == 'd') 1285 fetch(ixnew, lowc, d, f2, ' ', 0, flags); 1286 else { 1287 fetch(ixnew, lowc, c - 1, f2, ' ', 0, flags); 1288 fetch(ixnew, c, d, f2, 1289 ch == 'c' ? '!' : '+', 0, flags); 1290 } 1291 lowc = d + 1; 1292 cvp++; 1293 } 1294 fetch(ixnew, d + 1, upd, f2, ' ', 0, flags); 1295 } 1296 context_vec_ptr = context_vec_start - 1; 1297 } 1298 1299 /* dump accumulated "unified" diff changes */ 1300 static void 1301 dump_unified_vec(FILE *f1, FILE *f2, int flags) 1302 { 1303 struct context_vec *cvp = context_vec_start; 1304 int lowa, upb, lowc, upd; 1305 int a, b, c, d; 1306 char ch, *f; 1307 1308 if (context_vec_start > context_vec_ptr) 1309 return; 1310 1311 b = d = 0; /* gcc */ 1312 lowa = MAX(1, cvp->a - diff_context); 1313 upb = MIN(len[0], context_vec_ptr->b + diff_context); 1314 lowc = MAX(1, cvp->c - diff_context); 1315 upd = MIN(len[1], context_vec_ptr->d + diff_context); 1316 1317 diff_output("@@ -"); 1318 uni_range(lowa, upb); 1319 diff_output(" +"); 1320 uni_range(lowc, upd); 1321 diff_output(" @@"); 1322 if ((flags & D_PROTOTYPE)) { 1323 f = match_function(ixold, lowa-1, f1); 1324 if (f != NULL) { 1325 diff_output(" "); 1326 diff_output("%s", f); 1327 } 1328 } 1329 diff_output("\n"); 1330 1331 /* 1332 * Output changes in "unified" diff format--the old and new lines 1333 * are printed together. 1334 */ 1335 for (; cvp <= context_vec_ptr; cvp++) { 1336 a = cvp->a; 1337 b = cvp->b; 1338 c = cvp->c; 1339 d = cvp->d; 1340 1341 /* 1342 * c: both new and old changes 1343 * d: only changes in the old file 1344 * a: only changes in the new file 1345 */ 1346 if (a <= b && c <= d) 1347 ch = 'c'; 1348 else 1349 ch = (a <= b) ? 'd' : 'a'; 1350 1351 switch (ch) { 1352 case 'c': 1353 fetch(ixold, lowa, a - 1, f1, ' ', 0, flags); 1354 fetch(ixold, a, b, f1, '-', 0, flags); 1355 fetch(ixnew, c, d, f2, '+', 0, flags); 1356 break; 1357 case 'd': 1358 fetch(ixold, lowa, a - 1, f1, ' ', 0, flags); 1359 fetch(ixold, a, b, f1, '-', 0, flags); 1360 break; 1361 case 'a': 1362 fetch(ixnew, lowc, c - 1, f2, ' ', 0, flags); 1363 fetch(ixnew, c, d, f2, '+', 0, flags); 1364 break; 1365 } 1366 lowa = b + 1; 1367 lowc = d + 1; 1368 } 1369 fetch(ixnew, d + 1, upd, f2, ' ', 0, flags); 1370 1371 context_vec_ptr = context_vec_start - 1; 1372 } 1373 1374 void 1375 diff_output(const char *fmt, ...) 1376 { 1377 va_list vap; 1378 int i; 1379 char *str; 1380 1381 va_start(vap, fmt); 1382 i = vasprintf(&str, fmt, vap); 1383 va_end(vap); 1384 if (i == -1) 1385 err(1, "diff_output"); 1386 if (diffbuf != NULL) 1387 rcs_buf_append(diffbuf, str, strlen(str)); 1388 else 1389 printf("%s", str); 1390 xfree(str); 1391 } 1392