1 /* $OpenBSD: diff.c,v 1.18 2007/05/29 08:02:59 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 struct diff_arg { 169 char *rev1; 170 char *rev2; 171 char *date1; 172 char *date2; 173 }; 174 175 static void output(FILE *, FILE *, int); 176 static void check(FILE *, FILE *, int); 177 static void range(int, int, char *); 178 static void uni_range(int, int); 179 static void dump_context_vec(FILE *, FILE *, int); 180 static void dump_unified_vec(FILE *, FILE *, int); 181 static int prepare(int, FILE *, off_t, int); 182 static void prune(void); 183 static void equiv(struct line *, int, struct line *, int, int *); 184 static void unravel(int); 185 static void unsort(struct line *, int, int *); 186 static void change(FILE *, FILE *, int, int, int, int, int); 187 static void sort(struct line *, int); 188 static int ignoreline(char *); 189 static int asciifile(FILE *); 190 static void fetch(long *, int, int, FILE *, int, int, int); 191 static int newcand(int, int, int); 192 static int search(int *, int, int); 193 static int skipline(FILE *); 194 static int isqrt(int); 195 static int stone(int *, int, int *, int *, int); 196 static int readhash(FILE *, int); 197 static int files_differ(FILE *, FILE *); 198 static char *match_function(const long *, int, FILE *); 199 static char *preadline(int, size_t, off_t); 200 201 202 int diff_context = 3; 203 int diff_format = D_NORMAL; 204 char *diff_file = NULL; 205 RCSNUM *diff_rev1 = NULL; 206 RCSNUM *diff_rev2 = NULL; 207 char diffargs[512]; /* XXX */ 208 static struct stat stb1, stb2; 209 static char *ifdefname; 210 regex_t *diff_ignore_re; 211 212 static int *J; /* will be overlaid on class */ 213 static int *class; /* will be overlaid on file[0] */ 214 static int *klist; /* will be overlaid on file[0] after class */ 215 static int *member; /* will be overlaid on file[1] */ 216 static int clen; 217 static int inifdef; /* whether or not we are in a #ifdef block */ 218 static int diff_len[2]; 219 static int pref, suff; /* length of prefix and suffix */ 220 static int slen[2]; 221 static int anychange; 222 static long *ixnew; /* will be overlaid on file[1] */ 223 static long *ixold; /* will be overlaid on klist */ 224 static struct cand *clist; /* merely a free storage pot for candidates */ 225 static int clistlen; /* the length of clist */ 226 static struct line *sfile[2]; /* shortened by pruning common prefix/suffix */ 227 static u_char *chrtran; /* translation table for case-folding */ 228 static struct context_vec *context_vec_start; 229 static struct context_vec *context_vec_end; 230 static struct context_vec *context_vec_ptr; 231 232 #define FUNCTION_CONTEXT_SIZE 55 233 static char lastbuf[FUNCTION_CONTEXT_SIZE]; 234 static int lastline; 235 static int lastmatchline; 236 BUF *diffbuf = NULL; 237 238 /* 239 * chrtran points to one of 2 translation tables: cup2low if folding upper to 240 * lower case clow2low if not folding case 241 */ 242 u_char clow2low[256] = { 243 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 244 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 245 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20, 246 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b, 247 0x2c, 0x2d, 0x2e, 0x2f, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 248 0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, 0x40, 0x41, 249 0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49, 0x4a, 0x4b, 0x4c, 250 0x4d, 0x4e, 0x4f, 0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57, 251 0x58, 0x59, 0x5a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f, 0x60, 0x61, 0x62, 252 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 253 0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, 254 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x80, 0x81, 0x82, 0x83, 255 0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 256 0x8f, 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99, 257 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f, 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 258 0xa5, 0xa6, 0xa7, 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf, 259 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba, 260 0xbb, 0xbc, 0xbd, 0xbe, 0xbf, 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 261 0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, 0xd0, 262 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, 0xdb, 263 0xdc, 0xdd, 0xde, 0xdf, 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 264 0xe7, 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef, 0xf0, 0xf1, 265 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 266 0xfd, 0xfe, 0xff 267 }; 268 269 u_char cup2low[256] = { 270 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 271 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 272 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20, 273 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b, 274 0x2c, 0x2d, 0x2e, 0x2f, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 275 0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, 0x60, 0x61, 276 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 277 0x6d, 0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 278 0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x60, 0x61, 0x62, 279 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 280 0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, 281 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x80, 0x81, 0x82, 0x83, 282 0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 283 0x8f, 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99, 284 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f, 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 285 0xa5, 0xa6, 0xa7, 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf, 286 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba, 287 0xbb, 0xbc, 0xbd, 0xbe, 0xbf, 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 288 0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, 0xd0, 289 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, 0xdb, 290 0xdc, 0xdd, 0xde, 0xdf, 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 291 0xe7, 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef, 0xf0, 0xf1, 292 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 293 0xfd, 0xfe, 0xff 294 }; 295 296 int 297 rcs_diffreg(const char *file1, const char *file2, BUF *out, int flags) 298 { 299 FILE *f1, *f2; 300 int i, rval; 301 302 f1 = f2 = NULL; 303 rval = D_SAME; 304 anychange = 0; 305 lastline = 0; 306 lastmatchline = 0; 307 context_vec_ptr = context_vec_start - 1; 308 if (flags & D_IGNORECASE) 309 chrtran = cup2low; 310 else 311 chrtran = clow2low; 312 if (out != NULL) 313 diffbuf = out; 314 315 f1 = fopen(file1, "r"); 316 if (f1 == NULL) { 317 warn("%s", file1); 318 goto closem; 319 } 320 321 f2 = fopen(file2, "r"); 322 if (f2 == NULL) { 323 warn("%s", file2); 324 goto closem; 325 } 326 327 if (fstat(fileno(f1), &stb1) < 0) { 328 warn("%s", file1); 329 goto closem; 330 } 331 332 if (fstat(fileno(f2), &stb2) < 0) { 333 warn("%s", file2); 334 goto closem; 335 } 336 337 switch (files_differ(f1, f2)) { 338 case 1: 339 break; 340 case -1: 341 rval = D_ERROR; 342 /* FALLTHROUGH */ 343 case 0: 344 goto closem; 345 default: 346 errx(D_ERROR, "files_differ: invalid case"); 347 } 348 349 if ((flags & D_FORCEASCII) == 0 && 350 (!asciifile(f1) || !asciifile(f2))) { 351 rval = D_ERROR; 352 goto closem; 353 } 354 355 if (prepare(0, f1, stb1.st_size, flags) < 0 || 356 prepare(1, f2, stb2.st_size, flags) < 0) { 357 goto closem; 358 } 359 360 prune(); 361 sort(sfile[0], slen[0]); 362 sort(sfile[1], slen[1]); 363 364 member = (int *)file[1]; 365 equiv(sfile[0], slen[0], sfile[1], slen[1], member); 366 member = xrealloc(member, slen[1] + 2, sizeof(*member)); 367 368 class = (int *)file[0]; 369 unsort(sfile[0], slen[0], class); 370 class = xrealloc(class, slen[0] + 2, sizeof(*class)); 371 372 klist = xcalloc(slen[0] + 2, sizeof(*klist)); 373 clen = 0; 374 clistlen = 100; 375 clist = xcalloc(clistlen, sizeof(*clist)); 376 377 if ((i = stone(class, slen[0], member, klist, flags)) < 0) 378 goto closem; 379 380 xfree(member); 381 xfree(class); 382 383 J = xrealloc(J, diff_len[0] + 2, sizeof(*J)); 384 unravel(klist[i]); 385 xfree(clist); 386 xfree(klist); 387 388 ixold = xrealloc(ixold, diff_len[0] + 2, sizeof(*ixold)); 389 390 ixnew = xrealloc(ixnew, diff_len[1] + 2, sizeof(*ixnew)); 391 check(f1, f2, flags); 392 output(f1, f2, flags); 393 394 closem: 395 if (anychange == 1) { 396 if (rval == D_SAME) 397 rval = D_DIFFER; 398 } 399 if (f1 != NULL) 400 fclose(f1); 401 if (f2 != NULL) 402 fclose(f2); 403 404 return (rval); 405 } 406 407 /* 408 * Check to see if the given files differ. 409 * Returns 0 if they are the same, 1 if different, and -1 on error. 410 * XXX - could use code from cmp(1) [faster] 411 */ 412 static int 413 files_differ(FILE *f1, FILE *f2) 414 { 415 char buf1[BUFSIZ], buf2[BUFSIZ]; 416 size_t i, j; 417 418 if (stb1.st_size != stb2.st_size) 419 return (1); 420 for (;;) { 421 i = fread(buf1, 1, sizeof(buf1), f1); 422 j = fread(buf2, 1, sizeof(buf2), f2); 423 if (i != j) 424 return (1); 425 if (i == 0 && j == 0) { 426 if (ferror(f1) || ferror(f2)) 427 return (-1); 428 return (0); 429 } 430 if (memcmp(buf1, buf2, i) != 0) 431 return (1); 432 } 433 } 434 435 static int 436 prepare(int i, FILE *fd, off_t filesize, int flags) 437 { 438 struct line *p; 439 int j, h; 440 size_t sz; 441 442 rewind(fd); 443 444 sz = ((size_t)filesize <= SIZE_MAX ? (size_t)filesize : SIZE_MAX) / 25; 445 if (sz < 100) 446 sz = 100; 447 448 p = xcalloc(sz + 3, sizeof(*p)); 449 for (j = 0; (h = readhash(fd, flags));) { 450 if (j == (int)sz) { 451 sz = sz * 3 / 2; 452 p = xrealloc(p, sz + 3, sizeof(*p)); 453 } 454 p[++j].value = h; 455 } 456 diff_len[i] = j; 457 file[i] = p; 458 459 return (0); 460 } 461 462 static void 463 prune(void) 464 { 465 int i, j; 466 467 for (pref = 0; pref < diff_len[0] && pref < diff_len[1] && 468 file[0][pref + 1].value == file[1][pref + 1].value; 469 pref++) 470 ; 471 for (suff = 0; 472 (suff < diff_len[0] - pref) && (suff < diff_len[1] - pref) && 473 (file[0][diff_len[0] - suff].value == 474 file[1][diff_len[1] - suff].value); 475 suff++) 476 ; 477 for (j = 0; j < 2; j++) { 478 sfile[j] = file[j] + pref; 479 slen[j] = diff_len[j] - pref - suff; 480 for (i = 0; i <= slen[j]; i++) 481 sfile[j][i].serial = i; 482 } 483 } 484 485 static void 486 equiv(struct line *a, int n, struct line *b, int m, int *c) 487 { 488 int i, j; 489 490 i = j = 1; 491 while (i <= n && j <= m) { 492 if (a[i].value < b[j].value) 493 a[i++].value = 0; 494 else if (a[i].value == b[j].value) 495 a[i++].value = j; 496 else 497 j++; 498 } 499 while (i <= n) 500 a[i++].value = 0; 501 b[m + 1].value = 0; 502 j = 0; 503 while (++j <= m) { 504 c[j] = -b[j].serial; 505 while (b[j + 1].value == b[j].value) { 506 j++; 507 c[j] = b[j].serial; 508 } 509 } 510 c[j] = -1; 511 } 512 513 /* Code taken from ping.c */ 514 static int 515 isqrt(int n) 516 { 517 int y, x = 1; 518 519 if (n == 0) 520 return (0); 521 522 do { /* newton was a stinker */ 523 y = x; 524 x = n / x; 525 x += y; 526 x /= 2; 527 } while (x - y > 1 || x - y < -1); 528 529 return (x); 530 } 531 532 static int 533 stone(int *a, int n, int *b, int *c, int flags) 534 { 535 int ret; 536 int i, k, y, j, l; 537 int oldc, tc, oldl; 538 u_int numtries; 539 540 /* XXX move the isqrt() out of the macro to avoid multiple calls */ 541 const u_int bound = (flags & D_MINIMAL) ? UINT_MAX : 542 MAX(256, (u_int)isqrt(n)); 543 544 k = 0; 545 if ((ret = newcand(0, 0, 0)) < 0) 546 return (-1); 547 c[0] = ret; 548 for (i = 1; i <= n; i++) { 549 j = a[i]; 550 if (j == 0) 551 continue; 552 y = -b[j]; 553 oldl = 0; 554 oldc = c[0]; 555 numtries = 0; 556 do { 557 if (y <= clist[oldc].y) 558 continue; 559 l = search(c, k, y); 560 if (l != oldl + 1) 561 oldc = c[l - 1]; 562 if (l <= k) { 563 if (clist[c[l]].y <= y) 564 continue; 565 tc = c[l]; 566 if ((ret = newcand(i, y, oldc)) < 0) 567 return (-1); 568 c[l] = ret; 569 oldc = tc; 570 oldl = l; 571 numtries++; 572 } else { 573 if ((ret = newcand(i, y, oldc)) < 0) 574 return (-1); 575 c[l] = ret; 576 k++; 577 break; 578 } 579 } while ((y = b[++j]) > 0 && numtries < bound); 580 } 581 return (k); 582 } 583 584 static int 585 newcand(int x, int y, int pred) 586 { 587 struct cand *q; 588 589 if (clen == clistlen) { 590 clistlen = clistlen * 11 / 10; 591 clist = xrealloc(clist, clistlen, sizeof(*clist)); 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 ptrdiff_t offset = context_vec_ptr - context_vec_start; 932 max_context <<= 1; 933 context_vec_start = xrealloc(context_vec_start, 934 max_context, sizeof(*context_vec_start)); 935 context_vec_end = context_vec_start + max_context; 936 context_vec_ptr = context_vec_start + offset; 937 } 938 if (anychange == 0) { 939 /* 940 * Print the context/unidiff header first time through. 941 */ 942 t = localtime(&stb1.st_mtime); 943 (void)strftime(buf, sizeof(buf), 944 "%Y/%m/%d %H:%M:%S", t); 945 946 diff_output("%s %s %s", 947 diff_format == D_CONTEXT ? "***" : "---", diff_file, 948 buf); 949 950 if (diff_rev1 != NULL) { 951 rcsnum_tostr(diff_rev1, buf, sizeof(buf)); 952 diff_output("\t%s", buf); 953 } 954 955 printf("\n"); 956 957 t = localtime(&stb2.st_mtime); 958 (void)strftime(buf, sizeof(buf), 959 "%Y/%m/%d %H:%M:%S", t); 960 961 diff_output("%s %s %s", 962 diff_format == D_CONTEXT ? "---" : "+++", diff_file, 963 buf); 964 965 if (diff_rev2 != NULL) { 966 rcsnum_tostr(diff_rev2, buf, sizeof(buf)); 967 diff_output("\t%s", buf); 968 } 969 970 printf("\n"); 971 anychange = 1; 972 } else if (a > context_vec_ptr->b + (2 * diff_context) + 1 && 973 c > context_vec_ptr->d + (2 * diff_context) + 1) { 974 /* 975 * If this change is more than 'diff_context' lines 976 * from the previous change, dump the record and reset it. 977 */ 978 if (diff_format == D_CONTEXT) 979 dump_context_vec(f1, f2, flags); 980 else 981 dump_unified_vec(f1, f2, flags); 982 } 983 context_vec_ptr++; 984 context_vec_ptr->a = a; 985 context_vec_ptr->b = b; 986 context_vec_ptr->c = c; 987 context_vec_ptr->d = d; 988 return; 989 } 990 if (anychange == 0) 991 anychange = 1; 992 switch (diff_format) { 993 case D_BRIEF: 994 return; 995 case D_NORMAL: 996 range(a, b, ","); 997 diff_output("%c", a > b ? 'a' : c > d ? 'd' : 'c'); 998 if (diff_format == D_NORMAL) 999 range(c, d, ","); 1000 diff_output("\n"); 1001 break; 1002 case D_RCSDIFF: 1003 if (a > b) 1004 diff_output("a%d %d\n", b, d - c + 1); 1005 else { 1006 diff_output("d%d %d\n", a, b - a + 1); 1007 1008 if (!(c > d)) /* add changed lines */ 1009 diff_output("a%d %d\n", b, d - c + 1); 1010 } 1011 break; 1012 } 1013 if (diff_format == D_NORMAL || diff_format == D_IFDEF) { 1014 fetch(ixold, a, b, f1, '<', 1, flags); 1015 if (a <= b && c <= d && diff_format == D_NORMAL) 1016 diff_output("---\n"); 1017 } 1018 fetch(ixnew, c, d, f2, diff_format == D_NORMAL ? '>' : '\0', 0, flags); 1019 if (inifdef) { 1020 diff_output("#endif /* %s */\n", ifdefname); 1021 inifdef = 0; 1022 } 1023 } 1024 1025 static void 1026 fetch(long *f, int a, int b, FILE *lb, int ch, int oldfile, int flags) 1027 { 1028 long j, nc; 1029 int i, c, col; 1030 1031 /* 1032 * When doing #ifdef's, copy down to current line 1033 * if this is the first file, so that stuff makes it to output. 1034 */ 1035 if (diff_format == D_IFDEF && oldfile) { 1036 long curpos = ftell(lb); 1037 /* print through if append (a>b), else to (nb: 0 vs 1 orig) */ 1038 nc = f[a > b ? b : a - 1] - curpos; 1039 for (i = 0; i < nc; i++) 1040 diff_output("%c", getc(lb)); 1041 } 1042 if (a > b) 1043 return; 1044 if (diff_format == D_IFDEF) { 1045 if (inifdef) { 1046 diff_output("#else /* %s%s */\n", 1047 oldfile == 1 ? "!" : "", ifdefname); 1048 } else { 1049 if (oldfile) 1050 diff_output("#ifndef %s\n", ifdefname); 1051 else 1052 diff_output("#ifdef %s\n", ifdefname); 1053 } 1054 inifdef = 1 + oldfile; 1055 } 1056 for (i = a; i <= b; i++) { 1057 fseek(lb, f[i - 1], SEEK_SET); 1058 nc = f[i] - f[i - 1]; 1059 if (diff_format != D_IFDEF && ch != '\0') { 1060 diff_output("%c", ch); 1061 if (diff_format != D_UNIFIED) 1062 diff_output(" "); 1063 } 1064 col = 0; 1065 for (j = 0; j < nc; j++) { 1066 if ((c = getc(lb)) == EOF) { 1067 if (diff_format == D_RCSDIFF) 1068 warn("No newline at end of file"); 1069 else 1070 diff_output("\n\\ No newline at end of " 1071 "file"); 1072 return; 1073 } 1074 if (c == '\t' && (flags & D_EXPANDTABS)) { 1075 do { 1076 diff_output(" "); 1077 } while (++col & 7); 1078 } else { 1079 diff_output("%c", c); 1080 col++; 1081 } 1082 } 1083 } 1084 } 1085 1086 /* 1087 * Hash function taken from Robert Sedgewick, Algorithms in C, 3d ed., p 578. 1088 */ 1089 static int 1090 readhash(FILE *f, int flags) 1091 { 1092 int i, t, space; 1093 int sum; 1094 1095 sum = 1; 1096 space = 0; 1097 if ((flags & (D_FOLDBLANKS|D_IGNOREBLANKS)) == 0) { 1098 if (flags & D_IGNORECASE) 1099 for (i = 0; (t = getc(f)) != '\n'; i++) { 1100 if (t == EOF) { 1101 if (i == 0) 1102 return (0); 1103 break; 1104 } 1105 sum = sum * 127 + chrtran[t]; 1106 } 1107 else 1108 for (i = 0; (t = getc(f)) != '\n'; i++) { 1109 if (t == EOF) { 1110 if (i == 0) 1111 return (0); 1112 break; 1113 } 1114 sum = sum * 127 + t; 1115 } 1116 } else { 1117 for (i = 0;;) { 1118 switch (t = getc(f)) { 1119 case '\t': 1120 case ' ': 1121 space++; 1122 continue; 1123 default: 1124 if (space && (flags & D_IGNOREBLANKS) == 0) { 1125 i++; 1126 space = 0; 1127 } 1128 sum = sum * 127 + chrtran[t]; 1129 i++; 1130 continue; 1131 case EOF: 1132 if (i == 0) 1133 return (0); 1134 /* FALLTHROUGH */ 1135 case '\n': 1136 break; 1137 } 1138 break; 1139 } 1140 } 1141 /* 1142 * There is a remote possibility that we end up with a zero sum. 1143 * Zero is used as an EOF marker, so return 1 instead. 1144 */ 1145 return (sum == 0 ? 1 : sum); 1146 } 1147 1148 static int 1149 asciifile(FILE *f) 1150 { 1151 char buf[BUFSIZ]; 1152 size_t i, cnt; 1153 1154 if (f == NULL) 1155 return (1); 1156 1157 rewind(f); 1158 cnt = fread(buf, 1, sizeof(buf), f); 1159 for (i = 0; i < cnt; i++) 1160 if (!isprint(buf[i]) && !isspace(buf[i])) 1161 return (0); 1162 return (1); 1163 } 1164 1165 #define begins_with(s, pre) (strncmp(s, pre, sizeof(pre)-1) == 0) 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 char *state = NULL; 1175 1176 lastline = pos; 1177 while (pos > last) { 1178 fseek(fp, f[pos - 1], SEEK_SET); 1179 nc = f[pos] - f[pos - 1]; 1180 if (nc >= sizeof(buf)) 1181 nc = sizeof(buf) - 1; 1182 nc = fread(buf, 1, nc, fp); 1183 if (nc > 0) { 1184 buf[nc] = '\0'; 1185 p = strchr((const char *)buf, '\n'); 1186 if (p != NULL) 1187 *p = '\0'; 1188 if (isalpha(buf[0]) || buf[0] == '_' || buf[0] == '$') { 1189 if (begins_with(buf, "private:")) { 1190 if (!state) 1191 state = " (private)"; 1192 } else if (begins_with(buf, "protected:")) { 1193 if (!state) 1194 state = " (protected)"; 1195 } else if (begins_with(buf, "public:")) { 1196 if (!state) 1197 state = " (public)"; 1198 } else { 1199 if (strlcpy(lastbuf, (const char *)buf, 1200 sizeof(lastbuf)) >= sizeof(lastbuf)) 1201 errx(1, 1202 "match_function: strlcpy"); 1203 lastmatchline = pos; 1204 return lastbuf; 1205 } 1206 } 1207 } 1208 pos--; 1209 } 1210 return (lastmatchline > 0) ? lastbuf : NULL; 1211 } 1212 1213 1214 /* dump accumulated "context" diff changes */ 1215 static void 1216 dump_context_vec(FILE *f1, FILE *f2, int flags) 1217 { 1218 struct context_vec *cvp = context_vec_start; 1219 int lowa, upb, lowc, upd, do_output; 1220 int a, b, c, d; 1221 char ch, *f; 1222 1223 if (context_vec_start > context_vec_ptr) 1224 return; 1225 1226 b = d = 0; /* gcc */ 1227 lowa = MAX(1, cvp->a - diff_context); 1228 upb = MIN(diff_len[0], context_vec_ptr->b + diff_context); 1229 lowc = MAX(1, cvp->c - diff_context); 1230 upd = MIN(diff_len[1], context_vec_ptr->d + diff_context); 1231 1232 diff_output("***************"); 1233 if ((flags & D_PROTOTYPE)) { 1234 f = match_function(ixold, lowa - 1, f1); 1235 if (f != NULL) { 1236 diff_output(" "); 1237 diff_output("%s", f); 1238 } 1239 } 1240 diff_output("\n*** "); 1241 range(lowa, upb, ","); 1242 diff_output(" ****\n"); 1243 1244 /* 1245 * Output changes to the "old" file. The first loop suppresses 1246 * output if there were no changes to the "old" file (we'll see 1247 * the "old" lines as context in the "new" list). 1248 */ 1249 do_output = 0; 1250 for (; cvp <= context_vec_ptr; cvp++) 1251 if (cvp->a <= cvp->b) { 1252 cvp = context_vec_start; 1253 do_output++; 1254 break; 1255 } 1256 if (do_output != 0) { 1257 while (cvp <= context_vec_ptr) { 1258 a = cvp->a; 1259 b = cvp->b; 1260 c = cvp->c; 1261 d = cvp->d; 1262 1263 if (a <= b && c <= d) 1264 ch = 'c'; 1265 else 1266 ch = (a <= b) ? 'd' : 'a'; 1267 1268 if (ch == 'a') 1269 fetch(ixold, lowa, b, f1, ' ', 0, flags); 1270 else { 1271 fetch(ixold, lowa, a - 1, f1, ' ', 0, flags); 1272 fetch(ixold, a, b, f1, 1273 ch == 'c' ? '!' : '-', 0, flags); 1274 } 1275 lowa = b + 1; 1276 cvp++; 1277 } 1278 fetch(ixold, b + 1, upb, f1, ' ', 0, flags); 1279 } 1280 /* output changes to the "new" file */ 1281 diff_output("--- "); 1282 range(lowc, upd, ","); 1283 diff_output(" ----\n"); 1284 1285 do_output = 0; 1286 for (cvp = context_vec_start; cvp <= context_vec_ptr; cvp++) 1287 if (cvp->c <= cvp->d) { 1288 cvp = context_vec_start; 1289 do_output++; 1290 break; 1291 } 1292 if (do_output != 0) { 1293 while (cvp <= context_vec_ptr) { 1294 a = cvp->a; 1295 b = cvp->b; 1296 c = cvp->c; 1297 d = cvp->d; 1298 1299 if (a <= b && c <= d) 1300 ch = 'c'; 1301 else 1302 ch = (a <= b) ? 'd' : 'a'; 1303 1304 if (ch == 'd') 1305 fetch(ixnew, lowc, d, f2, ' ', 0, flags); 1306 else { 1307 fetch(ixnew, lowc, c - 1, f2, ' ', 0, flags); 1308 fetch(ixnew, c, d, f2, 1309 ch == 'c' ? '!' : '+', 0, flags); 1310 } 1311 lowc = d + 1; 1312 cvp++; 1313 } 1314 fetch(ixnew, d + 1, upd, f2, ' ', 0, flags); 1315 } 1316 context_vec_ptr = context_vec_start - 1; 1317 } 1318 1319 /* dump accumulated "unified" diff changes */ 1320 static void 1321 dump_unified_vec(FILE *f1, FILE *f2, int flags) 1322 { 1323 struct context_vec *cvp = context_vec_start; 1324 int lowa, upb, lowc, upd; 1325 int a, b, c, d; 1326 char ch, *f; 1327 1328 if (context_vec_start > context_vec_ptr) 1329 return; 1330 1331 b = d = 0; /* gcc */ 1332 lowa = MAX(1, cvp->a - diff_context); 1333 upb = MIN(diff_len[0], context_vec_ptr->b + diff_context); 1334 lowc = MAX(1, cvp->c - diff_context); 1335 upd = MIN(diff_len[1], context_vec_ptr->d + diff_context); 1336 1337 diff_output("@@ -"); 1338 uni_range(lowa, upb); 1339 diff_output(" +"); 1340 uni_range(lowc, upd); 1341 diff_output(" @@"); 1342 if ((flags & D_PROTOTYPE)) { 1343 f = match_function(ixold, lowa - 1, f1); 1344 if (f != NULL) { 1345 diff_output(" "); 1346 diff_output("%s", f); 1347 } 1348 } 1349 diff_output("\n"); 1350 1351 /* 1352 * Output changes in "unified" diff format--the old and new lines 1353 * are printed together. 1354 */ 1355 for (; cvp <= context_vec_ptr; cvp++) { 1356 a = cvp->a; 1357 b = cvp->b; 1358 c = cvp->c; 1359 d = cvp->d; 1360 1361 /* 1362 * c: both new and old changes 1363 * d: only changes in the old file 1364 * a: only changes in the new file 1365 */ 1366 if (a <= b && c <= d) 1367 ch = 'c'; 1368 else 1369 ch = (a <= b) ? 'd' : 'a'; 1370 1371 switch (ch) { 1372 case 'c': 1373 fetch(ixold, lowa, a - 1, f1, ' ', 0, flags); 1374 fetch(ixold, a, b, f1, '-', 0, flags); 1375 fetch(ixnew, c, d, f2, '+', 0, flags); 1376 break; 1377 case 'd': 1378 fetch(ixold, lowa, a - 1, f1, ' ', 0, flags); 1379 fetch(ixold, a, b, f1, '-', 0, flags); 1380 break; 1381 case 'a': 1382 fetch(ixnew, lowc, c - 1, f2, ' ', 0, flags); 1383 fetch(ixnew, c, d, f2, '+', 0, flags); 1384 break; 1385 } 1386 lowa = b + 1; 1387 lowc = d + 1; 1388 } 1389 fetch(ixnew, d + 1, upd, f2, ' ', 0, flags); 1390 1391 context_vec_ptr = context_vec_start - 1; 1392 } 1393 1394 void 1395 diff_output(const char *fmt, ...) 1396 { 1397 va_list vap; 1398 int i; 1399 char *str; 1400 1401 va_start(vap, fmt); 1402 i = vasprintf(&str, fmt, vap); 1403 va_end(vap); 1404 if (i == -1) 1405 err(1, "diff_output"); 1406 if (diffbuf != NULL) 1407 rcs_buf_append(diffbuf, str, strlen(str)); 1408 else 1409 printf("%s", str); 1410 xfree(str); 1411 } 1412