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