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