1 /* $OpenBSD: diff.c,v 1.30 2010/07/16 17:53:20 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 err(D_ERROR, "preadline"); 847 line[nr] = '\0'; 848 return (line); 849 } 850 851 static int 852 ignoreline(char *line) 853 { 854 int ret; 855 856 ret = regexec(diff_ignore_re, line, 0, NULL, 0); 857 xfree(line); 858 return (ret == 0); /* if it matched, it should be ignored. */ 859 } 860 861 /* 862 * Indicate that there is a difference between lines a and b of the from file 863 * to get to lines c to d of the to file. If a is greater then b then there 864 * are no lines in the from file involved and this means that there were 865 * lines appended (beginning at b). If c is greater than d then there are 866 * lines missing from the to file. 867 */ 868 static void 869 change(FILE *f1, FILE *f2, int a, int b, int c, int d, int flags) 870 { 871 static size_t max_context = 64; 872 char buf[64]; 873 struct tm *t; 874 int i; 875 876 if (diff_format != D_IFDEF && a > b && c > d) 877 return; 878 if (diff_ignore_re != NULL) { 879 char *line; 880 /* 881 * All lines in the change, insert, or delete must 882 * match an ignore pattern for the change to be 883 * ignored. 884 */ 885 if (a <= b) { /* Changes and deletes. */ 886 for (i = a; i <= b; i++) { 887 line = preadline(fileno(f1), 888 ixold[i] - ixold[i - 1], ixold[i - 1]); 889 if (!ignoreline(line)) 890 goto proceed; 891 } 892 } 893 if (a > b || c <= d) { /* Changes and inserts. */ 894 for (i = c; i <= d; i++) { 895 line = preadline(fileno(f2), 896 ixnew[i] - ixnew[i - 1], ixnew[i - 1]); 897 if (!ignoreline(line)) 898 goto proceed; 899 } 900 } 901 return; 902 } 903 proceed: 904 if (diff_format == D_CONTEXT || diff_format == D_UNIFIED) { 905 /* 906 * Allocate change records as needed. 907 */ 908 if (context_vec_ptr == context_vec_end - 1) { 909 ptrdiff_t offset = context_vec_ptr - context_vec_start; 910 max_context <<= 1; 911 context_vec_start = xrealloc(context_vec_start, 912 max_context, sizeof(*context_vec_start)); 913 context_vec_end = context_vec_start + max_context; 914 context_vec_ptr = context_vec_start + offset; 915 } 916 if (anychange == 0) { 917 /* 918 * Print the context/unidiff header first time through. 919 */ 920 t = localtime(&stb1.st_mtime); 921 (void)strftime(buf, sizeof(buf), 922 "%Y/%m/%d %H:%M:%S", t); 923 924 diff_output("%s %s %s", 925 diff_format == D_CONTEXT ? "***" : "---", diff_file, 926 buf); 927 928 if (diff_rev1 != NULL) { 929 rcsnum_tostr(diff_rev1, buf, sizeof(buf)); 930 diff_output("\t%s", buf); 931 } 932 933 printf("\n"); 934 935 t = localtime(&stb2.st_mtime); 936 (void)strftime(buf, sizeof(buf), 937 "%Y/%m/%d %H:%M:%S", t); 938 939 diff_output("%s %s %s", 940 diff_format == D_CONTEXT ? "---" : "+++", diff_file, 941 buf); 942 943 if (diff_rev2 != NULL) { 944 rcsnum_tostr(diff_rev2, buf, sizeof(buf)); 945 diff_output("\t%s", buf); 946 } 947 948 printf("\n"); 949 anychange = 1; 950 } else if (a > context_vec_ptr->b + (2 * diff_context) + 1 && 951 c > context_vec_ptr->d + (2 * diff_context) + 1) { 952 /* 953 * If this change is more than 'diff_context' lines from the 954 * previous change, dump the record and reset it. 955 */ 956 if (diff_format == D_CONTEXT) 957 dump_context_vec(f1, f2, flags); 958 else 959 dump_unified_vec(f1, f2, flags); 960 } 961 context_vec_ptr++; 962 context_vec_ptr->a = a; 963 context_vec_ptr->b = b; 964 context_vec_ptr->c = c; 965 context_vec_ptr->d = d; 966 return; 967 } 968 if (anychange == 0) 969 anychange = 1; 970 switch (diff_format) { 971 case D_BRIEF: 972 return; 973 case D_NORMAL: 974 range(a, b, ","); 975 diff_output("%c", a > b ? 'a' : c > d ? 'd' : 'c'); 976 if (diff_format == D_NORMAL) 977 range(c, d, ","); 978 diff_output("\n"); 979 break; 980 case D_RCSDIFF: 981 if (a > b) 982 diff_output("a%d %d\n", b, d - c + 1); 983 else { 984 diff_output("d%d %d\n", a, b - a + 1); 985 986 if (!(c > d)) /* add changed lines */ 987 diff_output("a%d %d\n", b, d - c + 1); 988 } 989 break; 990 } 991 if (diff_format == D_NORMAL || diff_format == D_IFDEF) { 992 fetch(ixold, a, b, f1, '<', 1, flags); 993 if (a <= b && c <= d && diff_format == D_NORMAL) 994 diff_output("---\n"); 995 } 996 fetch(ixnew, c, d, f2, diff_format == D_NORMAL ? '>' : '\0', 0, flags); 997 if (inifdef) { 998 diff_output("#endif /* %s */\n", ifdefname); 999 inifdef = 0; 1000 } 1001 } 1002 1003 static void 1004 fetch(long *f, int a, int b, FILE *lb, int ch, int oldfile, int flags) 1005 { 1006 long j, nc; 1007 int i, c, col; 1008 1009 /* 1010 * When doing #ifdef's, copy down to current line 1011 * if this is the first file, so that stuff makes it to output. 1012 */ 1013 if (diff_format == D_IFDEF && oldfile) { 1014 long curpos = ftell(lb); 1015 /* print through if append (a>b), else to (nb: 0 vs 1 orig) */ 1016 nc = f[a > b ? b : a - 1] - curpos; 1017 for (i = 0; i < nc; i++) 1018 diff_output("%c", getc(lb)); 1019 } 1020 if (a > b) 1021 return; 1022 if (diff_format == D_IFDEF) { 1023 if (inifdef) { 1024 diff_output("#else /* %s%s */\n", 1025 oldfile == 1 ? "!" : "", ifdefname); 1026 } else { 1027 if (oldfile) 1028 diff_output("#ifndef %s\n", ifdefname); 1029 else 1030 diff_output("#ifdef %s\n", ifdefname); 1031 } 1032 inifdef = 1 + oldfile; 1033 } 1034 for (i = a; i <= b; i++) { 1035 fseek(lb, f[i - 1], SEEK_SET); 1036 nc = f[i] - f[i - 1]; 1037 if (diff_format != D_IFDEF && ch != '\0') { 1038 diff_output("%c", ch); 1039 if (diff_format != D_UNIFIED) 1040 diff_output(" "); 1041 } 1042 col = 0; 1043 for (j = 0; j < nc; j++) { 1044 if ((c = getc(lb)) == EOF) { 1045 if (diff_format == D_RCSDIFF) 1046 warnx("No newline at end of file"); 1047 else 1048 diff_output("\n\\ No newline at end of " 1049 "file"); 1050 return; 1051 } 1052 if (c == '\t' && (flags & D_EXPANDTABS)) { 1053 do { 1054 diff_output(" "); 1055 } while (++col & 7); 1056 } else { 1057 diff_output("%c", c); 1058 col++; 1059 } 1060 } 1061 } 1062 } 1063 1064 /* 1065 * Hash function taken from Robert Sedgewick, Algorithms in C, 3d ed., p 578. 1066 */ 1067 static int 1068 readhash(FILE *f, int flags) 1069 { 1070 int i, t, space; 1071 int sum; 1072 1073 sum = 1; 1074 space = 0; 1075 if ((flags & (D_FOLDBLANKS|D_IGNOREBLANKS)) == 0) { 1076 if (flags & D_IGNORECASE) 1077 for (i = 0; (t = getc(f)) != '\n'; i++) { 1078 if (t == EOF) { 1079 if (i == 0) 1080 return (0); 1081 break; 1082 } 1083 sum = sum * 127 + chrtran[t]; 1084 } 1085 else 1086 for (i = 0; (t = getc(f)) != '\n'; i++) { 1087 if (t == EOF) { 1088 if (i == 0) 1089 return (0); 1090 break; 1091 } 1092 sum = sum * 127 + t; 1093 } 1094 } else { 1095 for (i = 0;;) { 1096 switch (t = getc(f)) { 1097 case '\t': 1098 case '\r': 1099 case '\v': 1100 case '\f': 1101 case ' ': 1102 space++; 1103 continue; 1104 default: 1105 if (space && (flags & D_IGNOREBLANKS) == 0) { 1106 i++; 1107 space = 0; 1108 } 1109 sum = sum * 127 + chrtran[t]; 1110 i++; 1111 continue; 1112 case EOF: 1113 if (i == 0) 1114 return (0); 1115 /* FALLTHROUGH */ 1116 case '\n': 1117 break; 1118 } 1119 break; 1120 } 1121 } 1122 /* 1123 * There is a remote possibility that we end up with a zero sum. 1124 * Zero is used as an EOF marker, so return 1 instead. 1125 */ 1126 return (sum == 0 ? 1 : sum); 1127 } 1128 1129 static int 1130 asciifile(FILE *f) 1131 { 1132 unsigned char buf[BUFSIZ]; 1133 size_t i, cnt; 1134 1135 if (f == NULL) 1136 return (1); 1137 1138 rewind(f); 1139 cnt = fread(buf, 1, sizeof(buf), f); 1140 for (i = 0; i < cnt; i++) 1141 if (!isprint(buf[i]) && !isspace(buf[i])) 1142 return (0); 1143 return (1); 1144 } 1145 1146 #define begins_with(s, pre) (strncmp(s, pre, sizeof(pre)-1) == 0) 1147 1148 static char * 1149 match_function(const long *f, int pos, FILE *fp) 1150 { 1151 unsigned char buf[FUNCTION_CONTEXT_SIZE]; 1152 size_t nc; 1153 int last = lastline; 1154 char *state = NULL; 1155 1156 lastline = pos; 1157 while (pos > last) { 1158 fseek(fp, f[pos - 1], SEEK_SET); 1159 nc = f[pos] - f[pos - 1]; 1160 if (nc >= sizeof(buf)) 1161 nc = sizeof(buf) - 1; 1162 nc = fread(buf, 1, nc, fp); 1163 if (nc > 0) { 1164 buf[nc] = '\0'; 1165 buf[strcspn(buf, "\n")] = '\0'; 1166 if (isalpha(buf[0]) || buf[0] == '_' || buf[0] == '$') { 1167 if (begins_with(buf, "private:")) { 1168 if (!state) 1169 state = " (private)"; 1170 } else if (begins_with(buf, "protected:")) { 1171 if (!state) 1172 state = " (protected)"; 1173 } else if (begins_with(buf, "public:")) { 1174 if (!state) 1175 state = " (public)"; 1176 } else { 1177 if (strlcpy(lastbuf, buf, 1178 sizeof(lastbuf)) >= sizeof(lastbuf)) 1179 errx(1, 1180 "match_function: strlcpy"); 1181 lastmatchline = pos; 1182 return lastbuf; 1183 } 1184 } 1185 } 1186 pos--; 1187 } 1188 return lastmatchline > 0 ? lastbuf : NULL; 1189 } 1190 1191 /* dump accumulated "context" diff changes */ 1192 static void 1193 dump_context_vec(FILE *f1, FILE *f2, int flags) 1194 { 1195 struct context_vec *cvp = context_vec_start; 1196 int lowa, upb, lowc, upd, do_output; 1197 int a, b, c, d; 1198 char ch, *f; 1199 1200 if (context_vec_start > context_vec_ptr) 1201 return; 1202 1203 b = d = 0; /* gcc */ 1204 lowa = MAX(1, cvp->a - diff_context); 1205 upb = MIN(len[0], context_vec_ptr->b + diff_context); 1206 lowc = MAX(1, cvp->c - diff_context); 1207 upd = MIN(len[1], context_vec_ptr->d + diff_context); 1208 1209 diff_output("***************"); 1210 if ((flags & D_PROTOTYPE)) { 1211 f = match_function(ixold, lowa-1, f1); 1212 if (f != NULL) 1213 diff_output(" %s", f); 1214 } 1215 diff_output("\n*** "); 1216 range(lowa, upb, ","); 1217 diff_output(" ****\n"); 1218 1219 /* 1220 * Output changes to the "old" file. The first loop suppresses 1221 * output if there were no changes to the "old" file (we'll see 1222 * the "old" lines as context in the "new" list). 1223 */ 1224 do_output = 0; 1225 for (; cvp <= context_vec_ptr; cvp++) 1226 if (cvp->a <= cvp->b) { 1227 cvp = context_vec_start; 1228 do_output++; 1229 break; 1230 } 1231 if (do_output) { 1232 while (cvp <= context_vec_ptr) { 1233 a = cvp->a; 1234 b = cvp->b; 1235 c = cvp->c; 1236 d = cvp->d; 1237 1238 if (a <= b && c <= d) 1239 ch = 'c'; 1240 else 1241 ch = (a <= b) ? 'd' : 'a'; 1242 1243 if (ch == 'a') 1244 fetch(ixold, lowa, b, f1, ' ', 0, flags); 1245 else { 1246 fetch(ixold, lowa, a - 1, f1, ' ', 0, flags); 1247 fetch(ixold, a, b, f1, 1248 ch == 'c' ? '!' : '-', 0, flags); 1249 } 1250 lowa = b + 1; 1251 cvp++; 1252 } 1253 fetch(ixold, b + 1, upb, f1, ' ', 0, flags); 1254 } 1255 /* output changes to the "new" file */ 1256 diff_output("--- "); 1257 range(lowc, upd, ","); 1258 diff_output(" ----\n"); 1259 1260 do_output = 0; 1261 for (cvp = context_vec_start; cvp <= context_vec_ptr; cvp++) 1262 if (cvp->c <= cvp->d) { 1263 cvp = context_vec_start; 1264 do_output++; 1265 break; 1266 } 1267 if (do_output) { 1268 while (cvp <= context_vec_ptr) { 1269 a = cvp->a; 1270 b = cvp->b; 1271 c = cvp->c; 1272 d = cvp->d; 1273 1274 if (a <= b && c <= d) 1275 ch = 'c'; 1276 else 1277 ch = (a <= b) ? 'd' : 'a'; 1278 1279 if (ch == 'd') 1280 fetch(ixnew, lowc, d, f2, ' ', 0, flags); 1281 else { 1282 fetch(ixnew, lowc, c - 1, f2, ' ', 0, flags); 1283 fetch(ixnew, c, d, f2, 1284 ch == 'c' ? '!' : '+', 0, flags); 1285 } 1286 lowc = d + 1; 1287 cvp++; 1288 } 1289 fetch(ixnew, d + 1, upd, f2, ' ', 0, flags); 1290 } 1291 context_vec_ptr = context_vec_start - 1; 1292 } 1293 1294 /* dump accumulated "unified" diff changes */ 1295 static void 1296 dump_unified_vec(FILE *f1, FILE *f2, int flags) 1297 { 1298 struct context_vec *cvp = context_vec_start; 1299 int lowa, upb, lowc, upd; 1300 int a, b, c, d; 1301 char ch, *f; 1302 1303 if (context_vec_start > context_vec_ptr) 1304 return; 1305 1306 b = d = 0; /* gcc */ 1307 lowa = MAX(1, cvp->a - diff_context); 1308 upb = MIN(len[0], context_vec_ptr->b + diff_context); 1309 lowc = MAX(1, cvp->c - diff_context); 1310 upd = MIN(len[1], context_vec_ptr->d + diff_context); 1311 1312 diff_output("@@ -"); 1313 uni_range(lowa, upb); 1314 diff_output(" +"); 1315 uni_range(lowc, upd); 1316 diff_output(" @@"); 1317 if ((flags & D_PROTOTYPE)) { 1318 f = match_function(ixold, lowa-1, f1); 1319 if (f != NULL) 1320 diff_output(" %s", f); 1321 } 1322 diff_output("\n"); 1323 1324 /* 1325 * Output changes in "unified" diff format--the old and new lines 1326 * are printed together. 1327 */ 1328 for (; cvp <= context_vec_ptr; cvp++) { 1329 a = cvp->a; 1330 b = cvp->b; 1331 c = cvp->c; 1332 d = cvp->d; 1333 1334 /* 1335 * c: both new and old changes 1336 * d: only changes in the old file 1337 * a: only changes in the new file 1338 */ 1339 if (a <= b && c <= d) 1340 ch = 'c'; 1341 else 1342 ch = (a <= b) ? 'd' : 'a'; 1343 1344 switch (ch) { 1345 case 'c': 1346 fetch(ixold, lowa, a - 1, f1, ' ', 0, flags); 1347 fetch(ixold, a, b, f1, '-', 0, flags); 1348 fetch(ixnew, c, d, f2, '+', 0, flags); 1349 break; 1350 case 'd': 1351 fetch(ixold, lowa, a - 1, f1, ' ', 0, flags); 1352 fetch(ixold, a, b, f1, '-', 0, flags); 1353 break; 1354 case 'a': 1355 fetch(ixnew, lowc, c - 1, f2, ' ', 0, flags); 1356 fetch(ixnew, c, d, f2, '+', 0, flags); 1357 break; 1358 } 1359 lowa = b + 1; 1360 lowc = d + 1; 1361 } 1362 fetch(ixnew, d + 1, upd, f2, ' ', 0, flags); 1363 1364 context_vec_ptr = context_vec_start - 1; 1365 } 1366 1367 void 1368 diff_output(const char *fmt, ...) 1369 { 1370 va_list vap; 1371 int i; 1372 char *str; 1373 1374 va_start(vap, fmt); 1375 i = vasprintf(&str, fmt, vap); 1376 va_end(vap); 1377 if (i == -1) 1378 err(1, "diff_output"); 1379 if (diffbuf != NULL) 1380 rcs_buf_append(diffbuf, str, strlen(str)); 1381 else 1382 printf("%s", str); 1383 xfree(str); 1384 } 1385