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