1 /* $OpenBSD: diff.c,v 1.17 2007/05/29 00:19:10 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 int newclistlen; 589 590 if (clen == clistlen) { 591 newclistlen = clistlen * 11 / 10; 592 clist = xrealloc(clist, newclistlen, sizeof(*clist)); 593 clistlen = newclistlen; 594 } 595 q = clist + clen; 596 q->x = x; 597 q->y = y; 598 q->pred = pred; 599 return (clen++); 600 } 601 602 static int 603 search(int *c, int k, int y) 604 { 605 int i, j, l, t; 606 607 if (clist[c[k]].y < y) /* quick look for typical case */ 608 return (k + 1); 609 i = 0; 610 j = k + 1; 611 for (;;) { 612 l = (i + j) / 2; 613 if (l <= i) 614 break; 615 t = clist[c[l]].y; 616 if (t > y) 617 j = l; 618 else if (t < y) 619 i = l; 620 else 621 return (l); 622 } 623 return (l + 1); 624 } 625 626 static void 627 unravel(int p) 628 { 629 struct cand *q; 630 int i; 631 632 for (i = 0; i <= diff_len[0]; i++) 633 J[i] = i <= pref ? i : 634 i > diff_len[0] - suff ? i + diff_len[1] - diff_len[0] : 0; 635 for (q = clist + p; q->y != 0; q = clist + q->pred) 636 J[q->x + pref] = q->y + pref; 637 } 638 639 /* 640 * Check does double duty: 641 * 1. ferret out any fortuitous correspondences due 642 * to confounding by hashing (which result in "jackpot") 643 * 2. collect random access indexes to the two files 644 */ 645 static void 646 check(FILE *f1, FILE *f2, int flags) 647 { 648 int i, j, jackpot, c, d; 649 long ctold, ctnew; 650 651 rewind(f1); 652 rewind(f2); 653 j = 1; 654 ixold[0] = ixnew[0] = 0; 655 jackpot = 0; 656 ctold = ctnew = 0; 657 for (i = 1; i <= diff_len[0]; i++) { 658 if (J[i] == 0) { 659 ixold[i] = ctold += skipline(f1); 660 continue; 661 } 662 while (j < J[i]) { 663 ixnew[j] = ctnew += skipline(f2); 664 j++; 665 } 666 if (flags & (D_FOLDBLANKS|D_IGNOREBLANKS|D_IGNORECASE)) { 667 for (;;) { 668 c = getc(f1); 669 d = getc(f2); 670 /* 671 * GNU diff ignores a missing newline 672 * in one file for -b or -w. 673 */ 674 if ((flags & (D_FOLDBLANKS|D_IGNOREBLANKS)) && 675 ((c == EOF && d == '\n') || 676 (c == '\n' && d == EOF))) { 677 break; 678 } 679 ctold++; 680 ctnew++; 681 if ((flags & D_FOLDBLANKS) && isspace(c) && 682 isspace(d)) { 683 do { 684 if (c == '\n') 685 break; 686 ctold++; 687 } while (isspace(c = getc(f1))); 688 do { 689 if (d == '\n') 690 break; 691 ctnew++; 692 } while (isspace(d = getc(f2))); 693 } else if ((flags & D_IGNOREBLANKS)) { 694 while (isspace(c) && c != '\n') { 695 c = getc(f1); 696 ctold++; 697 } 698 while (isspace(d) && d != '\n') { 699 d = getc(f2); 700 ctnew++; 701 } 702 } 703 if (chrtran[c] != chrtran[d]) { 704 jackpot++; 705 J[i] = 0; 706 if (c != '\n' && c != EOF) 707 ctold += skipline(f1); 708 if (d != '\n' && c != EOF) 709 ctnew += skipline(f2); 710 break; 711 } 712 if (c == '\n' || c == EOF) 713 break; 714 } 715 } else { 716 for (;;) { 717 ctold++; 718 ctnew++; 719 if ((c = getc(f1)) != (d = getc(f2))) { 720 /* jackpot++; */ 721 J[i] = 0; 722 if (c != '\n' && c != EOF) 723 ctold += skipline(f1); 724 if (d != '\n' && c != EOF) 725 ctnew += skipline(f2); 726 break; 727 } 728 if (c == '\n' || c == EOF) 729 break; 730 } 731 } 732 ixold[i] = ctold; 733 ixnew[j] = ctnew; 734 j++; 735 } 736 for (; j <= diff_len[1]; j++) 737 ixnew[j] = ctnew += skipline(f2); 738 /* 739 * if (jackpot != 0) 740 * printf("jackpot\n"); 741 */ 742 } 743 744 /* shellsort CACM #201 */ 745 static void 746 sort(struct line *a, int n) 747 { 748 struct line *ai, *aim, w; 749 int j, m = 0, k; 750 751 if (n == 0) 752 return; 753 for (j = 1; j <= n; j *= 2) 754 m = 2 * j - 1; 755 for (m /= 2; m != 0; m /= 2) { 756 k = n - m; 757 for (j = 1; j <= k; j++) { 758 for (ai = &a[j]; ai > a; ai -= m) { 759 aim = &ai[m]; 760 if (aim < ai) 761 break; /* wraparound */ 762 if (aim->value > ai[0].value || 763 (aim->value == ai[0].value && 764 aim->serial > ai[0].serial)) 765 break; 766 w.value = ai[0].value; 767 ai[0].value = aim->value; 768 aim->value = w.value; 769 w.serial = ai[0].serial; 770 ai[0].serial = aim->serial; 771 aim->serial = w.serial; 772 } 773 } 774 } 775 } 776 777 static void 778 unsort(struct line *f, int l, int *b) 779 { 780 int *a, i; 781 782 a = xcalloc(l + 1, sizeof(*a)); 783 for (i = 1; i <= l; i++) 784 a[f[i].serial] = f[i].value; 785 for (i = 1; i <= l; i++) 786 b[i] = a[i]; 787 xfree(a); 788 } 789 790 static int 791 skipline(FILE *f) 792 { 793 int i, c; 794 795 for (i = 1; (c = getc(f)) != '\n' && c != EOF; i++) 796 continue; 797 return (i); 798 } 799 800 static void 801 output(FILE *f1, FILE *f2, int flags) 802 { 803 int m, i0, i1, j0, j1; 804 805 rewind(f1); 806 rewind(f2); 807 m = diff_len[0]; 808 J[0] = 0; 809 J[m + 1] = diff_len[1] + 1; 810 for (i0 = 1; i0 <= m; i0 = i1 + 1) { 811 while (i0 <= m && J[i0] == J[i0 - 1] + 1) 812 i0++; 813 j0 = J[i0 - 1] + 1; 814 i1 = i0 - 1; 815 while (i1 < m && J[i1 + 1] == 0) 816 i1++; 817 j1 = J[i1 + 1] - 1; 818 J[i1] = j1; 819 change(f1, f2, i0, i1, j0, j1, flags); 820 } 821 if (m == 0) 822 change(f1, f2, 1, 0, 1, diff_len[1], flags); 823 if (diff_format == D_IFDEF) { 824 for (;;) { 825 #define c i0 826 if ((c = getc(f1)) == EOF) 827 return; 828 diff_output("%c", c); 829 } 830 #undef c 831 } 832 if (anychange != 0) { 833 if (diff_format == D_CONTEXT) 834 dump_context_vec(f1, f2, flags); 835 else if (diff_format == D_UNIFIED) 836 dump_unified_vec(f1, f2, flags); 837 } 838 } 839 840 static void 841 range(int a, int b, char *separator) 842 { 843 diff_output("%d", a > b ? b : a); 844 if (a < b) 845 diff_output("%s%d", separator, b); 846 } 847 848 static void 849 uni_range(int a, int b) 850 { 851 if (a < b) 852 diff_output("%d,%d", a, b - a + 1); 853 else if (a == b) 854 diff_output("%d", b); 855 else 856 diff_output("%d,0", b); 857 } 858 859 static char * 860 preadline(int fd, size_t rlen, off_t off) 861 { 862 char *line; 863 ssize_t nr; 864 865 line = xmalloc(rlen + 1); 866 if ((nr = pread(fd, line, rlen, off)) < 0) { 867 warn("preadline failed"); 868 xfree(line); 869 return (NULL); 870 } 871 line[nr] = '\0'; 872 return (line); 873 } 874 875 static int 876 ignoreline(char *line) 877 { 878 int ret; 879 880 ret = regexec(diff_ignore_re, line, 0, NULL, 0); 881 xfree(line); 882 return (ret == 0); /* if it matched, it should be ignored. */ 883 } 884 885 /* 886 * Indicate that there is a difference between lines a and b of the from file 887 * to get to lines c to d of the to file. If a is greater then b then there 888 * are no lines in the from file involved and this means that there were 889 * lines appended (beginning at b). If c is greater than d then there are 890 * lines missing from the to file. 891 */ 892 static void 893 change(FILE *f1, FILE *f2, int a, int b, int c, int d, int flags) 894 { 895 int i; 896 static size_t max_context = 64; 897 char buf[64]; 898 struct tm *t; 899 900 if (diff_format != D_IFDEF && a > b && c > d) 901 return; 902 if (diff_ignore_re != NULL) { 903 char *line; 904 /* 905 * All lines in the change, insert, or delete must 906 * match an ignore pattern for the change to be 907 * ignored. 908 */ 909 if (a <= b) { /* Changes and deletes. */ 910 for (i = a; i <= b; i++) { 911 line = preadline(fileno(f1), 912 ixold[i] - ixold[i - 1], ixold[i - 1]); 913 if (!ignoreline(line)) 914 goto proceed; 915 } 916 } 917 if (a > b || c <= d) { /* Changes and inserts. */ 918 for (i = c; i <= d; i++) { 919 line = preadline(fileno(f2), 920 ixnew[i] - ixnew[i - 1], ixnew[i - 1]); 921 if (!ignoreline(line)) 922 goto proceed; 923 } 924 } 925 return; 926 } 927 proceed: 928 if (diff_format == D_CONTEXT || diff_format == D_UNIFIED) { 929 /* 930 * Allocate change records as needed. 931 */ 932 if (context_vec_ptr == context_vec_end - 1) { 933 ptrdiff_t offset = context_vec_ptr - context_vec_start; 934 max_context <<= 1; 935 context_vec_start = xrealloc(context_vec_start, 936 max_context, sizeof(*context_vec_start)); 937 context_vec_end = context_vec_start + max_context; 938 context_vec_ptr = context_vec_start + offset; 939 } 940 if (anychange == 0) { 941 /* 942 * Print the context/unidiff header first time through. 943 */ 944 t = localtime(&stb1.st_mtime); 945 (void)strftime(buf, sizeof(buf), 946 "%Y/%m/%d %H:%M:%S", t); 947 948 diff_output("%s %s %s", 949 diff_format == D_CONTEXT ? "***" : "---", diff_file, 950 buf); 951 952 if (diff_rev1 != NULL) { 953 rcsnum_tostr(diff_rev1, buf, sizeof(buf)); 954 diff_output("\t%s", buf); 955 } 956 957 printf("\n"); 958 959 t = localtime(&stb2.st_mtime); 960 (void)strftime(buf, sizeof(buf), 961 "%Y/%m/%d %H:%M:%S", t); 962 963 diff_output("%s %s %s", 964 diff_format == D_CONTEXT ? "---" : "+++", diff_file, 965 buf); 966 967 if (diff_rev2 != NULL) { 968 rcsnum_tostr(diff_rev2, buf, sizeof(buf)); 969 diff_output("\t%s", buf); 970 } 971 972 printf("\n"); 973 anychange = 1; 974 } else if (a > context_vec_ptr->b + (2 * diff_context) + 1 && 975 c > context_vec_ptr->d + (2 * diff_context) + 1) { 976 /* 977 * If this change is more than 'diff_context' lines 978 * from the previous change, dump the record and reset it. 979 */ 980 if (diff_format == D_CONTEXT) 981 dump_context_vec(f1, f2, flags); 982 else 983 dump_unified_vec(f1, f2, flags); 984 } 985 context_vec_ptr++; 986 context_vec_ptr->a = a; 987 context_vec_ptr->b = b; 988 context_vec_ptr->c = c; 989 context_vec_ptr->d = d; 990 return; 991 } 992 if (anychange == 0) 993 anychange = 1; 994 switch (diff_format) { 995 case D_BRIEF: 996 return; 997 case D_NORMAL: 998 range(a, b, ","); 999 diff_output("%c", a > b ? 'a' : c > d ? 'd' : 'c'); 1000 if (diff_format == D_NORMAL) 1001 range(c, d, ","); 1002 diff_output("\n"); 1003 break; 1004 case D_RCSDIFF: 1005 if (a > b) 1006 diff_output("a%d %d\n", b, d - c + 1); 1007 else { 1008 diff_output("d%d %d\n", a, b - a + 1); 1009 1010 if (!(c > d)) /* add changed lines */ 1011 diff_output("a%d %d\n", b, d - c + 1); 1012 } 1013 break; 1014 } 1015 if (diff_format == D_NORMAL || diff_format == D_IFDEF) { 1016 fetch(ixold, a, b, f1, '<', 1, flags); 1017 if (a <= b && c <= d && diff_format == D_NORMAL) 1018 diff_output("---\n"); 1019 } 1020 fetch(ixnew, c, d, f2, diff_format == D_NORMAL ? '>' : '\0', 0, flags); 1021 if (inifdef) { 1022 diff_output("#endif /* %s */\n", ifdefname); 1023 inifdef = 0; 1024 } 1025 } 1026 1027 static void 1028 fetch(long *f, int a, int b, FILE *lb, int ch, int oldfile, int flags) 1029 { 1030 long j, nc; 1031 int i, c, col; 1032 1033 /* 1034 * When doing #ifdef's, copy down to current line 1035 * if this is the first file, so that stuff makes it to output. 1036 */ 1037 if (diff_format == D_IFDEF && oldfile) { 1038 long curpos = ftell(lb); 1039 /* print through if append (a>b), else to (nb: 0 vs 1 orig) */ 1040 nc = f[a > b ? b : a - 1] - curpos; 1041 for (i = 0; i < nc; i++) 1042 diff_output("%c", getc(lb)); 1043 } 1044 if (a > b) 1045 return; 1046 if (diff_format == D_IFDEF) { 1047 if (inifdef) { 1048 diff_output("#else /* %s%s */\n", 1049 oldfile == 1 ? "!" : "", ifdefname); 1050 } else { 1051 if (oldfile) 1052 diff_output("#ifndef %s\n", ifdefname); 1053 else 1054 diff_output("#ifdef %s\n", ifdefname); 1055 } 1056 inifdef = 1 + oldfile; 1057 } 1058 for (i = a; i <= b; i++) { 1059 fseek(lb, f[i - 1], SEEK_SET); 1060 nc = f[i] - f[i - 1]; 1061 if (diff_format != D_IFDEF && ch != '\0') { 1062 diff_output("%c", ch); 1063 if (diff_format != D_UNIFIED) 1064 diff_output(" "); 1065 } 1066 col = 0; 1067 for (j = 0; j < nc; j++) { 1068 if ((c = getc(lb)) == EOF) { 1069 if (diff_format == D_RCSDIFF) 1070 warn("No newline at end of file"); 1071 else 1072 diff_output("\n\\ No newline at end of " 1073 "file"); 1074 return; 1075 } 1076 if (c == '\t' && (flags & D_EXPANDTABS)) { 1077 do { 1078 diff_output(" "); 1079 } while (++col & 7); 1080 } else { 1081 diff_output("%c", c); 1082 col++; 1083 } 1084 } 1085 } 1086 } 1087 1088 /* 1089 * Hash function taken from Robert Sedgewick, Algorithms in C, 3d ed., p 578. 1090 */ 1091 static int 1092 readhash(FILE *f, int flags) 1093 { 1094 int i, t, space; 1095 int sum; 1096 1097 sum = 1; 1098 space = 0; 1099 if ((flags & (D_FOLDBLANKS|D_IGNOREBLANKS)) == 0) { 1100 if (flags & D_IGNORECASE) 1101 for (i = 0; (t = getc(f)) != '\n'; i++) { 1102 if (t == EOF) { 1103 if (i == 0) 1104 return (0); 1105 break; 1106 } 1107 sum = sum * 127 + chrtran[t]; 1108 } 1109 else 1110 for (i = 0; (t = getc(f)) != '\n'; i++) { 1111 if (t == EOF) { 1112 if (i == 0) 1113 return (0); 1114 break; 1115 } 1116 sum = sum * 127 + t; 1117 } 1118 } else { 1119 for (i = 0;;) { 1120 switch (t = getc(f)) { 1121 case '\t': 1122 case ' ': 1123 space++; 1124 continue; 1125 default: 1126 if (space && (flags & D_IGNOREBLANKS) == 0) { 1127 i++; 1128 space = 0; 1129 } 1130 sum = sum * 127 + chrtran[t]; 1131 i++; 1132 continue; 1133 case EOF: 1134 if (i == 0) 1135 return (0); 1136 /* FALLTHROUGH */ 1137 case '\n': 1138 break; 1139 } 1140 break; 1141 } 1142 } 1143 /* 1144 * There is a remote possibility that we end up with a zero sum. 1145 * Zero is used as an EOF marker, so return 1 instead. 1146 */ 1147 return (sum == 0 ? 1 : sum); 1148 } 1149 1150 static int 1151 asciifile(FILE *f) 1152 { 1153 char buf[BUFSIZ]; 1154 size_t i, cnt; 1155 1156 if (f == NULL) 1157 return (1); 1158 1159 rewind(f); 1160 cnt = fread(buf, 1, sizeof(buf), f); 1161 for (i = 0; i < cnt; i++) 1162 if (!isprint(buf[i]) && !isspace(buf[i])) 1163 return (0); 1164 return (1); 1165 } 1166 1167 #define begins_with(s, pre) (strncmp(s, pre, sizeof(pre)-1) == 0) 1168 1169 static char* 1170 match_function(const long *f, int pos, FILE *fp) 1171 { 1172 unsigned char buf[FUNCTION_CONTEXT_SIZE]; 1173 size_t nc; 1174 int last = lastline; 1175 char *p; 1176 char *state = NULL; 1177 1178 lastline = pos; 1179 while (pos > last) { 1180 fseek(fp, f[pos - 1], SEEK_SET); 1181 nc = f[pos] - f[pos - 1]; 1182 if (nc >= sizeof(buf)) 1183 nc = sizeof(buf) - 1; 1184 nc = fread(buf, 1, nc, fp); 1185 if (nc > 0) { 1186 buf[nc] = '\0'; 1187 p = strchr((const char *)buf, '\n'); 1188 if (p != NULL) 1189 *p = '\0'; 1190 if (isalpha(buf[0]) || buf[0] == '_' || buf[0] == '$') { 1191 if (begins_with(buf, "private:")) { 1192 if (!state) 1193 state = " (private)"; 1194 } else if (begins_with(buf, "protected:")) { 1195 if (!state) 1196 state = " (protected)"; 1197 } else if (begins_with(buf, "public:")) { 1198 if (!state) 1199 state = " (public)"; 1200 } else { 1201 if (strlcpy(lastbuf, (const char *)buf, 1202 sizeof(lastbuf)) >= sizeof(lastbuf)) 1203 errx(1, 1204 "match_function: strlcpy"); 1205 lastmatchline = pos; 1206 return lastbuf; 1207 } 1208 } 1209 } 1210 pos--; 1211 } 1212 return (lastmatchline > 0) ? lastbuf : NULL; 1213 } 1214 1215 1216 /* dump accumulated "context" diff changes */ 1217 static void 1218 dump_context_vec(FILE *f1, FILE *f2, int flags) 1219 { 1220 struct context_vec *cvp = context_vec_start; 1221 int lowa, upb, lowc, upd, do_output; 1222 int a, b, c, d; 1223 char ch, *f; 1224 1225 if (context_vec_start > context_vec_ptr) 1226 return; 1227 1228 b = d = 0; /* gcc */ 1229 lowa = MAX(1, cvp->a - diff_context); 1230 upb = MIN(diff_len[0], context_vec_ptr->b + diff_context); 1231 lowc = MAX(1, cvp->c - diff_context); 1232 upd = MIN(diff_len[1], context_vec_ptr->d + diff_context); 1233 1234 diff_output("***************"); 1235 if ((flags & D_PROTOTYPE)) { 1236 f = match_function(ixold, lowa - 1, f1); 1237 if (f != NULL) { 1238 diff_output(" "); 1239 diff_output("%s", f); 1240 } 1241 } 1242 diff_output("\n*** "); 1243 range(lowa, upb, ","); 1244 diff_output(" ****\n"); 1245 1246 /* 1247 * Output changes to the "old" file. The first loop suppresses 1248 * output if there were no changes to the "old" file (we'll see 1249 * the "old" lines as context in the "new" list). 1250 */ 1251 do_output = 0; 1252 for (; cvp <= context_vec_ptr; cvp++) 1253 if (cvp->a <= cvp->b) { 1254 cvp = context_vec_start; 1255 do_output++; 1256 break; 1257 } 1258 if (do_output != 0) { 1259 while (cvp <= context_vec_ptr) { 1260 a = cvp->a; 1261 b = cvp->b; 1262 c = cvp->c; 1263 d = cvp->d; 1264 1265 if (a <= b && c <= d) 1266 ch = 'c'; 1267 else 1268 ch = (a <= b) ? 'd' : 'a'; 1269 1270 if (ch == 'a') 1271 fetch(ixold, lowa, b, f1, ' ', 0, flags); 1272 else { 1273 fetch(ixold, lowa, a - 1, f1, ' ', 0, flags); 1274 fetch(ixold, a, b, f1, 1275 ch == 'c' ? '!' : '-', 0, flags); 1276 } 1277 lowa = b + 1; 1278 cvp++; 1279 } 1280 fetch(ixold, b + 1, upb, f1, ' ', 0, flags); 1281 } 1282 /* output changes to the "new" file */ 1283 diff_output("--- "); 1284 range(lowc, upd, ","); 1285 diff_output(" ----\n"); 1286 1287 do_output = 0; 1288 for (cvp = context_vec_start; cvp <= context_vec_ptr; cvp++) 1289 if (cvp->c <= cvp->d) { 1290 cvp = context_vec_start; 1291 do_output++; 1292 break; 1293 } 1294 if (do_output != 0) { 1295 while (cvp <= context_vec_ptr) { 1296 a = cvp->a; 1297 b = cvp->b; 1298 c = cvp->c; 1299 d = cvp->d; 1300 1301 if (a <= b && c <= d) 1302 ch = 'c'; 1303 else 1304 ch = (a <= b) ? 'd' : 'a'; 1305 1306 if (ch == 'd') 1307 fetch(ixnew, lowc, d, f2, ' ', 0, flags); 1308 else { 1309 fetch(ixnew, lowc, c - 1, f2, ' ', 0, flags); 1310 fetch(ixnew, c, d, f2, 1311 ch == 'c' ? '!' : '+', 0, flags); 1312 } 1313 lowc = d + 1; 1314 cvp++; 1315 } 1316 fetch(ixnew, d + 1, upd, f2, ' ', 0, flags); 1317 } 1318 context_vec_ptr = context_vec_start - 1; 1319 } 1320 1321 /* dump accumulated "unified" diff changes */ 1322 static void 1323 dump_unified_vec(FILE *f1, FILE *f2, int flags) 1324 { 1325 struct context_vec *cvp = context_vec_start; 1326 int lowa, upb, lowc, upd; 1327 int a, b, c, d; 1328 char ch, *f; 1329 1330 if (context_vec_start > context_vec_ptr) 1331 return; 1332 1333 b = d = 0; /* gcc */ 1334 lowa = MAX(1, cvp->a - diff_context); 1335 upb = MIN(diff_len[0], context_vec_ptr->b + diff_context); 1336 lowc = MAX(1, cvp->c - diff_context); 1337 upd = MIN(diff_len[1], context_vec_ptr->d + diff_context); 1338 1339 diff_output("@@ -"); 1340 uni_range(lowa, upb); 1341 diff_output(" +"); 1342 uni_range(lowc, upd); 1343 diff_output(" @@"); 1344 if ((flags & D_PROTOTYPE)) { 1345 f = match_function(ixold, lowa - 1, f1); 1346 if (f != NULL) { 1347 diff_output(" "); 1348 diff_output("%s", f); 1349 } 1350 } 1351 diff_output("\n"); 1352 1353 /* 1354 * Output changes in "unified" diff format--the old and new lines 1355 * are printed together. 1356 */ 1357 for (; cvp <= context_vec_ptr; cvp++) { 1358 a = cvp->a; 1359 b = cvp->b; 1360 c = cvp->c; 1361 d = cvp->d; 1362 1363 /* 1364 * c: both new and old changes 1365 * d: only changes in the old file 1366 * a: only changes in the new file 1367 */ 1368 if (a <= b && c <= d) 1369 ch = 'c'; 1370 else 1371 ch = (a <= b) ? 'd' : 'a'; 1372 1373 switch (ch) { 1374 case 'c': 1375 fetch(ixold, lowa, a - 1, f1, ' ', 0, flags); 1376 fetch(ixold, a, b, f1, '-', 0, flags); 1377 fetch(ixnew, c, d, f2, '+', 0, flags); 1378 break; 1379 case 'd': 1380 fetch(ixold, lowa, a - 1, f1, ' ', 0, flags); 1381 fetch(ixold, a, b, f1, '-', 0, flags); 1382 break; 1383 case 'a': 1384 fetch(ixnew, lowc, c - 1, f2, ' ', 0, flags); 1385 fetch(ixnew, c, d, f2, '+', 0, flags); 1386 break; 1387 } 1388 lowa = b + 1; 1389 lowc = d + 1; 1390 } 1391 fetch(ixnew, d + 1, upd, f2, ' ', 0, flags); 1392 1393 context_vec_ptr = context_vec_start - 1; 1394 } 1395 1396 void 1397 diff_output(const char *fmt, ...) 1398 { 1399 va_list vap; 1400 int i; 1401 char *str; 1402 1403 va_start(vap, fmt); 1404 i = vasprintf(&str, fmt, vap); 1405 va_end(vap); 1406 if (i == -1) 1407 err(1, "diff_output"); 1408 if (diffbuf != NULL) 1409 rcs_buf_append(diffbuf, str, strlen(str)); 1410 else 1411 printf("%s", str); 1412 xfree(str); 1413 } 1414