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