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