1 /* $OpenBSD: diff_internals.c,v 1.20 2008/03/08 11:53:36 joris 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 #include <sys/param.h> 68 #include <sys/stat.h> 69 70 #include <ctype.h> 71 #include <errno.h> 72 #include <regex.h> 73 #include <stddef.h> 74 #include <stdio.h> 75 #include <string.h> 76 #include <unistd.h> 77 78 #include "cvs.h" 79 #include "diff.h" 80 81 /* 82 * diff - compare two files. 83 */ 84 85 /* 86 * Uses an algorithm due to Harold Stone, which finds 87 * a pair of longest identical subsequences in the two 88 * files. 89 * 90 * The major goal is to generate the match vector J. 91 * J[i] is the index of the line in file1 corresponding 92 * to line i file0. J[i] = 0 if there is no 93 * such line in file1. 94 * 95 * Lines are hashed so as to work in core. All potential 96 * matches are located by sorting the lines of each file 97 * on the hash (called ``value''). In particular, this 98 * collects the equivalence classes in file1 together. 99 * Subroutine equiv replaces the value of each line in 100 * file0 by the index of the first element of its 101 * matching equivalence in (the reordered) file1. 102 * To save space equiv squeezes file1 into a single 103 * array member in which the equivalence classes 104 * are simply concatenated, except that their first 105 * members are flagged by changing sign. 106 * 107 * Next the indices that point into member are unsorted into 108 * array class according to the original order of file0. 109 * 110 * The cleverness lies in routine stone. This marches 111 * through the lines of file0, developing a vector klist 112 * of "k-candidates". At step i a k-candidate is a matched 113 * pair of lines x,y (x in file0 y in file1) such that 114 * there is a common subsequence of length k 115 * between the first i lines of file0 and the first y 116 * lines of file1, but there is no such subsequence for 117 * any smaller y. x is the earliest possible mate to y 118 * that occurs in such a subsequence. 119 * 120 * Whenever any of the members of the equivalence class of 121 * lines in file1 matable to a line in file0 has serial number 122 * less than the y of some k-candidate, that k-candidate 123 * with the smallest such y is replaced. The new 124 * k-candidate is chained (via pred) to the current 125 * k-1 candidate so that the actual subsequence can 126 * be recovered. When a member has serial number greater 127 * that the y of all k-candidates, the klist is extended. 128 * At the end, the longest subsequence is pulled out 129 * and placed in the array J by unravel 130 * 131 * With J in hand, the matches there recorded are 132 * check'ed against reality to assure that no spurious 133 * matches have crept in due to hashing. If they have, 134 * they are broken, and "jackpot" is recorded--a harmless 135 * matter except that a true match for a spuriously 136 * mated line may now be unnecessarily reported as a change. 137 * 138 * Much of the complexity of the program comes simply 139 * from trying to minimize core utilization and 140 * maximize the range of doable problems by dynamically 141 * allocating what is needed and reusing what is not. 142 * The core requirements for problems larger than somewhat 143 * are (in words) 2*length(file0) + length(file1) + 144 * 3*(number of k-candidates installed), typically about 145 * 6n words for files of length n. 146 */ 147 148 struct cand { 149 int x; 150 int y; 151 int pred; 152 }; 153 154 struct line { 155 int serial; 156 int value; 157 } *file[2]; 158 159 /* 160 * The following struct is used to record change information when 161 * doing a "context" or "unified" diff. (see routine "change" to 162 * understand the highly mnemonic field names) 163 */ 164 struct context_vec { 165 int a; /* start line in old file */ 166 int b; /* end line in old file */ 167 int c; /* start line in new file */ 168 int d; /* end line in new file */ 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 void 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 diff_head(void); 183 static void rdiff_head(void); 184 static void change(FILE *, FILE *, int, int, int, int); 185 static void sort(struct line *, int); 186 static int ignoreline(char *); 187 static int asciifile(FILE *); 188 static void fetch(long *, int, int, FILE *, int, int); 189 static int newcand(int, int, int); 190 static int search(int *, int, int); 191 static int skipline(FILE *); 192 static int isqrt(int); 193 static int stone(int *, int, int *, int *); 194 static int readhash(FILE *); 195 static int files_differ(FILE *, FILE *); 196 static char *match_function(const long *, int, FILE *); 197 static char *preadline(int, size_t, off_t); 198 199 static int aflag, bflag, dflag, tflag, Tflag, wflag; 200 static int context = 3; 201 int diff_format = D_NORMAL; 202 int diff_iflag = 0; 203 int diff_pflag = 0; 204 char *diff_file = NULL; 205 RCSNUM *diff_rev1 = NULL; 206 RCSNUM *diff_rev2 = NULL; 207 char diffargs[128]; 208 static struct stat stb1, stb2; 209 static char *ifdefname, *ignore_pats; 210 regex_t 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 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 /* 240 * chrtran points to one of 2 translation tables: cup2low if folding upper to 241 * lower case clow2low if not folding case 242 */ 243 u_char clow2low[256] = { 244 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 245 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 246 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20, 247 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b, 248 0x2c, 0x2d, 0x2e, 0x2f, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 249 0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, 0x40, 0x41, 250 0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49, 0x4a, 0x4b, 0x4c, 251 0x4d, 0x4e, 0x4f, 0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57, 252 0x58, 0x59, 0x5a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f, 0x60, 0x61, 0x62, 253 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 254 0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, 255 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x80, 0x81, 0x82, 0x83, 256 0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 257 0x8f, 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99, 258 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f, 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 259 0xa5, 0xa6, 0xa7, 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf, 260 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba, 261 0xbb, 0xbc, 0xbd, 0xbe, 0xbf, 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 262 0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, 0xd0, 263 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, 0xdb, 264 0xdc, 0xdd, 0xde, 0xdf, 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 265 0xe7, 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef, 0xf0, 0xf1, 266 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 267 0xfd, 0xfe, 0xff 268 }; 269 270 u_char cup2low[256] = { 271 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 272 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 273 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20, 274 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b, 275 0x2c, 0x2d, 0x2e, 0x2f, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 276 0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, 0x60, 0x61, 277 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 278 0x6d, 0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 279 0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x60, 0x61, 0x62, 280 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 281 0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, 282 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x80, 0x81, 0x82, 0x83, 283 0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 284 0x8f, 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99, 285 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f, 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 286 0xa5, 0xa6, 0xa7, 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf, 287 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba, 288 0xbb, 0xbc, 0xbd, 0xbe, 0xbf, 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 289 0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, 0xd0, 290 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, 0xdb, 291 0xdc, 0xdd, 0xde, 0xdf, 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 292 0xe7, 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef, 0xf0, 0xf1, 293 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 294 0xfd, 0xfe, 0xff 295 }; 296 297 int 298 cvs_diffreg(const char *file1, const char *file2, int _fd1, int _fd2, BUF *out) 299 { 300 FILE *f1, *f2; 301 int i, rval, fd1, fd2; 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 chrtran = (diff_iflag ? cup2low : clow2low); 310 if (out != NULL) 311 diffbuf = out; 312 313 fd1 = dup(_fd1); 314 if (fd1 == -1) 315 fatal("cvs_diffreg: dup: %s", strerror(errno)); 316 317 fd2 = dup(_fd2); 318 if (fd2 == -1) 319 fatal("cvs_diffreg: dup: %s", strerror(errno)); 320 321 if (lseek(fd1, 0, SEEK_SET) < 0) 322 fatal("cvs_diffreg: lseek: %s", strerror(errno)); 323 324 f1 = fdopen(fd1, "r"); 325 if (f1 == NULL) { 326 cvs_log(LP_ERR, "%s", file1); 327 goto closem; 328 } 329 330 if (lseek(fd2, 0, SEEK_SET) < 0) 331 fatal("cvs_diffreg: lseek: %s", strerror(errno)); 332 333 f2 = fdopen(fd2, "r"); 334 if (f2 == NULL) { 335 cvs_log(LP_ERR, "%s", file2); 336 goto closem; 337 } 338 339 if (fstat(fd1, &stb1) < 0) { 340 cvs_log(LP_ERR, "%s", file1); 341 goto closem; 342 } 343 344 if (fstat(fd2, &stb2) < 0) { 345 cvs_log(LP_ERR, "%s", file2); 346 goto closem; 347 } 348 349 switch (files_differ(f1, f2)) { 350 case 0: 351 goto closem; 352 case 1: 353 break; 354 default: 355 /* error */ 356 goto closem; 357 } 358 359 if (!asciifile(f1) || !asciifile(f2)) { 360 rval = D_BINARY; 361 goto closem; 362 } 363 364 prepare(0, f1, stb1.st_size); 365 prepare(1, f2, stb2.st_size); 366 367 prune(); 368 sort(sfile[0], slen[0]); 369 sort(sfile[1], slen[1]); 370 371 member = (int *)file[1]; 372 equiv(sfile[0], slen[0], sfile[1], slen[1], member); 373 member = xrealloc(member, slen[1] + 2, sizeof(*member)); 374 375 class = (int *)file[0]; 376 unsort(sfile[0], slen[0], class); 377 class = xrealloc(class, slen[0] + 2, sizeof(*class)); 378 379 klist = xcalloc(slen[0] + 2, sizeof(*klist)); 380 clen = 0; 381 clistlen = 100; 382 clist = xcalloc(clistlen, sizeof(*clist)); 383 i = stone(class, slen[0], member, klist); 384 xfree(member); 385 xfree(class); 386 387 J = xrealloc(J, len[0] + 2, sizeof(*J)); 388 unravel(klist[i]); 389 xfree(clist); 390 xfree(klist); 391 392 ixold = xrealloc(ixold, len[0] + 2, sizeof(*ixold)); 393 ixnew = xrealloc(ixnew, len[1] + 2, sizeof(*ixnew)); 394 check(f1, f2); 395 output(f1, f2); 396 397 closem: 398 if (anychange) { 399 if (rval == D_SAME) 400 rval = D_DIFFER; 401 } 402 if (f1 != NULL) 403 fclose(f1); 404 405 if (f2 != NULL) 406 fclose(f2); 407 408 return (rval); 409 } 410 411 /* 412 * Check to see if the given files differ. 413 * Returns 0 if they are the same, 1 if different, and -1 on error. 414 * XXX - could use code from cmp(1) [faster] 415 */ 416 static int 417 files_differ(FILE *f1, FILE *f2) 418 { 419 char buf1[BUFSIZ], buf2[BUFSIZ]; 420 size_t i, j; 421 422 if (stb1.st_size != stb2.st_size) 423 return (1); 424 for (;;) { 425 i = fread(buf1, 1, sizeof(buf1), f1); 426 j = fread(buf2, 1, sizeof(buf2), f2); 427 if (i != j) 428 return (1); 429 if (i == 0 && j == 0) { 430 if (ferror(f1) || ferror(f2)) 431 return (1); 432 return (0); 433 } 434 if (memcmp(buf1, buf2, i) != 0) 435 return (1); 436 } 437 } 438 439 static void 440 prepare(int i, FILE *fd, off_t filesize) 441 { 442 struct line *p; 443 int j, h; 444 size_t sz; 445 446 rewind(fd); 447 448 sz = (filesize <= SIZE_MAX ? filesize : SIZE_MAX) / 25; 449 if (sz < 100) 450 sz = 100; 451 452 p = xcalloc(sz + 3, sizeof(*p)); 453 for (j = 0; (h = readhash(fd));) { 454 if (j == sz) { 455 sz = sz * 3 / 2; 456 p = xrealloc(p, sz + 3, sizeof(*p)); 457 } 458 p[++j].value = h; 459 } 460 len[i] = j; 461 file[i] = p; 462 } 463 464 static void 465 prune(void) 466 { 467 int i, j; 468 469 for (pref = 0; pref < len[0] && pref < len[1] && 470 file[0][pref + 1].value == file[1][pref + 1].value; 471 pref++) 472 ; 473 for (suff = 0; suff < len[0] - pref && suff < len[1] - pref && 474 file[0][len[0] - suff].value == file[1][len[1] - suff].value; 475 suff++) 476 ; 477 for (j = 0; j < 2; j++) { 478 sfile[j] = file[j] + pref; 479 slen[j] = 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) 534 { 535 int i, k, y, j, l; 536 int oldc, tc, oldl; 537 u_int numtries; 538 539 /* XXX move the isqrt() out of the macro to avoid multiple calls */ 540 const u_int bound = dflag ? UINT_MAX : MAX(256, (u_int)isqrt(n)); 541 542 k = 0; 543 c[0] = newcand(0, 0, 0); 544 for (i = 1; i <= n; i++) { 545 j = a[i]; 546 if (j == 0) 547 continue; 548 y = -b[j]; 549 oldl = 0; 550 oldc = c[0]; 551 numtries = 0; 552 do { 553 if (y <= clist[oldc].y) 554 continue; 555 l = search(c, k, y); 556 if (l != oldl + 1) 557 oldc = c[l - 1]; 558 if (l <= k) { 559 if (clist[c[l]].y <= y) 560 continue; 561 tc = c[l]; 562 c[l] = newcand(i, y, oldc); 563 oldc = tc; 564 oldl = l; 565 numtries++; 566 } else { 567 c[l] = newcand(i, y, oldc); 568 k++; 569 break; 570 } 571 } while ((y = b[++j]) > 0 && numtries < bound); 572 } 573 return (k); 574 } 575 576 static int 577 newcand(int x, int y, int pred) 578 { 579 struct cand *q; 580 581 if (clen == clistlen) { 582 clistlen = clistlen * 11 / 10; 583 clist = xrealloc(clist, clistlen, sizeof(*clist)); 584 } 585 q = clist + clen; 586 q->x = x; 587 q->y = y; 588 q->pred = pred; 589 return (clen++); 590 } 591 592 static int 593 search(int *c, int k, int y) 594 { 595 int i, j, l, t; 596 597 if (clist[c[k]].y < y) /* quick look for typical case */ 598 return (k + 1); 599 i = 0; 600 j = k + 1; 601 for (;;) { 602 l = (i + j) / 2; 603 if (l <= i) 604 break; 605 t = clist[c[l]].y; 606 if (t > y) 607 j = l; 608 else if (t < y) 609 i = l; 610 else 611 return (l); 612 } 613 return (l + 1); 614 } 615 616 static void 617 unravel(int p) 618 { 619 struct cand *q; 620 int i; 621 622 for (i = 0; i <= len[0]; i++) 623 J[i] = i <= pref ? i : 624 i > len[0] - suff ? i + len[1] - len[0] : 0; 625 for (q = clist + p; q->y != 0; q = clist + q->pred) 626 J[q->x + pref] = q->y + pref; 627 } 628 629 /* 630 * Check does double duty: 631 * 1. ferret out any fortuitous correspondences due 632 * to confounding by hashing (which result in "jackpot") 633 * 2. collect random access indexes to the two files 634 */ 635 static void 636 check(FILE *f1, FILE *f2) 637 { 638 int i, j, jackpot, c, d; 639 long ctold, ctnew; 640 641 rewind(f1); 642 rewind(f2); 643 j = 1; 644 ixold[0] = ixnew[0] = 0; 645 jackpot = 0; 646 ctold = ctnew = 0; 647 for (i = 1; i <= len[0]; i++) { 648 if (J[i] == 0) { 649 ixold[i] = ctold += skipline(f1); 650 continue; 651 } 652 while (j < J[i]) { 653 ixnew[j] = ctnew += skipline(f2); 654 j++; 655 } 656 if (bflag == 1 || wflag == 1 || diff_iflag == 1) { 657 for (;;) { 658 c = getc(f1); 659 d = getc(f2); 660 /* 661 * GNU diff ignores a missing newline 662 * in one file for -b or -w. 663 */ 664 if ((bflag == 1 || wflag == 1) && 665 ((c == EOF && d == '\n') || 666 (c == '\n' && d == EOF))) { 667 break; 668 } 669 ctold++; 670 ctnew++; 671 if (bflag == 1 && isspace(c) && isspace(d)) { 672 do { 673 if (c == '\n') 674 break; 675 ctold++; 676 } while (isspace(c = getc(f1))); 677 do { 678 if (d == '\n') 679 break; 680 ctnew++; 681 } while (isspace(d = getc(f2))); 682 } else if (wflag == 1) { 683 while (isspace(c) && c != '\n') { 684 c = getc(f1); 685 ctold++; 686 } 687 while (isspace(d) && d != '\n') { 688 d = getc(f2); 689 ctnew++; 690 } 691 } 692 if (chrtran[c] != chrtran[d]) { 693 jackpot++; 694 J[i] = 0; 695 if (c != '\n' && c != EOF) 696 ctold += skipline(f1); 697 if (d != '\n' && c != EOF) 698 ctnew += skipline(f2); 699 break; 700 } 701 if (c == '\n' || c == EOF) 702 break; 703 } 704 } else { 705 for (;;) { 706 ctold++; 707 ctnew++; 708 if ((c = getc(f1)) != (d = getc(f2))) { 709 /* jackpot++; */ 710 J[i] = 0; 711 if (c != '\n' && c != EOF) 712 ctold += skipline(f1); 713 if (d != '\n' && c != EOF) 714 ctnew += skipline(f2); 715 break; 716 } 717 if (c == '\n' || c == EOF) 718 break; 719 } 720 } 721 ixold[i] = ctold; 722 ixnew[j] = ctnew; 723 j++; 724 } 725 for (; j <= len[1]; j++) 726 ixnew[j] = ctnew += skipline(f2); 727 /* 728 * if (jackpot) 729 * fprintf(stderr, "jackpot\n"); 730 */ 731 } 732 733 /* shellsort CACM #201 */ 734 static void 735 sort(struct line *a, int n) 736 { 737 struct line *ai, *aim, w; 738 int j, m = 0, k; 739 740 if (n == 0) 741 return; 742 for (j = 1; j <= n; j *= 2) 743 m = 2 * j - 1; 744 for (m /= 2; m != 0; m /= 2) { 745 k = n - m; 746 for (j = 1; j <= k; j++) { 747 for (ai = &a[j]; ai > a; ai -= m) { 748 aim = &ai[m]; 749 if (aim < ai) 750 break; /* wraparound */ 751 if (aim->value > ai[0].value || 752 (aim->value == ai[0].value && 753 aim->serial > ai[0].serial)) 754 break; 755 w.value = ai[0].value; 756 ai[0].value = aim->value; 757 aim->value = w.value; 758 w.serial = ai[0].serial; 759 ai[0].serial = aim->serial; 760 aim->serial = w.serial; 761 } 762 } 763 } 764 } 765 766 static void 767 unsort(struct line *f, int l, int *b) 768 { 769 int *a, i; 770 771 a = xcalloc(l + 1, sizeof(*a)); 772 for (i = 1; i <= l; i++) 773 a[f[i].serial] = f[i].value; 774 for (i = 1; i <= l; i++) 775 b[i] = a[i]; 776 xfree(a); 777 } 778 779 static int 780 skipline(FILE *f) 781 { 782 int i, c; 783 784 for (i = 1; (c = getc(f)) != '\n' && c != EOF; i++) 785 continue; 786 return (i); 787 } 788 789 static void 790 output(FILE *f1, FILE *f2) 791 { 792 int m, i0, i1, j0, j1; 793 794 rewind(f1); 795 rewind(f2); 796 m = len[0]; 797 J[0] = 0; 798 J[m + 1] = len[1] + 1; 799 for (i0 = 1; i0 <= m; i0 = i1 + 1) { 800 while (i0 <= m && J[i0] == J[i0 - 1] + 1) 801 i0++; 802 j0 = J[i0 - 1] + 1; 803 i1 = i0 - 1; 804 while (i1 < m && J[i1 + 1] == 0) 805 i1++; 806 j1 = J[i1 + 1] - 1; 807 J[i1] = j1; 808 change(f1, f2, i0, i1, j0, j1); 809 } 810 if (m == 0) 811 change(f1, f2, 1, 0, 1, len[1]); 812 if (diff_format == D_IFDEF) { 813 for (;;) { 814 #define c i0 815 if ((c = getc(f1)) == EOF) 816 return; 817 diff_output("%c", c); 818 } 819 #undef c 820 } 821 if (anychange != 0) { 822 if (diff_format == D_CONTEXT) 823 dump_context_vec(f1, f2); 824 else if (diff_format == D_UNIFIED) 825 dump_unified_vec(f1, f2); 826 } 827 } 828 829 static void 830 range(int a, int b, char *separator) 831 { 832 diff_output("%d", a > b ? b : a); 833 if (a < b) 834 diff_output("%s%d", separator, b); 835 } 836 837 static void 838 uni_range(int a, int b) 839 { 840 if (a < b) 841 diff_output("%d,%d", a, b - a + 1); 842 else if (a == b) 843 diff_output("%d", b); 844 else 845 diff_output("%d,0", b); 846 } 847 848 static char * 849 preadline(int fd, size_t rlen, off_t off) 850 { 851 char *line; 852 ssize_t nr; 853 854 line = xmalloc(rlen + 1); 855 if ((nr = pread(fd, line, rlen, off)) < 0) { 856 cvs_log(LP_ERR, "preadline failed"); 857 xfree(line); 858 return (NULL); 859 } 860 line[nr] = '\0'; 861 return (line); 862 } 863 864 static int 865 ignoreline(char *line) 866 { 867 int ret; 868 869 ret = regexec(&ignore_re, line, 0, NULL, 0); 870 xfree(line); 871 return (ret == 0); /* if it matched, it should be ignored. */ 872 } 873 874 static void 875 diff_head(void) 876 { 877 char buf[64]; 878 struct tm *t; 879 time_t curr_time; 880 881 if (diff_rev1 != NULL) { 882 t = gmtime(&stb1.st_mtime); 883 } else { 884 time(&curr_time); 885 t = localtime(&curr_time); 886 } 887 888 (void)strftime(buf, sizeof(buf), "%b %G %H:%M:%S -0000", t); 889 diff_output("%s %s %d %s", diff_format == D_CONTEXT ? 890 "***" : "---", diff_file, t->tm_mday, buf); 891 892 if (diff_rev1 != NULL) { 893 rcsnum_tostr(diff_rev1, buf, sizeof(buf)); 894 diff_output("\t%s", buf); 895 } 896 897 diff_output("\n"); 898 899 t = gmtime(&stb2.st_mtime); 900 901 (void)strftime(buf, sizeof(buf), "%b %G %H:%M:%S -0000", t); 902 diff_output("%s %s %d %s", diff_format == D_CONTEXT ? 903 "---" : "+++", diff_file, t->tm_mday, buf); 904 905 if (diff_rev2 != NULL) { 906 rcsnum_tostr(diff_rev2, buf, sizeof(buf)); 907 diff_output("\t%s", buf); 908 } 909 910 diff_output("\n"); 911 } 912 913 static void 914 rdiff_head(void) 915 { 916 char buf[64]; 917 struct tm *t; 918 time_t curr_time; 919 920 if (diff_rev1 != NULL) { 921 t = localtime(&stb1.st_mtime); 922 } else { 923 time(&curr_time); 924 t = localtime(&curr_time); 925 } 926 927 diff_output("%s ", diff_format == D_CONTEXT ? "***" : "---"); 928 929 if (diff_rev1 == NULL) { 930 diff_output("%s", CVS_PATH_DEVNULL); 931 t = gmtime(&stb1.st_atime); 932 } else { 933 rcsnum_tostr(diff_rev1, buf, sizeof(buf)); 934 diff_output("%s:%s", diff_file, buf); 935 } 936 937 (void)strftime(buf, sizeof(buf), "%a %b %e %H:%M:%S %G", t); 938 diff_output("\t%s\n", buf); 939 940 if (diff_rev2 != NULL) { 941 t = localtime(&stb2.st_mtime); 942 } else { 943 time(&curr_time); 944 t = localtime(&curr_time); 945 } 946 947 (void)strftime(buf, sizeof(buf), "%a %b %e %H:%M:%S %G", t); 948 949 diff_output("%s %s %s\n", diff_format == D_CONTEXT ? "---" : "+++", 950 diff_file, buf); 951 } 952 953 /* 954 * Indicate that there is a difference between lines a and b of the from file 955 * to get to lines c to d of the to file. If a is greater then b then there 956 * are no lines in the from file involved and this means that there were 957 * lines appended (beginning at b). If c is greater than d then there are 958 * lines missing from the to file. 959 */ 960 static void 961 change(FILE *f1, FILE *f2, int a, int b, int c, int d) 962 { 963 static size_t max_context = 64; 964 int i; 965 966 if (diff_format != D_IFDEF && a > b && c > d) 967 return; 968 if (ignore_pats != NULL) { 969 char *line; 970 /* 971 * All lines in the change, insert, or delete must 972 * match an ignore pattern for the change to be 973 * ignored. 974 */ 975 if (a <= b) { /* Changes and deletes. */ 976 for (i = a; i <= b; i++) { 977 line = preadline(fileno(f1), 978 ixold[i] - ixold[i - 1], ixold[i - 1]); 979 if (!ignoreline(line)) 980 goto proceed; 981 } 982 } 983 if (a > b || c <= d) { /* Changes and inserts. */ 984 for (i = c; i <= d; i++) { 985 line = preadline(fileno(f2), 986 ixnew[i] - ixnew[i - 1], ixnew[i - 1]); 987 if (!ignoreline(line)) 988 goto proceed; 989 } 990 } 991 return; 992 } 993 proceed: 994 if (diff_format == D_CONTEXT || diff_format == D_UNIFIED) { 995 /* 996 * Allocate change records as needed. 997 */ 998 if (context_vec_ptr == context_vec_end - 1) { 999 ptrdiff_t offset = context_vec_ptr - context_vec_start; 1000 max_context <<= 1; 1001 context_vec_start = xrealloc(context_vec_start, 1002 max_context, sizeof(*context_vec_start)); 1003 context_vec_end = context_vec_start + max_context; 1004 context_vec_ptr = context_vec_start + offset; 1005 } 1006 if (anychange == 0) { 1007 /* 1008 * Print the context/unidiff header first time through. 1009 */ 1010 if (cvs_cmdop == CVS_OP_RDIFF) 1011 rdiff_head(); 1012 else 1013 diff_head(); 1014 1015 anychange = 1; 1016 } else if (a > context_vec_ptr->b + (2 * context) + 1 && 1017 c > context_vec_ptr->d + (2 * context) + 1) { 1018 /* 1019 * If this change is more than 'context' lines from the 1020 * previous change, dump the record and reset it. 1021 */ 1022 if (diff_format == D_CONTEXT) 1023 dump_context_vec(f1, f2); 1024 else 1025 dump_unified_vec(f1, f2); 1026 } 1027 context_vec_ptr++; 1028 context_vec_ptr->a = a; 1029 context_vec_ptr->b = b; 1030 context_vec_ptr->c = c; 1031 context_vec_ptr->d = d; 1032 return; 1033 } 1034 if (anychange == 0) 1035 anychange = 1; 1036 switch (diff_format) { 1037 case D_BRIEF: 1038 return; 1039 case D_NORMAL: 1040 range(a, b, ","); 1041 diff_output("%c", a > b ? 'a' : c > d ? 'd' : 'c'); 1042 if (diff_format == D_NORMAL) 1043 range(c, d, ","); 1044 diff_output("\n"); 1045 break; 1046 case D_RCSDIFF: 1047 if (a > b) 1048 diff_output("a%d %d\n", b, d - c + 1); 1049 else { 1050 diff_output("d%d %d\n", a, b - a + 1); 1051 1052 if (!(c > d)) /* add changed lines */ 1053 diff_output("a%d %d\n", b, d - c + 1); 1054 } 1055 break; 1056 } 1057 if (diff_format == D_NORMAL || diff_format == D_IFDEF) { 1058 fetch(ixold, a, b, f1, '<', 1); 1059 if (a <= b && c <= d && diff_format == D_NORMAL) 1060 diff_output("---\n"); 1061 } 1062 fetch(ixnew, c, d, f2, diff_format == D_NORMAL ? '>' : '\0', 0); 1063 if (inifdef) { 1064 diff_output("#endif /* %s */\n", ifdefname); 1065 inifdef = 0; 1066 } 1067 } 1068 1069 static void 1070 fetch(long *f, int a, int b, FILE *lb, int ch, int oldfile) 1071 { 1072 long j, nc; 1073 int i, c, col; 1074 1075 /* 1076 * When doing #ifdef's, copy down to current line 1077 * if this is the first file, so that stuff makes it to output. 1078 */ 1079 if (diff_format == D_IFDEF && oldfile) { 1080 long curpos = ftell(lb); 1081 /* print through if append (a>b), else to (nb: 0 vs 1 orig) */ 1082 nc = f[a > b ? b : a - 1] - curpos; 1083 for (i = 0; i < nc; i++) 1084 diff_output("%c", getc(lb)); 1085 } 1086 if (a > b) 1087 return; 1088 if (diff_format == D_IFDEF) { 1089 if (inifdef) { 1090 diff_output("#else /* %s%s */\n", 1091 oldfile == 1 ? "!" : "", ifdefname); 1092 } else { 1093 if (oldfile) 1094 diff_output("#ifndef %s\n", ifdefname); 1095 else 1096 diff_output("#ifdef %s\n", ifdefname); 1097 } 1098 inifdef = 1 + oldfile; 1099 } 1100 for (i = a; i <= b; i++) { 1101 fseek(lb, f[i - 1], SEEK_SET); 1102 nc = f[i] - f[i - 1]; 1103 if (diff_format != D_IFDEF && ch != '\0') { 1104 diff_output("%c", ch); 1105 if (Tflag == 1 && (diff_format == D_NORMAL || 1106 diff_format == D_CONTEXT || 1107 diff_format == D_UNIFIED)) 1108 diff_output("\t"); 1109 else if (diff_format != D_UNIFIED) 1110 diff_output(" "); 1111 } 1112 col = 0; 1113 for (j = 0; j < nc; j++) { 1114 if ((c = getc(lb)) == EOF) { 1115 if (diff_format == D_RCSDIFF) 1116 cvs_log(LP_ERR, 1117 "No newline at end of file"); 1118 else 1119 diff_output("\n\\ No newline at end of " 1120 "file\n"); 1121 return; 1122 } 1123 if (c == '\t' && tflag == 1) { 1124 do { 1125 diff_output(" "); 1126 } while (++col & 7); 1127 } else { 1128 diff_output("%c", c); 1129 col++; 1130 } 1131 } 1132 } 1133 } 1134 1135 /* 1136 * Hash function taken from Robert Sedgewick, Algorithms in C, 3d ed., p 578. 1137 */ 1138 static int 1139 readhash(FILE *f) 1140 { 1141 int i, t, space; 1142 int sum; 1143 1144 sum = 1; 1145 space = 0; 1146 if (bflag != 1 && wflag != 1) { 1147 if (diff_iflag == 1) 1148 for (i = 0; (t = getc(f)) != '\n'; i++) { 1149 if (t == EOF) { 1150 if (i == 0) 1151 return (0); 1152 break; 1153 } 1154 sum = sum * 127 + chrtran[t]; 1155 } 1156 else 1157 for (i = 0; (t = getc(f)) != '\n'; i++) { 1158 if (t == EOF) { 1159 if (i == 0) 1160 return (0); 1161 break; 1162 } 1163 sum = sum * 127 + t; 1164 } 1165 } else { 1166 for (i = 0;;) { 1167 switch (t = getc(f)) { 1168 case '\t': 1169 case '\r': 1170 case '\v': 1171 case '\f': 1172 case ' ': 1173 space++; 1174 continue; 1175 default: 1176 if (space != 0 && wflag != 1) { 1177 i++; 1178 space = 0; 1179 } 1180 sum = sum * 127 + chrtran[t]; 1181 i++; 1182 continue; 1183 case EOF: 1184 if (i == 0) 1185 return (0); 1186 /* FALLTHROUGH */ 1187 case '\n': 1188 break; 1189 } 1190 break; 1191 } 1192 } 1193 /* 1194 * There is a remote possibility that we end up with a zero sum. 1195 * Zero is used as an EOF marker, so return 1 instead. 1196 */ 1197 return (sum == 0 ? 1 : sum); 1198 } 1199 1200 static int 1201 asciifile(FILE *f) 1202 { 1203 unsigned char buf[BUFSIZ]; 1204 size_t i, cnt; 1205 1206 if (aflag == 1 || f == NULL) 1207 return (1); 1208 1209 rewind(f); 1210 cnt = fread(buf, 1, sizeof(buf), f); 1211 for (i = 0; i < cnt; i++) 1212 if (!isprint(buf[i]) && !isspace(buf[i])) 1213 return (0); 1214 return (1); 1215 } 1216 1217 #define begins_with(s, pre) (strncmp(s, pre, sizeof(pre)-1) == 0) 1218 1219 static char * 1220 match_function(const long *f, int pos, FILE *fp) 1221 { 1222 unsigned char buf[FUNCTION_CONTEXT_SIZE]; 1223 size_t nc; 1224 int last = lastline; 1225 char *p; 1226 char *state = NULL; 1227 1228 lastline = pos; 1229 while (pos > last) { 1230 fseek(fp, f[pos - 1], SEEK_SET); 1231 nc = f[pos] - f[pos - 1]; 1232 if (nc >= sizeof(buf)) 1233 nc = sizeof(buf) - 1; 1234 nc = fread(buf, 1, nc, fp); 1235 if (nc > 0) { 1236 buf[nc] = '\0'; 1237 p = strchr((const char *)buf, '\n'); 1238 if (p != NULL) 1239 *p = '\0'; 1240 if (isalpha(buf[0]) || buf[0] == '_' || buf[0] == '$') { 1241 if (begins_with(buf, "private:")) { 1242 if (!state) 1243 state = " (private)"; 1244 } else if (begins_with(buf, "protected:")) { 1245 if (!state) 1246 state = " (protected)"; 1247 } else if (begins_with(buf, "public:")) { 1248 if (!state) 1249 state = " (public)"; 1250 } else { 1251 strlcpy(lastbuf, buf, 1252 sizeof lastbuf); 1253 if (state) 1254 strlcat(lastbuf, state, 1255 sizeof lastbuf); 1256 lastmatchline = pos; 1257 return lastbuf; 1258 } 1259 } 1260 } 1261 pos--; 1262 } 1263 return lastmatchline > 0 ? lastbuf : NULL; 1264 } 1265 1266 /* dump accumulated "context" diff changes */ 1267 static void 1268 dump_context_vec(FILE *f1, FILE *f2) 1269 { 1270 struct context_vec *cvp = context_vec_start; 1271 int lowa, upb, lowc, upd, do_output; 1272 int a, b, c, d; 1273 char ch, *f; 1274 1275 if (context_vec_start > context_vec_ptr) 1276 return; 1277 1278 b = d = 0; /* gcc */ 1279 lowa = MAX(1, cvp->a - context); 1280 upb = MIN(len[0], context_vec_ptr->b + context); 1281 lowc = MAX(1, cvp->c - context); 1282 upd = MIN(len[1], context_vec_ptr->d + context); 1283 1284 diff_output("***************"); 1285 if (diff_pflag == 1) { 1286 f = match_function(ixold, lowa-1, f1); 1287 if (f != NULL) { 1288 diff_output(" "); 1289 diff_output("%s", f); 1290 } 1291 } 1292 diff_output("\n*** "); 1293 range(lowa, upb, ","); 1294 diff_output(" ****\n"); 1295 1296 /* 1297 * Output changes to the "old" file. The first loop suppresses 1298 * output if there were no changes to the "old" file (we'll see 1299 * the "old" lines as context in the "new" list). 1300 */ 1301 do_output = 0; 1302 for (; cvp <= context_vec_ptr; cvp++) 1303 if (cvp->a <= cvp->b) { 1304 cvp = context_vec_start; 1305 do_output++; 1306 break; 1307 } 1308 if (do_output) { 1309 while (cvp <= context_vec_ptr) { 1310 a = cvp->a; 1311 b = cvp->b; 1312 c = cvp->c; 1313 d = cvp->d; 1314 1315 if (a <= b && c <= d) 1316 ch = 'c'; 1317 else 1318 ch = (a <= b) ? 'd' : 'a'; 1319 1320 if (ch == 'a') 1321 fetch(ixold, lowa, b, f1, ' ', 0); 1322 else { 1323 fetch(ixold, lowa, a - 1, f1, ' ', 0); 1324 fetch(ixold, a, b, f1, 1325 ch == 'c' ? '!' : '-', 0); 1326 } 1327 lowa = b + 1; 1328 cvp++; 1329 } 1330 fetch(ixold, b + 1, upb, f1, ' ', 0); 1331 } 1332 /* output changes to the "new" file */ 1333 diff_output("--- "); 1334 range(lowc, upd, ","); 1335 diff_output(" ----\n"); 1336 1337 do_output = 0; 1338 for (cvp = context_vec_start; cvp <= context_vec_ptr; cvp++) 1339 if (cvp->c <= cvp->d) { 1340 cvp = context_vec_start; 1341 do_output++; 1342 break; 1343 } 1344 if (do_output) { 1345 while (cvp <= context_vec_ptr) { 1346 a = cvp->a; 1347 b = cvp->b; 1348 c = cvp->c; 1349 d = cvp->d; 1350 1351 if (a <= b && c <= d) 1352 ch = 'c'; 1353 else 1354 ch = (a <= b) ? 'd' : 'a'; 1355 1356 if (ch == 'd') 1357 fetch(ixnew, lowc, d, f2, ' ', 0); 1358 else { 1359 fetch(ixnew, lowc, c - 1, f2, ' ', 0); 1360 fetch(ixnew, c, d, f2, 1361 ch == 'c' ? '!' : '+', 0); 1362 } 1363 lowc = d + 1; 1364 cvp++; 1365 } 1366 fetch(ixnew, d + 1, upd, f2, ' ', 0); 1367 } 1368 context_vec_ptr = context_vec_start - 1; 1369 } 1370 1371 /* dump accumulated "unified" diff changes */ 1372 static void 1373 dump_unified_vec(FILE *f1, FILE *f2) 1374 { 1375 struct context_vec *cvp = context_vec_start; 1376 int lowa, upb, lowc, upd; 1377 int a, b, c, d; 1378 char ch, *f; 1379 1380 if (context_vec_start > context_vec_ptr) 1381 return; 1382 1383 b = d = 0; /* gcc */ 1384 lowa = MAX(1, cvp->a - context); 1385 upb = MIN(len[0], context_vec_ptr->b + context); 1386 lowc = MAX(1, cvp->c - context); 1387 upd = MIN(len[1], context_vec_ptr->d + context); 1388 1389 diff_output("@@ -"); 1390 uni_range(lowa, upb); 1391 diff_output(" +"); 1392 uni_range(lowc, upd); 1393 diff_output(" @@"); 1394 if (diff_pflag == 1) { 1395 f = match_function(ixold, lowa-1, f1); 1396 if (f != NULL) { 1397 diff_output(" "); 1398 diff_output("%s", f); 1399 } 1400 } 1401 diff_output("\n"); 1402 1403 /* 1404 * Output changes in "unified" diff format--the old and new lines 1405 * are printed together. 1406 */ 1407 for (; cvp <= context_vec_ptr; cvp++) { 1408 a = cvp->a; 1409 b = cvp->b; 1410 c = cvp->c; 1411 d = cvp->d; 1412 1413 /* 1414 * c: both new and old changes 1415 * d: only changes in the old file 1416 * a: only changes in the new file 1417 */ 1418 if (a <= b && c <= d) 1419 ch = 'c'; 1420 else 1421 ch = (a <= b) ? 'd' : 'a'; 1422 1423 switch (ch) { 1424 case 'c': 1425 fetch(ixold, lowa, a - 1, f1, ' ', 0); 1426 fetch(ixold, a, b, f1, '-', 0); 1427 fetch(ixnew, c, d, f2, '+', 0); 1428 break; 1429 case 'd': 1430 fetch(ixold, lowa, a - 1, f1, ' ', 0); 1431 fetch(ixold, a, b, f1, '-', 0); 1432 break; 1433 case 'a': 1434 fetch(ixnew, lowc, c - 1, f2, ' ', 0); 1435 fetch(ixnew, c, d, f2, '+', 0); 1436 break; 1437 } 1438 lowa = b + 1; 1439 lowc = d + 1; 1440 } 1441 fetch(ixnew, d + 1, upd, f2, ' ', 0); 1442 1443 context_vec_ptr = context_vec_start - 1; 1444 } 1445 1446 void 1447 diff_output(const char *fmt, ...) 1448 { 1449 va_list vap; 1450 int i; 1451 char *str; 1452 1453 va_start(vap, fmt); 1454 i = vasprintf(&str, fmt, vap); 1455 va_end(vap); 1456 if (i == -1) 1457 fatal("diff_output: %s", strerror(errno)); 1458 if (diffbuf != NULL) 1459 cvs_buf_append(diffbuf, str, strlen(str)); 1460 else 1461 cvs_printf("%s", str); 1462 xfree(str); 1463 } 1464