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