1 /* $OpenBSD: diff.c,v 1.19 2007/05/30 03:24:54 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 } cand; 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 int 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 diff_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 if (prepare(0, f1, stb1.st_size, flags) < 0 || 349 prepare(1, f2, stb2.st_size, flags) < 0) { 350 goto closem; 351 } 352 353 prune(); 354 sort(sfile[0], slen[0]); 355 sort(sfile[1], slen[1]); 356 357 member = (int *)file[1]; 358 equiv(sfile[0], slen[0], sfile[1], slen[1], member); 359 member = xrealloc(member, slen[1] + 2, sizeof(*member)); 360 361 class = (int *)file[0]; 362 unsort(sfile[0], slen[0], class); 363 class = xrealloc(class, slen[0] + 2, sizeof(*class)); 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 J = xrealloc(J, diff_len[0] + 2, sizeof(*J)); 377 unravel(klist[i]); 378 xfree(clist); 379 xfree(klist); 380 381 ixold = xrealloc(ixold, diff_len[0] + 2, sizeof(*ixold)); 382 383 ixnew = xrealloc(ixnew, diff_len[1] + 2, sizeof(*ixnew)); 384 check(f1, f2, flags); 385 output(f1, f2, flags); 386 387 closem: 388 if (anychange == 1) { 389 if (rval == D_SAME) 390 rval = D_DIFFER; 391 } 392 if (f1 != NULL) 393 fclose(f1); 394 if (f2 != NULL) 395 fclose(f2); 396 397 return (rval); 398 } 399 400 /* 401 * Check to see if the given files differ. 402 * Returns 0 if they are the same, 1 if different, and -1 on error. 403 * XXX - could use code from cmp(1) [faster] 404 */ 405 static int 406 files_differ(FILE *f1, FILE *f2) 407 { 408 char buf1[BUFSIZ], buf2[BUFSIZ]; 409 size_t i, j; 410 411 if (stb1.st_size != stb2.st_size) 412 return (1); 413 for (;;) { 414 i = fread(buf1, 1, sizeof(buf1), f1); 415 j = fread(buf2, 1, sizeof(buf2), f2); 416 if (i != j) 417 return (1); 418 if (i == 0 && j == 0) { 419 if (ferror(f1) || ferror(f2)) 420 return (-1); 421 return (0); 422 } 423 if (memcmp(buf1, buf2, i) != 0) 424 return (1); 425 } 426 } 427 428 static int 429 prepare(int i, FILE *fd, off_t filesize, int flags) 430 { 431 struct line *p; 432 int j, h; 433 size_t sz; 434 435 rewind(fd); 436 437 sz = ((size_t)filesize <= SIZE_MAX ? (size_t)filesize : SIZE_MAX) / 25; 438 if (sz < 100) 439 sz = 100; 440 441 p = xcalloc(sz + 3, sizeof(*p)); 442 for (j = 0; (h = readhash(fd, flags));) { 443 if (j == (int)sz) { 444 sz = sz * 3 / 2; 445 p = xrealloc(p, sz + 3, sizeof(*p)); 446 } 447 p[++j].value = h; 448 } 449 diff_len[i] = j; 450 file[i] = p; 451 452 return (0); 453 } 454 455 static void 456 prune(void) 457 { 458 int i, j; 459 460 for (pref = 0; pref < diff_len[0] && pref < diff_len[1] && 461 file[0][pref + 1].value == file[1][pref + 1].value; 462 pref++) 463 ; 464 for (suff = 0; 465 (suff < diff_len[0] - pref) && (suff < diff_len[1] - pref) && 466 (file[0][diff_len[0] - suff].value == 467 file[1][diff_len[1] - suff].value); 468 suff++) 469 ; 470 for (j = 0; j < 2; j++) { 471 sfile[j] = file[j] + pref; 472 slen[j] = diff_len[j] - pref - suff; 473 for (i = 0; i <= slen[j]; i++) 474 sfile[j][i].serial = i; 475 } 476 } 477 478 static void 479 equiv(struct line *a, int n, struct line *b, int m, int *c) 480 { 481 int i, j; 482 483 i = j = 1; 484 while (i <= n && j <= m) { 485 if (a[i].value < b[j].value) 486 a[i++].value = 0; 487 else if (a[i].value == b[j].value) 488 a[i++].value = j; 489 else 490 j++; 491 } 492 while (i <= n) 493 a[i++].value = 0; 494 b[m + 1].value = 0; 495 j = 0; 496 while (++j <= m) { 497 c[j] = -b[j].serial; 498 while (b[j + 1].value == b[j].value) { 499 j++; 500 c[j] = b[j].serial; 501 } 502 } 503 c[j] = -1; 504 } 505 506 /* Code taken from ping.c */ 507 static int 508 isqrt(int n) 509 { 510 int y, x = 1; 511 512 if (n == 0) 513 return (0); 514 515 do { /* newton was a stinker */ 516 y = x; 517 x = n / x; 518 x += y; 519 x /= 2; 520 } while (x - y > 1 || x - y < -1); 521 522 return (x); 523 } 524 525 static int 526 stone(int *a, int n, int *b, int *c, int flags) 527 { 528 int ret; 529 int i, k, y, j, l; 530 int oldc, tc, oldl; 531 u_int numtries; 532 533 /* XXX move the isqrt() out of the macro to avoid multiple calls */ 534 const u_int bound = (flags & D_MINIMAL) ? UINT_MAX : 535 MAX(256, (u_int)isqrt(n)); 536 537 k = 0; 538 if ((ret = newcand(0, 0, 0)) < 0) 539 return (-1); 540 c[0] = ret; 541 for (i = 1; i <= n; i++) { 542 j = a[i]; 543 if (j == 0) 544 continue; 545 y = -b[j]; 546 oldl = 0; 547 oldc = c[0]; 548 numtries = 0; 549 do { 550 if (y <= clist[oldc].y) 551 continue; 552 l = search(c, k, y); 553 if (l != oldl + 1) 554 oldc = c[l - 1]; 555 if (l <= k) { 556 if (clist[c[l]].y <= y) 557 continue; 558 tc = c[l]; 559 if ((ret = newcand(i, y, oldc)) < 0) 560 return (-1); 561 c[l] = ret; 562 oldc = tc; 563 oldl = l; 564 numtries++; 565 } else { 566 if ((ret = newcand(i, y, oldc)) < 0) 567 return (-1); 568 c[l] = ret; 569 k++; 570 break; 571 } 572 } while ((y = b[++j]) > 0 && numtries < bound); 573 } 574 return (k); 575 } 576 577 static int 578 newcand(int x, int y, int pred) 579 { 580 struct cand *q; 581 582 if (clen == clistlen) { 583 clistlen = clistlen * 11 / 10; 584 clist = xrealloc(clist, clistlen, sizeof(*clist)); 585 } 586 q = clist + clen; 587 q->x = x; 588 q->y = y; 589 q->pred = pred; 590 return (clen++); 591 } 592 593 static int 594 search(int *c, int k, int y) 595 { 596 int i, j, l, t; 597 598 if (clist[c[k]].y < y) /* quick look for typical case */ 599 return (k + 1); 600 i = 0; 601 j = k + 1; 602 for (;;) { 603 l = (i + j) / 2; 604 if (l <= i) 605 break; 606 t = clist[c[l]].y; 607 if (t > y) 608 j = l; 609 else if (t < y) 610 i = l; 611 else 612 return (l); 613 } 614 return (l + 1); 615 } 616 617 static void 618 unravel(int p) 619 { 620 struct cand *q; 621 int i; 622 623 for (i = 0; i <= diff_len[0]; i++) 624 J[i] = i <= pref ? i : 625 i > diff_len[0] - suff ? i + diff_len[1] - diff_len[0] : 0; 626 for (q = clist + p; q->y != 0; q = clist + q->pred) 627 J[q->x + pref] = q->y + pref; 628 } 629 630 /* 631 * Check does double duty: 632 * 1. ferret out any fortuitous correspondences due 633 * to confounding by hashing (which result in "jackpot") 634 * 2. collect random access indexes to the two files 635 */ 636 static void 637 check(FILE *f1, FILE *f2, int flags) 638 { 639 int i, j, jackpot, c, d; 640 long ctold, ctnew; 641 642 rewind(f1); 643 rewind(f2); 644 j = 1; 645 ixold[0] = ixnew[0] = 0; 646 jackpot = 0; 647 ctold = ctnew = 0; 648 for (i = 1; i <= diff_len[0]; i++) { 649 if (J[i] == 0) { 650 ixold[i] = ctold += skipline(f1); 651 continue; 652 } 653 while (j < J[i]) { 654 ixnew[j] = ctnew += skipline(f2); 655 j++; 656 } 657 if (flags & (D_FOLDBLANKS|D_IGNOREBLANKS|D_IGNORECASE)) { 658 for (;;) { 659 c = getc(f1); 660 d = getc(f2); 661 /* 662 * GNU diff ignores a missing newline 663 * in one file for -b or -w. 664 */ 665 if ((flags & (D_FOLDBLANKS|D_IGNOREBLANKS)) && 666 ((c == EOF && d == '\n') || 667 (c == '\n' && d == EOF))) { 668 break; 669 } 670 ctold++; 671 ctnew++; 672 if ((flags & D_FOLDBLANKS) && isspace(c) && 673 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 ((flags & D_IGNOREBLANKS)) { 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 * 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, int flags) 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, flags); 811 } 812 if (m == 0) 813 change(f1, f2, 1, 0, 1, diff_len[1], flags); 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, flags); 826 else if (diff_format == D_UNIFIED) 827 dump_unified_vec(f1, f2, flags); 828 } 829 } 830 831 static 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 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 warn("preadline failed"); 859 xfree(line); 860 return (NULL); 861 } 862 line[nr] = '\0'; 863 return (line); 864 } 865 866 static int 867 ignoreline(char *line) 868 { 869 int ret; 870 871 ret = regexec(diff_ignore_re, line, 0, NULL, 0); 872 xfree(line); 873 return (ret == 0); /* if it matched, it should be ignored. */ 874 } 875 876 /* 877 * Indicate that there is a difference between lines a and b of the from file 878 * to get to lines c to d of the to file. If a is greater then b then there 879 * are no lines in the from file involved and this means that there were 880 * lines appended (beginning at b). If c is greater than d then there are 881 * lines missing from the to file. 882 */ 883 static void 884 change(FILE *f1, FILE *f2, int a, int b, int c, int d, int flags) 885 { 886 int i; 887 static size_t max_context = 64; 888 char buf[64]; 889 struct tm *t; 890 891 if (diff_format != D_IFDEF && a > b && c > d) 892 return; 893 if (diff_ignore_re != NULL) { 894 char *line; 895 /* 896 * All lines in the change, insert, or delete must 897 * match an ignore pattern for the change to be 898 * ignored. 899 */ 900 if (a <= b) { /* Changes and deletes. */ 901 for (i = a; i <= b; i++) { 902 line = preadline(fileno(f1), 903 ixold[i] - ixold[i - 1], ixold[i - 1]); 904 if (!ignoreline(line)) 905 goto proceed; 906 } 907 } 908 if (a > b || c <= d) { /* Changes and inserts. */ 909 for (i = c; i <= d; i++) { 910 line = preadline(fileno(f2), 911 ixnew[i] - ixnew[i - 1], ixnew[i - 1]); 912 if (!ignoreline(line)) 913 goto proceed; 914 } 915 } 916 return; 917 } 918 proceed: 919 if (diff_format == D_CONTEXT || diff_format == D_UNIFIED) { 920 /* 921 * Allocate change records as needed. 922 */ 923 if (context_vec_ptr == context_vec_end - 1) { 924 ptrdiff_t offset = context_vec_ptr - context_vec_start; 925 max_context <<= 1; 926 context_vec_start = xrealloc(context_vec_start, 927 max_context, sizeof(*context_vec_start)); 928 context_vec_end = context_vec_start + max_context; 929 context_vec_ptr = context_vec_start + offset; 930 } 931 if (anychange == 0) { 932 /* 933 * Print the context/unidiff header first time through. 934 */ 935 t = localtime(&stb1.st_mtime); 936 (void)strftime(buf, sizeof(buf), 937 "%Y/%m/%d %H:%M:%S", t); 938 939 diff_output("%s %s %s", 940 diff_format == D_CONTEXT ? "***" : "---", diff_file, 941 buf); 942 943 if (diff_rev1 != NULL) { 944 rcsnum_tostr(diff_rev1, buf, sizeof(buf)); 945 diff_output("\t%s", buf); 946 } 947 948 printf("\n"); 949 950 t = localtime(&stb2.st_mtime); 951 (void)strftime(buf, sizeof(buf), 952 "%Y/%m/%d %H:%M:%S", t); 953 954 diff_output("%s %s %s", 955 diff_format == D_CONTEXT ? "---" : "+++", diff_file, 956 buf); 957 958 if (diff_rev2 != NULL) { 959 rcsnum_tostr(diff_rev2, buf, sizeof(buf)); 960 diff_output("\t%s", buf); 961 } 962 963 printf("\n"); 964 anychange = 1; 965 } else if (a > context_vec_ptr->b + (2 * diff_context) + 1 && 966 c > context_vec_ptr->d + (2 * diff_context) + 1) { 967 /* 968 * If this change is more than 'diff_context' lines 969 * from the previous change, dump the record and reset it. 970 */ 971 if (diff_format == D_CONTEXT) 972 dump_context_vec(f1, f2, flags); 973 else 974 dump_unified_vec(f1, f2, flags); 975 } 976 context_vec_ptr++; 977 context_vec_ptr->a = a; 978 context_vec_ptr->b = b; 979 context_vec_ptr->c = c; 980 context_vec_ptr->d = d; 981 return; 982 } 983 if (anychange == 0) 984 anychange = 1; 985 switch (diff_format) { 986 case D_BRIEF: 987 return; 988 case D_NORMAL: 989 range(a, b, ","); 990 diff_output("%c", a > b ? 'a' : c > d ? 'd' : 'c'); 991 if (diff_format == D_NORMAL) 992 range(c, d, ","); 993 diff_output("\n"); 994 break; 995 case D_RCSDIFF: 996 if (a > b) 997 diff_output("a%d %d\n", b, d - c + 1); 998 else { 999 diff_output("d%d %d\n", a, b - a + 1); 1000 1001 if (!(c > d)) /* add changed lines */ 1002 diff_output("a%d %d\n", b, d - c + 1); 1003 } 1004 break; 1005 } 1006 if (diff_format == D_NORMAL || diff_format == D_IFDEF) { 1007 fetch(ixold, a, b, f1, '<', 1, flags); 1008 if (a <= b && c <= d && diff_format == D_NORMAL) 1009 diff_output("---\n"); 1010 } 1011 fetch(ixnew, c, d, f2, diff_format == D_NORMAL ? '>' : '\0', 0, flags); 1012 if (inifdef) { 1013 diff_output("#endif /* %s */\n", ifdefname); 1014 inifdef = 0; 1015 } 1016 } 1017 1018 static void 1019 fetch(long *f, int a, int b, FILE *lb, int ch, int oldfile, int flags) 1020 { 1021 long j, nc; 1022 int i, c, col; 1023 1024 /* 1025 * When doing #ifdef's, copy down to current line 1026 * if this is the first file, so that stuff makes it to output. 1027 */ 1028 if (diff_format == D_IFDEF && oldfile) { 1029 long curpos = ftell(lb); 1030 /* print through if append (a>b), else to (nb: 0 vs 1 orig) */ 1031 nc = f[a > b ? b : a - 1] - curpos; 1032 for (i = 0; i < nc; i++) 1033 diff_output("%c", getc(lb)); 1034 } 1035 if (a > b) 1036 return; 1037 if (diff_format == D_IFDEF) { 1038 if (inifdef) { 1039 diff_output("#else /* %s%s */\n", 1040 oldfile == 1 ? "!" : "", ifdefname); 1041 } else { 1042 if (oldfile) 1043 diff_output("#ifndef %s\n", ifdefname); 1044 else 1045 diff_output("#ifdef %s\n", ifdefname); 1046 } 1047 inifdef = 1 + oldfile; 1048 } 1049 for (i = a; i <= b; i++) { 1050 fseek(lb, f[i - 1], SEEK_SET); 1051 nc = f[i] - f[i - 1]; 1052 if (diff_format != D_IFDEF && ch != '\0') { 1053 diff_output("%c", ch); 1054 if (diff_format != D_UNIFIED) 1055 diff_output(" "); 1056 } 1057 col = 0; 1058 for (j = 0; j < nc; j++) { 1059 if ((c = getc(lb)) == EOF) { 1060 if (diff_format == D_RCSDIFF) 1061 warn("No newline at end of file"); 1062 else 1063 diff_output("\n\\ No newline at end of " 1064 "file"); 1065 return; 1066 } 1067 if (c == '\t' && (flags & D_EXPANDTABS)) { 1068 do { 1069 diff_output(" "); 1070 } while (++col & 7); 1071 } else { 1072 diff_output("%c", c); 1073 col++; 1074 } 1075 } 1076 } 1077 } 1078 1079 /* 1080 * Hash function taken from Robert Sedgewick, Algorithms in C, 3d ed., p 578. 1081 */ 1082 static int 1083 readhash(FILE *f, int flags) 1084 { 1085 int i, t, space; 1086 int sum; 1087 1088 sum = 1; 1089 space = 0; 1090 if ((flags & (D_FOLDBLANKS|D_IGNOREBLANKS)) == 0) { 1091 if (flags & D_IGNORECASE) 1092 for (i = 0; (t = getc(f)) != '\n'; i++) { 1093 if (t == EOF) { 1094 if (i == 0) 1095 return (0); 1096 break; 1097 } 1098 sum = sum * 127 + chrtran[t]; 1099 } 1100 else 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 + t; 1108 } 1109 } else { 1110 for (i = 0;;) { 1111 switch (t = getc(f)) { 1112 case '\t': 1113 case ' ': 1114 space++; 1115 continue; 1116 default: 1117 if (space && (flags & D_IGNOREBLANKS) == 0) { 1118 i++; 1119 space = 0; 1120 } 1121 sum = sum * 127 + chrtran[t]; 1122 i++; 1123 continue; 1124 case EOF: 1125 if (i == 0) 1126 return (0); 1127 /* FALLTHROUGH */ 1128 case '\n': 1129 break; 1130 } 1131 break; 1132 } 1133 } 1134 /* 1135 * There is a remote possibility that we end up with a zero sum. 1136 * Zero is used as an EOF marker, so return 1 instead. 1137 */ 1138 return (sum == 0 ? 1 : sum); 1139 } 1140 1141 static int 1142 asciifile(FILE *f) 1143 { 1144 char buf[BUFSIZ]; 1145 size_t i, cnt; 1146 1147 if (f == NULL) 1148 return (1); 1149 1150 rewind(f); 1151 cnt = fread(buf, 1, sizeof(buf), f); 1152 for (i = 0; i < cnt; i++) 1153 if (!isprint(buf[i]) && !isspace(buf[i])) 1154 return (0); 1155 return (1); 1156 } 1157 1158 #define begins_with(s, pre) (strncmp(s, pre, sizeof(pre)-1) == 0) 1159 1160 static char* 1161 match_function(const long *f, int pos, FILE *fp) 1162 { 1163 unsigned char buf[FUNCTION_CONTEXT_SIZE]; 1164 size_t nc; 1165 int last = lastline; 1166 char *p; 1167 char *state = NULL; 1168 1169 lastline = pos; 1170 while (pos > last) { 1171 fseek(fp, f[pos - 1], SEEK_SET); 1172 nc = f[pos] - f[pos - 1]; 1173 if (nc >= sizeof(buf)) 1174 nc = sizeof(buf) - 1; 1175 nc = fread(buf, 1, nc, fp); 1176 if (nc > 0) { 1177 buf[nc] = '\0'; 1178 p = strchr((const char *)buf, '\n'); 1179 if (p != NULL) 1180 *p = '\0'; 1181 if (isalpha(buf[0]) || buf[0] == '_' || buf[0] == '$') { 1182 if (begins_with(buf, "private:")) { 1183 if (!state) 1184 state = " (private)"; 1185 } else if (begins_with(buf, "protected:")) { 1186 if (!state) 1187 state = " (protected)"; 1188 } else if (begins_with(buf, "public:")) { 1189 if (!state) 1190 state = " (public)"; 1191 } else { 1192 if (strlcpy(lastbuf, (const char *)buf, 1193 sizeof(lastbuf)) >= sizeof(lastbuf)) 1194 errx(1, 1195 "match_function: strlcpy"); 1196 lastmatchline = pos; 1197 return lastbuf; 1198 } 1199 } 1200 } 1201 pos--; 1202 } 1203 return (lastmatchline > 0) ? lastbuf : NULL; 1204 } 1205 1206 1207 /* dump accumulated "context" diff changes */ 1208 static void 1209 dump_context_vec(FILE *f1, FILE *f2, int flags) 1210 { 1211 struct context_vec *cvp = context_vec_start; 1212 int lowa, upb, lowc, upd, do_output; 1213 int a, b, c, d; 1214 char ch, *f; 1215 1216 if (context_vec_start > context_vec_ptr) 1217 return; 1218 1219 b = d = 0; /* gcc */ 1220 lowa = MAX(1, cvp->a - diff_context); 1221 upb = MIN(diff_len[0], context_vec_ptr->b + diff_context); 1222 lowc = MAX(1, cvp->c - diff_context); 1223 upd = MIN(diff_len[1], context_vec_ptr->d + diff_context); 1224 1225 diff_output("***************"); 1226 if ((flags & D_PROTOTYPE)) { 1227 f = match_function(ixold, lowa - 1, f1); 1228 if (f != NULL) { 1229 diff_output(" "); 1230 diff_output("%s", f); 1231 } 1232 } 1233 diff_output("\n*** "); 1234 range(lowa, upb, ","); 1235 diff_output(" ****\n"); 1236 1237 /* 1238 * Output changes to the "old" file. The first loop suppresses 1239 * output if there were no changes to the "old" file (we'll see 1240 * the "old" lines as context in the "new" list). 1241 */ 1242 do_output = 0; 1243 for (; cvp <= context_vec_ptr; cvp++) 1244 if (cvp->a <= cvp->b) { 1245 cvp = context_vec_start; 1246 do_output++; 1247 break; 1248 } 1249 if (do_output != 0) { 1250 while (cvp <= context_vec_ptr) { 1251 a = cvp->a; 1252 b = cvp->b; 1253 c = cvp->c; 1254 d = cvp->d; 1255 1256 if (a <= b && c <= d) 1257 ch = 'c'; 1258 else 1259 ch = (a <= b) ? 'd' : 'a'; 1260 1261 if (ch == 'a') 1262 fetch(ixold, lowa, b, f1, ' ', 0, flags); 1263 else { 1264 fetch(ixold, lowa, a - 1, f1, ' ', 0, flags); 1265 fetch(ixold, a, b, f1, 1266 ch == 'c' ? '!' : '-', 0, flags); 1267 } 1268 lowa = b + 1; 1269 cvp++; 1270 } 1271 fetch(ixold, b + 1, upb, f1, ' ', 0, flags); 1272 } 1273 /* output changes to the "new" file */ 1274 diff_output("--- "); 1275 range(lowc, upd, ","); 1276 diff_output(" ----\n"); 1277 1278 do_output = 0; 1279 for (cvp = context_vec_start; cvp <= context_vec_ptr; cvp++) 1280 if (cvp->c <= cvp->d) { 1281 cvp = context_vec_start; 1282 do_output++; 1283 break; 1284 } 1285 if (do_output != 0) { 1286 while (cvp <= context_vec_ptr) { 1287 a = cvp->a; 1288 b = cvp->b; 1289 c = cvp->c; 1290 d = cvp->d; 1291 1292 if (a <= b && c <= d) 1293 ch = 'c'; 1294 else 1295 ch = (a <= b) ? 'd' : 'a'; 1296 1297 if (ch == 'd') 1298 fetch(ixnew, lowc, d, f2, ' ', 0, flags); 1299 else { 1300 fetch(ixnew, lowc, c - 1, f2, ' ', 0, flags); 1301 fetch(ixnew, c, d, f2, 1302 ch == 'c' ? '!' : '+', 0, flags); 1303 } 1304 lowc = d + 1; 1305 cvp++; 1306 } 1307 fetch(ixnew, d + 1, upd, f2, ' ', 0, flags); 1308 } 1309 context_vec_ptr = context_vec_start - 1; 1310 } 1311 1312 /* dump accumulated "unified" diff changes */ 1313 static void 1314 dump_unified_vec(FILE *f1, FILE *f2, int flags) 1315 { 1316 struct context_vec *cvp = context_vec_start; 1317 int lowa, upb, lowc, upd; 1318 int a, b, c, d; 1319 char ch, *f; 1320 1321 if (context_vec_start > context_vec_ptr) 1322 return; 1323 1324 b = d = 0; /* gcc */ 1325 lowa = MAX(1, cvp->a - diff_context); 1326 upb = MIN(diff_len[0], context_vec_ptr->b + diff_context); 1327 lowc = MAX(1, cvp->c - diff_context); 1328 upd = MIN(diff_len[1], context_vec_ptr->d + diff_context); 1329 1330 diff_output("@@ -"); 1331 uni_range(lowa, upb); 1332 diff_output(" +"); 1333 uni_range(lowc, upd); 1334 diff_output(" @@"); 1335 if ((flags & D_PROTOTYPE)) { 1336 f = match_function(ixold, lowa - 1, f1); 1337 if (f != NULL) { 1338 diff_output(" "); 1339 diff_output("%s", f); 1340 } 1341 } 1342 diff_output("\n"); 1343 1344 /* 1345 * Output changes in "unified" diff format--the old and new lines 1346 * are printed together. 1347 */ 1348 for (; cvp <= context_vec_ptr; cvp++) { 1349 a = cvp->a; 1350 b = cvp->b; 1351 c = cvp->c; 1352 d = cvp->d; 1353 1354 /* 1355 * c: both new and old changes 1356 * d: only changes in the old file 1357 * a: only changes in the new file 1358 */ 1359 if (a <= b && c <= d) 1360 ch = 'c'; 1361 else 1362 ch = (a <= b) ? 'd' : 'a'; 1363 1364 switch (ch) { 1365 case 'c': 1366 fetch(ixold, lowa, a - 1, f1, ' ', 0, flags); 1367 fetch(ixold, a, b, f1, '-', 0, flags); 1368 fetch(ixnew, c, d, f2, '+', 0, flags); 1369 break; 1370 case 'd': 1371 fetch(ixold, lowa, a - 1, f1, ' ', 0, flags); 1372 fetch(ixold, a, b, f1, '-', 0, flags); 1373 break; 1374 case 'a': 1375 fetch(ixnew, lowc, c - 1, f2, ' ', 0, flags); 1376 fetch(ixnew, c, d, f2, '+', 0, flags); 1377 break; 1378 } 1379 lowa = b + 1; 1380 lowc = d + 1; 1381 } 1382 fetch(ixnew, d + 1, upd, f2, ' ', 0, flags); 1383 1384 context_vec_ptr = context_vec_start - 1; 1385 } 1386 1387 void 1388 diff_output(const char *fmt, ...) 1389 { 1390 va_list vap; 1391 int i; 1392 char *str; 1393 1394 va_start(vap, fmt); 1395 i = vasprintf(&str, fmt, vap); 1396 va_end(vap); 1397 if (i == -1) 1398 err(1, "diff_output"); 1399 if (diffbuf != NULL) 1400 rcs_buf_append(diffbuf, str, strlen(str)); 1401 else 1402 printf("%s", str); 1403 xfree(str); 1404 } 1405