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