1 /* $OpenBSD: diff_internals.c,v 1.34 2011/04/01 17:25:26 nicm 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 *, int); 173 static void check(FILE *, FILE *, int); 174 static void range(int, int, char *); 175 static void uni_range(int, int); 176 static void dump_context_vec(FILE *, FILE *, int); 177 static void dump_unified_vec(FILE *, FILE *, int); 178 static void prepare(int, FILE *, off_t, int); 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, 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, 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 *, int); 195 static int readhash(FILE *, int); 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; 201 int diff_context = 3; 202 int diff_format = D_NORMAL; 203 const char *diff_file1 = NULL; 204 const char *diff_file2 = NULL; 205 RCSNUM *diff_rev1 = NULL; 206 RCSNUM *diff_rev2 = NULL; 207 char diffargs[512]; 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 diffreg(const char *file1, const char *file2, int _fd1, int _fd2, 299 BUF *out, int flags) 300 { 301 FILE *f1, *f2; 302 int i, rval, fd1, fd2; 303 304 diff_file1 = file1; 305 diff_file2 = file2; 306 f1 = f2 = NULL; 307 rval = D_SAME; 308 anychange = 0; 309 lastline = 0; 310 lastmatchline = 0; 311 context_vec_ptr = context_vec_start - 1; 312 if (flags & D_IGNORECASE) 313 chrtran = cup2low; 314 else 315 chrtran = clow2low; 316 if (out != NULL) 317 diffbuf = out; 318 319 fd1 = dup(_fd1); 320 if (fd1 == -1) 321 fatal("diffreg: dup: %s", strerror(errno)); 322 323 fd2 = dup(_fd2); 324 if (fd2 == -1) 325 fatal("diffreg: dup: %s", strerror(errno)); 326 327 if (lseek(fd1, 0, SEEK_SET) < 0) 328 fatal("diffreg: lseek: %s", strerror(errno)); 329 330 f1 = fdopen(fd1, "r"); 331 if (f1 == NULL) { 332 cvs_log(LP_ERR, "%s", file1); 333 goto closem; 334 } 335 336 if (lseek(fd2, 0, SEEK_SET) < 0) 337 fatal("diffreg: lseek: %s", strerror(errno)); 338 339 f2 = fdopen(fd2, "r"); 340 if (f2 == NULL) { 341 cvs_log(LP_ERR, "%s", file2); 342 goto closem; 343 } 344 345 if (fstat(fd1, &stb1) < 0) { 346 cvs_log(LP_ERR, "%s", file1); 347 goto closem; 348 } 349 350 if (fstat(fd2, &stb2) < 0) { 351 cvs_log(LP_ERR, "%s", file2); 352 goto closem; 353 } 354 355 switch (files_differ(f1, f2)) { 356 case 0: 357 goto closem; 358 case 1: 359 break; 360 default: 361 /* error */ 362 goto closem; 363 } 364 365 if ((flags & D_FORCEASCII) == 0 && 366 (!asciifile(f1) || !asciifile(f2))) { 367 rval = D_BINARY; 368 goto closem; 369 } 370 371 prepare(0, f1, stb1.st_size, flags); 372 prepare(1, f2, stb2.st_size, flags); 373 374 prune(); 375 sort(sfile[0], slen[0]); 376 sort(sfile[1], slen[1]); 377 378 member = (int *)file[1]; 379 equiv(sfile[0], slen[0], sfile[1], slen[1], member); 380 member = xrealloc(member, slen[1] + 2, sizeof(*member)); 381 382 class = (int *)file[0]; 383 unsort(sfile[0], slen[0], class); 384 class = xrealloc(class, slen[0] + 2, sizeof(*class)); 385 386 klist = xcalloc(slen[0] + 2, sizeof(*klist)); 387 clen = 0; 388 clistlen = 100; 389 clist = xcalloc(clistlen, sizeof(*clist)); 390 i = stone(class, slen[0], member, klist, flags); 391 xfree(member); 392 xfree(class); 393 394 J = xrealloc(J, len[0] + 2, sizeof(*J)); 395 unravel(klist[i]); 396 xfree(clist); 397 xfree(klist); 398 399 ixold = xrealloc(ixold, len[0] + 2, sizeof(*ixold)); 400 ixnew = xrealloc(ixnew, len[1] + 2, sizeof(*ixnew)); 401 check(f1, f2, flags); 402 output(f1, f2, flags); 403 404 closem: 405 if (anychange) { 406 if (rval == D_SAME) 407 rval = D_DIFFER; 408 } 409 if (f1 != NULL) 410 fclose(f1); 411 if (f2 != NULL) 412 fclose(f2); 413 414 return (rval); 415 } 416 417 /* 418 * Check to see if the given files differ. 419 * Returns 0 if they are the same, 1 if different, and -1 on error. 420 * XXX - could use code from cmp(1) [faster] 421 */ 422 static int 423 files_differ(FILE *f1, FILE *f2) 424 { 425 char buf1[BUFSIZ], buf2[BUFSIZ]; 426 size_t i, j; 427 428 if (stb1.st_size != stb2.st_size) 429 return (1); 430 for (;;) { 431 i = fread(buf1, 1, sizeof(buf1), f1); 432 j = fread(buf2, 1, sizeof(buf2), f2); 433 if ((!i && ferror(f1)) || (!j && ferror(f2))) 434 return (-1); 435 if (i != j) 436 return (1); 437 if (i == 0) 438 return (0); 439 if (memcmp(buf1, buf2, i) != 0) 440 return (1); 441 } 442 } 443 444 static void 445 prepare(int i, FILE *fd, off_t filesize, int flags) 446 { 447 struct line *p; 448 int j, h; 449 size_t sz; 450 451 rewind(fd); 452 453 sz = (filesize <= SIZE_MAX ? filesize : SIZE_MAX) / 25; 454 if (sz < 100) 455 sz = 100; 456 457 p = xcalloc(sz + 3, sizeof(*p)); 458 for (j = 0; (h = readhash(fd, flags));) { 459 if (j == sz) { 460 sz = sz * 3 / 2; 461 p = xrealloc(p, sz + 3, sizeof(*p)); 462 } 463 p[++j].value = h; 464 } 465 len[i] = j; 466 file[i] = p; 467 } 468 469 static void 470 prune(void) 471 { 472 int i, j; 473 474 for (pref = 0; pref < len[0] && pref < len[1] && 475 file[0][pref + 1].value == file[1][pref + 1].value; 476 pref++) 477 ; 478 for (suff = 0; suff < len[0] - pref && suff < len[1] - pref && 479 file[0][len[0] - suff].value == file[1][len[1] - suff].value; 480 suff++) 481 ; 482 for (j = 0; j < 2; j++) { 483 sfile[j] = file[j] + pref; 484 slen[j] = len[j] - pref - suff; 485 for (i = 0; i <= slen[j]; i++) 486 sfile[j][i].serial = i; 487 } 488 } 489 490 static void 491 equiv(struct line *a, int n, struct line *b, int m, int *c) 492 { 493 int i, j; 494 495 i = j = 1; 496 while (i <= n && j <= m) { 497 if (a[i].value < b[j].value) 498 a[i++].value = 0; 499 else if (a[i].value == b[j].value) 500 a[i++].value = j; 501 else 502 j++; 503 } 504 while (i <= n) 505 a[i++].value = 0; 506 b[m + 1].value = 0; 507 j = 0; 508 while (++j <= m) { 509 c[j] = -b[j].serial; 510 while (b[j + 1].value == b[j].value) { 511 j++; 512 c[j] = b[j].serial; 513 } 514 } 515 c[j] = -1; 516 } 517 518 /* Code taken from ping.c */ 519 static int 520 isqrt(int n) 521 { 522 int y, x = 1; 523 524 if (n == 0) 525 return (0); 526 527 do { /* newton was a stinker */ 528 y = x; 529 x = n / x; 530 x += y; 531 x /= 2; 532 } while ((x - y) > 1 || (x - y) < -1); 533 534 return (x); 535 } 536 537 static int 538 stone(int *a, int n, int *b, int *c, int flags) 539 { 540 int i, k, y, j, l; 541 int oldc, tc, oldl, sq; 542 u_int numtries, bound; 543 544 if (flags & D_MINIMAL) 545 bound = UINT_MAX; 546 else { 547 sq = isqrt(n); 548 bound = MAX(256, sq); 549 } 550 551 k = 0; 552 c[0] = newcand(0, 0, 0); 553 for (i = 1; i <= n; i++) { 554 j = a[i]; 555 if (j == 0) 556 continue; 557 y = -b[j]; 558 oldl = 0; 559 oldc = c[0]; 560 numtries = 0; 561 do { 562 if (y <= clist[oldc].y) 563 continue; 564 l = search(c, k, y); 565 if (l != oldl + 1) 566 oldc = c[l - 1]; 567 if (l <= k) { 568 if (clist[c[l]].y <= y) 569 continue; 570 tc = c[l]; 571 c[l] = newcand(i, y, oldc); 572 oldc = tc; 573 oldl = l; 574 numtries++; 575 } else { 576 c[l] = newcand(i, y, oldc); 577 k++; 578 break; 579 } 580 } while ((y = b[++j]) > 0 && numtries < bound); 581 } 582 return (k); 583 } 584 585 static int 586 newcand(int x, int y, int pred) 587 { 588 struct cand *q; 589 590 if (clen == clistlen) { 591 clistlen = clistlen * 11 / 10; 592 clist = xrealloc(clist, clistlen, sizeof(*clist)); 593 } 594 q = clist + clen; 595 q->x = x; 596 q->y = y; 597 q->pred = pred; 598 return (clen++); 599 } 600 601 static int 602 search(int *c, int k, int y) 603 { 604 int i, j, l, t; 605 606 if (clist[c[k]].y < y) /* quick look for typical case */ 607 return (k + 1); 608 i = 0; 609 j = k + 1; 610 for (;;) { 611 l = (i + j) / 2; 612 if (l <= i) 613 break; 614 t = clist[c[l]].y; 615 if (t > y) 616 j = l; 617 else if (t < y) 618 i = l; 619 else 620 return (l); 621 } 622 return (l + 1); 623 } 624 625 static void 626 unravel(int p) 627 { 628 struct cand *q; 629 int i; 630 631 for (i = 0; i <= len[0]; i++) 632 J[i] = i <= pref ? i : 633 i > len[0] - suff ? i + len[1] - len[0] : 0; 634 for (q = clist + p; q->y != 0; q = clist + q->pred) 635 J[q->x + pref] = q->y + pref; 636 } 637 638 /* 639 * Check does double duty: 640 * 1. ferret out any fortuitous correspondences due 641 * to confounding by hashing (which result in "jackpot") 642 * 2. collect random access indexes to the two files 643 */ 644 static void 645 check(FILE *f1, FILE *f2, int flags) 646 { 647 int i, j, jackpot, c, d; 648 long ctold, ctnew; 649 650 rewind(f1); 651 rewind(f2); 652 j = 1; 653 ixold[0] = ixnew[0] = 0; 654 jackpot = 0; 655 ctold = ctnew = 0; 656 for (i = 1; i <= len[0]; i++) { 657 if (J[i] == 0) { 658 ixold[i] = ctold += skipline(f1); 659 continue; 660 } 661 while (j < J[i]) { 662 ixnew[j] = ctnew += skipline(f2); 663 j++; 664 } 665 if (flags & (D_FOLDBLANKS|D_IGNOREBLANKS|D_IGNORECASE)) { 666 for (;;) { 667 c = getc(f1); 668 d = getc(f2); 669 /* 670 * GNU diff ignores a missing newline 671 * in one file for -b or -w. 672 */ 673 if ((flags & (D_FOLDBLANKS|D_IGNOREBLANKS)) && 674 ((c == EOF && d == '\n') || 675 (c == '\n' && d == EOF))) { 676 break; 677 } 678 ctold++; 679 ctnew++; 680 if ((flags & D_FOLDBLANKS) && isspace(c) && 681 isspace(d)) { 682 do { 683 if (c == '\n') 684 break; 685 ctold++; 686 } while (isspace(c = getc(f1))); 687 do { 688 if (d == '\n') 689 break; 690 ctnew++; 691 } while (isspace(d = getc(f2))); 692 } else if ((flags & D_IGNOREBLANKS)) { 693 while (isspace(c) && c != '\n') { 694 c = getc(f1); 695 ctold++; 696 } 697 while (isspace(d) && d != '\n') { 698 d = getc(f2); 699 ctnew++; 700 } 701 } 702 if (chrtran[c] != chrtran[d]) { 703 jackpot++; 704 J[i] = 0; 705 if (c != '\n' && c != EOF) 706 ctold += skipline(f1); 707 if (d != '\n' && c != EOF) 708 ctnew += skipline(f2); 709 break; 710 } 711 if (c == '\n' || c == EOF) 712 break; 713 } 714 } else { 715 for (;;) { 716 ctold++; 717 ctnew++; 718 if ((c = getc(f1)) != (d = getc(f2))) { 719 /* jackpot++; */ 720 J[i] = 0; 721 if (c != '\n' && c != EOF) 722 ctold += skipline(f1); 723 if (d != '\n' && c != EOF) 724 ctnew += skipline(f2); 725 break; 726 } 727 if (c == '\n' || c == EOF) 728 break; 729 } 730 } 731 ixold[i] = ctold; 732 ixnew[j] = ctnew; 733 j++; 734 } 735 for (; j <= len[1]; j++) 736 ixnew[j] = ctnew += skipline(f2); 737 /* 738 * if (jackpot) 739 * fprintf(stderr, "jackpot\n"); 740 */ 741 } 742 743 /* shellsort CACM #201 */ 744 static void 745 sort(struct line *a, int n) 746 { 747 struct line *ai, *aim, w; 748 int j, m = 0, k; 749 750 if (n == 0) 751 return; 752 for (j = 1; j <= n; j *= 2) 753 m = 2 * j - 1; 754 for (m /= 2; m != 0; m /= 2) { 755 k = n - m; 756 for (j = 1; j <= k; j++) { 757 for (ai = &a[j]; ai > a; ai -= m) { 758 aim = &ai[m]; 759 if (aim < ai) 760 break; /* wraparound */ 761 if (aim->value > ai[0].value || 762 (aim->value == ai[0].value && 763 aim->serial > ai[0].serial)) 764 break; 765 w.value = ai[0].value; 766 ai[0].value = aim->value; 767 aim->value = w.value; 768 w.serial = ai[0].serial; 769 ai[0].serial = aim->serial; 770 aim->serial = w.serial; 771 } 772 } 773 } 774 } 775 776 static void 777 unsort(struct line *f, int l, int *b) 778 { 779 int *a, i; 780 781 a = xcalloc(l + 1, sizeof(*a)); 782 for (i = 1; i <= l; i++) 783 a[f[i].serial] = f[i].value; 784 for (i = 1; i <= l; i++) 785 b[i] = a[i]; 786 xfree(a); 787 } 788 789 static int 790 skipline(FILE *f) 791 { 792 int i, c; 793 794 for (i = 1; (c = getc(f)) != '\n' && c != EOF; i++) 795 continue; 796 return (i); 797 } 798 799 static void 800 output(FILE *f1, FILE *f2, int flags) 801 { 802 int m, i0, i1, j0, j1; 803 804 rewind(f1); 805 rewind(f2); 806 m = len[0]; 807 J[0] = 0; 808 J[m + 1] = len[1] + 1; 809 for (i0 = 1; i0 <= m; i0 = i1 + 1) { 810 while (i0 <= m && J[i0] == J[i0 - 1] + 1) 811 i0++; 812 j0 = J[i0 - 1] + 1; 813 i1 = i0 - 1; 814 while (i1 < m && J[i1 + 1] == 0) 815 i1++; 816 j1 = J[i1 + 1] - 1; 817 J[i1] = j1; 818 change(f1, f2, i0, i1, j0, j1, flags); 819 } 820 if (m == 0) 821 change(f1, f2, 1, 0, 1, len[1], flags); 822 if (diff_format == D_IFDEF) { 823 for (;;) { 824 #define c i0 825 if ((c = getc(f1)) == EOF) 826 return; 827 diff_output("%c", c); 828 } 829 #undef c 830 } 831 if (anychange != 0) { 832 if (diff_format == D_CONTEXT) 833 dump_context_vec(f1, f2, flags); 834 else if (diff_format == D_UNIFIED) 835 dump_unified_vec(f1, f2, flags); 836 } 837 } 838 839 static void 840 range(int a, int b, char *separator) 841 { 842 diff_output("%d", a > b ? b : a); 843 if (a < b) 844 diff_output("%s%d", separator, b); 845 } 846 847 static void 848 uni_range(int a, int b) 849 { 850 if (a < b) 851 diff_output("%d,%d", a, b - a + 1); 852 else if (a == b) 853 diff_output("%d", b); 854 else 855 diff_output("%d,0", b); 856 } 857 858 static char * 859 preadline(int fd, size_t rlen, off_t off) 860 { 861 char *line; 862 ssize_t nr; 863 864 line = xmalloc(rlen + 1); 865 if ((nr = pread(fd, line, rlen, off)) < 0) 866 fatal("preadline: %s", strerror(errno)); 867 line[nr] = '\0'; 868 return (line); 869 } 870 871 static int 872 ignoreline(char *line) 873 { 874 int ret; 875 876 ret = regexec(&ignore_re, line, 0, NULL, 0); 877 xfree(line); 878 return (ret == 0); /* if it matched, it should be ignored. */ 879 } 880 881 static void 882 diff_head(void) 883 { 884 char buf[64]; 885 struct tm t; 886 time_t curr_time; 887 888 if (diff_rev1 != NULL) { 889 gmtime_r(&stb1.st_mtime, &t); 890 } else { 891 time(&curr_time); 892 localtime_r(&curr_time, &t); 893 } 894 895 (void)strftime(buf, sizeof(buf), "%b %G %H:%M:%S -0000", &t); 896 diff_output("%s %s %d %s", diff_format == D_CONTEXT ? 897 "***" : "---", diff_file1, t.tm_mday, buf); 898 899 if (diff_rev1 != NULL) { 900 rcsnum_tostr(diff_rev1, buf, sizeof(buf)); 901 diff_output("\t%s", buf); 902 } 903 904 diff_output("\n"); 905 906 gmtime_r(&stb2.st_mtime, &t); 907 908 (void)strftime(buf, sizeof(buf), "%b %G %H:%M:%S -0000", &t); 909 diff_output("%s %s %d %s", diff_format == D_CONTEXT ? 910 "---" : "+++", diff_file2, t.tm_mday, buf); 911 912 if (diff_rev2 != NULL) { 913 rcsnum_tostr(diff_rev2, buf, sizeof(buf)); 914 diff_output("\t%s", buf); 915 } 916 917 diff_output("\n"); 918 } 919 920 static void 921 rdiff_head(void) 922 { 923 char buf[64]; 924 struct tm t; 925 time_t curr_time; 926 927 diff_output("%s ", diff_format == D_CONTEXT ? "***" : "---"); 928 929 if (diff_rev1 == NULL) { 930 diff_output("%s", CVS_PATH_DEVNULL); 931 gmtime_r(&stb1.st_atime, &t); 932 } else { 933 rcsnum_tostr(diff_rev1, buf, sizeof(buf)); 934 diff_output("%s:%s", diff_file1, buf); 935 localtime_r(&stb1.st_mtime, &t); 936 } 937 938 (void)strftime(buf, sizeof(buf), "%a %b %e %H:%M:%S %G", &t); 939 diff_output("\t%s\n", buf); 940 941 if (diff_rev2 != NULL) { 942 localtime_r(&stb2.st_mtime, &t); 943 } else { 944 time(&curr_time); 945 localtime_r(&curr_time, &t); 946 } 947 948 (void)strftime(buf, sizeof(buf), "%a %b %e %H:%M:%S %G", &t); 949 950 diff_output("%s %s %s\n", diff_format == D_CONTEXT ? "---" : "+++", 951 diff_file2, buf); 952 } 953 954 /* 955 * Indicate that there is a difference between lines a and b of the from file 956 * to get to lines c to d of the to file. If a is greater then b then there 957 * are no lines in the from file involved and this means that there were 958 * lines appended (beginning at b). If c is greater than d then there are 959 * lines missing from the to file. 960 */ 961 static void 962 change(FILE *f1, FILE *f2, int a, int b, int c, int d, int flags) 963 { 964 static size_t max_context = 64; 965 int i; 966 967 if (diff_format != D_IFDEF && a > b && c > d) 968 return; 969 if (ignore_pats != NULL) { 970 char *line; 971 /* 972 * All lines in the change, insert, or delete must 973 * match an ignore pattern for the change to be 974 * ignored. 975 */ 976 if (a <= b) { /* Changes and deletes. */ 977 for (i = a; i <= b; i++) { 978 line = preadline(fileno(f1), 979 ixold[i] - ixold[i - 1], ixold[i - 1]); 980 if (!ignoreline(line)) 981 goto proceed; 982 } 983 } 984 if (a > b || c <= d) { /* Changes and inserts. */ 985 for (i = c; i <= d; i++) { 986 line = preadline(fileno(f2), 987 ixnew[i] - ixnew[i - 1], ixnew[i - 1]); 988 if (!ignoreline(line)) 989 goto proceed; 990 } 991 } 992 return; 993 } 994 proceed: 995 if (diff_format == D_CONTEXT || diff_format == D_UNIFIED) { 996 /* 997 * Allocate change records as needed. 998 */ 999 if (context_vec_ptr == context_vec_end - 1) { 1000 ptrdiff_t offset = context_vec_ptr - context_vec_start; 1001 max_context <<= 1; 1002 context_vec_start = xrealloc(context_vec_start, 1003 max_context, sizeof(*context_vec_start)); 1004 context_vec_end = context_vec_start + max_context; 1005 context_vec_ptr = context_vec_start + offset; 1006 } 1007 if (anychange == 0) { 1008 /* 1009 * Print the context/unidiff header first time through. 1010 */ 1011 if (cvs_cmdop == CVS_OP_RDIFF) 1012 rdiff_head(); 1013 else 1014 diff_head(); 1015 1016 anychange = 1; 1017 } else if (a > context_vec_ptr->b + (2 * diff_context) + 1 && 1018 c > context_vec_ptr->d + (2 * diff_context) + 1) { 1019 /* 1020 * If this change is more than 'context' lines from the 1021 * previous change, dump the record and reset it. 1022 */ 1023 if (diff_format == D_CONTEXT) 1024 dump_context_vec(f1, f2, flags); 1025 else 1026 dump_unified_vec(f1, f2, flags); 1027 } 1028 context_vec_ptr++; 1029 context_vec_ptr->a = a; 1030 context_vec_ptr->b = b; 1031 context_vec_ptr->c = c; 1032 context_vec_ptr->d = d; 1033 return; 1034 } 1035 if (anychange == 0) 1036 anychange = 1; 1037 switch (diff_format) { 1038 case D_BRIEF: 1039 return; 1040 case D_NORMAL: 1041 range(a, b, ","); 1042 diff_output("%c", a > b ? 'a' : c > d ? 'd' : 'c'); 1043 if (diff_format == D_NORMAL) 1044 range(c, d, ","); 1045 diff_output("\n"); 1046 break; 1047 case D_RCSDIFF: 1048 if (a > b) 1049 diff_output("a%d %d\n", b, d - c + 1); 1050 else { 1051 diff_output("d%d %d\n", a, b - a + 1); 1052 1053 if (!(c > d)) /* add changed lines */ 1054 diff_output("a%d %d\n", b, d - c + 1); 1055 } 1056 break; 1057 } 1058 if (diff_format == D_NORMAL || diff_format == D_IFDEF) { 1059 fetch(ixold, a, b, f1, '<', 1, flags); 1060 if (a <= b && c <= d && diff_format == D_NORMAL) 1061 diff_output("---\n"); 1062 } 1063 fetch(ixnew, c, d, f2, diff_format == D_NORMAL ? '>' : '\0', 0, flags); 1064 if (inifdef) { 1065 diff_output("#endif /* %s */\n", ifdefname); 1066 inifdef = 0; 1067 } 1068 } 1069 1070 static void 1071 fetch(long *f, int a, int b, FILE *lb, int ch, int oldfile, int flags) 1072 { 1073 long j, nc; 1074 int i, c, col; 1075 1076 /* 1077 * When doing #ifdef's, copy down to current line 1078 * if this is the first file, so that stuff makes it to output. 1079 */ 1080 if (diff_format == D_IFDEF && oldfile) { 1081 long curpos = ftell(lb); 1082 /* print through if append (a>b), else to (nb: 0 vs 1 orig) */ 1083 nc = f[a > b ? b : a - 1] - curpos; 1084 for (i = 0; i < nc; i++) 1085 diff_output("%c", getc(lb)); 1086 } 1087 if (a > b) 1088 return; 1089 if (diff_format == D_IFDEF) { 1090 if (inifdef) { 1091 diff_output("#else /* %s%s */\n", 1092 oldfile == 1 ? "!" : "", ifdefname); 1093 } else { 1094 if (oldfile) 1095 diff_output("#ifndef %s\n", ifdefname); 1096 else 1097 diff_output("#ifdef %s\n", ifdefname); 1098 } 1099 inifdef = 1 + oldfile; 1100 } 1101 for (i = a; i <= b; i++) { 1102 fseek(lb, f[i - 1], SEEK_SET); 1103 nc = f[i] - f[i - 1]; 1104 if (diff_format != D_IFDEF && ch != '\0') { 1105 diff_output("%c", ch); 1106 if (Tflag == 1 && (diff_format == D_NORMAL || 1107 diff_format == D_CONTEXT || 1108 diff_format == D_UNIFIED)) 1109 diff_output("\t"); 1110 else if (diff_format != D_UNIFIED) 1111 diff_output(" "); 1112 } 1113 col = 0; 1114 for (j = 0; j < nc; j++) { 1115 if ((c = getc(lb)) == EOF) { 1116 if (diff_format == D_RCSDIFF) 1117 cvs_log(LP_ERR, 1118 "No newline at end of file"); 1119 else 1120 diff_output("\n\\ No newline at end of " 1121 "file\n"); 1122 return; 1123 } 1124 if (c == '\t' && (flags & D_EXPANDTABS)) { 1125 do { 1126 diff_output(" "); 1127 } while (++col & 7); 1128 } else { 1129 diff_output("%c", c); 1130 col++; 1131 } 1132 } 1133 } 1134 } 1135 1136 /* 1137 * Hash function taken from Robert Sedgewick, Algorithms in C, 3d ed., p 578. 1138 */ 1139 static int 1140 readhash(FILE *f, int flags) 1141 { 1142 int i, t, space; 1143 int sum; 1144 1145 sum = 1; 1146 space = 0; 1147 if ((flags & (D_FOLDBLANKS|D_IGNOREBLANKS)) == 0) { 1148 if (flags & D_IGNORECASE) 1149 for (i = 0; (t = getc(f)) != '\n'; i++) { 1150 if (t == EOF) { 1151 if (i == 0) 1152 return (0); 1153 break; 1154 } 1155 sum = sum * 127 + chrtran[t]; 1156 } 1157 else 1158 for (i = 0; (t = getc(f)) != '\n'; i++) { 1159 if (t == EOF) { 1160 if (i == 0) 1161 return (0); 1162 break; 1163 } 1164 sum = sum * 127 + t; 1165 } 1166 } else { 1167 for (i = 0;;) { 1168 switch (t = getc(f)) { 1169 case '\t': 1170 case '\r': 1171 case '\v': 1172 case '\f': 1173 case ' ': 1174 space++; 1175 continue; 1176 default: 1177 if (space && (flags & D_IGNOREBLANKS) == 0) { 1178 i++; 1179 space = 0; 1180 } 1181 sum = sum * 127 + chrtran[t]; 1182 i++; 1183 continue; 1184 case EOF: 1185 if (i == 0) 1186 return (0); 1187 /* FALLTHROUGH */ 1188 case '\n': 1189 break; 1190 } 1191 break; 1192 } 1193 } 1194 /* 1195 * There is a remote possibility that we end up with a zero sum. 1196 * Zero is used as an EOF marker, so return 1 instead. 1197 */ 1198 return (sum == 0 ? 1 : sum); 1199 } 1200 1201 static int 1202 asciifile(FILE *f) 1203 { 1204 unsigned char buf[BUFSIZ]; 1205 size_t i, cnt; 1206 1207 if (f == NULL) 1208 return (1); 1209 1210 rewind(f); 1211 cnt = fread(buf, 1, sizeof(buf), f); 1212 for (i = 0; i < cnt; i++) 1213 if (!isprint(buf[i]) && !isspace(buf[i])) 1214 return (0); 1215 return (1); 1216 } 1217 1218 #define begins_with(s, pre) (strncmp(s, pre, sizeof(pre)-1) == 0) 1219 1220 static char * 1221 match_function(const long *f, int pos, FILE *fp) 1222 { 1223 unsigned char buf[FUNCTION_CONTEXT_SIZE]; 1224 size_t nc; 1225 int last = lastline; 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 buf[strcspn(buf, "\n")] = '\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, sizeof lastbuf); 1250 if (state) 1251 strlcat(lastbuf, state, 1252 sizeof lastbuf); 1253 lastmatchline = pos; 1254 return lastbuf; 1255 } 1256 } 1257 } 1258 pos--; 1259 } 1260 return lastmatchline > 0 ? lastbuf : NULL; 1261 } 1262 1263 /* dump accumulated "context" diff changes */ 1264 static void 1265 dump_context_vec(FILE *f1, FILE *f2, int flags) 1266 { 1267 struct context_vec *cvp = context_vec_start; 1268 int lowa, upb, lowc, upd, do_output; 1269 int a, b, c, d; 1270 char ch, *f; 1271 1272 if (context_vec_start > context_vec_ptr) 1273 return; 1274 1275 b = d = 0; /* gcc */ 1276 lowa = MAX(1, cvp->a - diff_context); 1277 upb = MIN(len[0], context_vec_ptr->b + diff_context); 1278 lowc = MAX(1, cvp->c - diff_context); 1279 upd = MIN(len[1], context_vec_ptr->d + diff_context); 1280 1281 diff_output("***************"); 1282 if ((flags & D_PROTOTYPE)) { 1283 f = match_function(ixold, lowa-1, f1); 1284 if (f != NULL) 1285 diff_output(" %s", f); 1286 } 1287 diff_output("\n*** "); 1288 range(lowa, upb, ","); 1289 diff_output(" ****\n"); 1290 1291 /* 1292 * Output changes to the "old" file. The first loop suppresses 1293 * output if there were no changes to the "old" file (we'll see 1294 * the "old" lines as context in the "new" list). 1295 */ 1296 do_output = 0; 1297 for (; cvp <= context_vec_ptr; cvp++) 1298 if (cvp->a <= cvp->b) { 1299 cvp = context_vec_start; 1300 do_output++; 1301 break; 1302 } 1303 if (do_output) { 1304 while (cvp <= context_vec_ptr) { 1305 a = cvp->a; 1306 b = cvp->b; 1307 c = cvp->c; 1308 d = cvp->d; 1309 1310 if (a <= b && c <= d) 1311 ch = 'c'; 1312 else 1313 ch = (a <= b) ? 'd' : 'a'; 1314 1315 if (ch == 'a') 1316 fetch(ixold, lowa, b, f1, ' ', 0, flags); 1317 else { 1318 fetch(ixold, lowa, a - 1, f1, ' ', 0, flags); 1319 fetch(ixold, a, b, f1, 1320 ch == 'c' ? '!' : '-', 0, flags); 1321 } 1322 lowa = b + 1; 1323 cvp++; 1324 } 1325 fetch(ixold, b + 1, upb, f1, ' ', 0, flags); 1326 } 1327 /* output changes to the "new" file */ 1328 diff_output("--- "); 1329 range(lowc, upd, ","); 1330 diff_output(" ----\n"); 1331 1332 do_output = 0; 1333 for (cvp = context_vec_start; cvp <= context_vec_ptr; cvp++) 1334 if (cvp->c <= cvp->d) { 1335 cvp = context_vec_start; 1336 do_output++; 1337 break; 1338 } 1339 if (do_output) { 1340 while (cvp <= context_vec_ptr) { 1341 a = cvp->a; 1342 b = cvp->b; 1343 c = cvp->c; 1344 d = cvp->d; 1345 1346 if (a <= b && c <= d) 1347 ch = 'c'; 1348 else 1349 ch = (a <= b) ? 'd' : 'a'; 1350 1351 if (ch == 'd') 1352 fetch(ixnew, lowc, d, f2, ' ', 0, flags); 1353 else { 1354 fetch(ixnew, lowc, c - 1, f2, ' ', 0, flags); 1355 fetch(ixnew, c, d, f2, 1356 ch == 'c' ? '!' : '+', 0, flags); 1357 } 1358 lowc = d + 1; 1359 cvp++; 1360 } 1361 fetch(ixnew, d + 1, upd, f2, ' ', 0, flags); 1362 } 1363 context_vec_ptr = context_vec_start - 1; 1364 } 1365 1366 /* dump accumulated "unified" diff changes */ 1367 static void 1368 dump_unified_vec(FILE *f1, FILE *f2, int flags) 1369 { 1370 struct context_vec *cvp = context_vec_start; 1371 int lowa, upb, lowc, upd; 1372 int a, b, c, d; 1373 char ch, *f; 1374 1375 if (context_vec_start > context_vec_ptr) 1376 return; 1377 1378 b = d = 0; /* gcc */ 1379 lowa = MAX(1, cvp->a - diff_context); 1380 upb = MIN(len[0], context_vec_ptr->b + diff_context); 1381 lowc = MAX(1, cvp->c - diff_context); 1382 upd = MIN(len[1], context_vec_ptr->d + diff_context); 1383 1384 diff_output("@@ -"); 1385 uni_range(lowa, upb); 1386 diff_output(" +"); 1387 uni_range(lowc, upd); 1388 diff_output(" @@"); 1389 if ((flags & D_PROTOTYPE)) { 1390 f = match_function(ixold, lowa-1, f1); 1391 if (f != NULL) 1392 diff_output(" %s", f); 1393 } 1394 diff_output("\n"); 1395 1396 /* 1397 * Output changes in "unified" diff format--the old and new lines 1398 * are printed together. 1399 */ 1400 for (; cvp <= context_vec_ptr; cvp++) { 1401 a = cvp->a; 1402 b = cvp->b; 1403 c = cvp->c; 1404 d = cvp->d; 1405 1406 /* 1407 * c: both new and old changes 1408 * d: only changes in the old file 1409 * a: only changes in the new file 1410 */ 1411 if (a <= b && c <= d) 1412 ch = 'c'; 1413 else 1414 ch = (a <= b) ? 'd' : 'a'; 1415 1416 switch (ch) { 1417 case 'c': 1418 fetch(ixold, lowa, a - 1, f1, ' ', 0, flags); 1419 fetch(ixold, a, b, f1, '-', 0, flags); 1420 fetch(ixnew, c, d, f2, '+', 0, flags); 1421 break; 1422 case 'd': 1423 fetch(ixold, lowa, a - 1, f1, ' ', 0, flags); 1424 fetch(ixold, a, b, f1, '-', 0, flags); 1425 break; 1426 case 'a': 1427 fetch(ixnew, lowc, c - 1, f2, ' ', 0, flags); 1428 fetch(ixnew, c, d, f2, '+', 0, flags); 1429 break; 1430 } 1431 lowa = b + 1; 1432 lowc = d + 1; 1433 } 1434 fetch(ixnew, d + 1, upd, f2, ' ', 0, flags); 1435 1436 context_vec_ptr = context_vec_start - 1; 1437 } 1438 1439 void 1440 diff_output(const char *fmt, ...) 1441 { 1442 va_list vap; 1443 int i; 1444 char *str; 1445 1446 va_start(vap, fmt); 1447 i = vasprintf(&str, fmt, vap); 1448 va_end(vap); 1449 if (i == -1) 1450 fatal("diff_output: could not allocate memory"); 1451 if (diffbuf != NULL) 1452 buf_puts(diffbuf, str); 1453 else 1454 cvs_printf("%s", str); 1455 xfree(str); 1456 } 1457