1 /* $OpenBSD: diff_internals.c,v 1.33 2010/07/28 21:19:30 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; 542 u_int numtries; 543 544 /* XXX move the isqrt() out of the macro to avoid multiple calls */ 545 const u_int bound = (flags & D_MINIMAL) ? UINT_MAX : 546 MAX(256, isqrt(n)); 547 548 k = 0; 549 c[0] = newcand(0, 0, 0); 550 for (i = 1; i <= n; i++) { 551 j = a[i]; 552 if (j == 0) 553 continue; 554 y = -b[j]; 555 oldl = 0; 556 oldc = c[0]; 557 numtries = 0; 558 do { 559 if (y <= clist[oldc].y) 560 continue; 561 l = search(c, k, y); 562 if (l != oldl + 1) 563 oldc = c[l - 1]; 564 if (l <= k) { 565 if (clist[c[l]].y <= y) 566 continue; 567 tc = c[l]; 568 c[l] = newcand(i, y, oldc); 569 oldc = tc; 570 oldl = l; 571 numtries++; 572 } else { 573 c[l] = newcand(i, y, oldc); 574 k++; 575 break; 576 } 577 } while ((y = b[++j]) > 0 && numtries < bound); 578 } 579 return (k); 580 } 581 582 static int 583 newcand(int x, int y, int pred) 584 { 585 struct cand *q; 586 587 if (clen == clistlen) { 588 clistlen = clistlen * 11 / 10; 589 clist = xrealloc(clist, clistlen, sizeof(*clist)); 590 } 591 q = clist + clen; 592 q->x = x; 593 q->y = y; 594 q->pred = pred; 595 return (clen++); 596 } 597 598 static int 599 search(int *c, int k, int y) 600 { 601 int i, j, l, t; 602 603 if (clist[c[k]].y < y) /* quick look for typical case */ 604 return (k + 1); 605 i = 0; 606 j = k + 1; 607 for (;;) { 608 l = (i + j) / 2; 609 if (l <= i) 610 break; 611 t = clist[c[l]].y; 612 if (t > y) 613 j = l; 614 else if (t < y) 615 i = l; 616 else 617 return (l); 618 } 619 return (l + 1); 620 } 621 622 static void 623 unravel(int p) 624 { 625 struct cand *q; 626 int i; 627 628 for (i = 0; i <= len[0]; i++) 629 J[i] = i <= pref ? i : 630 i > len[0] - suff ? i + len[1] - len[0] : 0; 631 for (q = clist + p; q->y != 0; q = clist + q->pred) 632 J[q->x + pref] = q->y + pref; 633 } 634 635 /* 636 * Check does double duty: 637 * 1. ferret out any fortuitous correspondences due 638 * to confounding by hashing (which result in "jackpot") 639 * 2. collect random access indexes to the two files 640 */ 641 static void 642 check(FILE *f1, FILE *f2, int flags) 643 { 644 int i, j, jackpot, c, d; 645 long ctold, ctnew; 646 647 rewind(f1); 648 rewind(f2); 649 j = 1; 650 ixold[0] = ixnew[0] = 0; 651 jackpot = 0; 652 ctold = ctnew = 0; 653 for (i = 1; i <= len[0]; i++) { 654 if (J[i] == 0) { 655 ixold[i] = ctold += skipline(f1); 656 continue; 657 } 658 while (j < J[i]) { 659 ixnew[j] = ctnew += skipline(f2); 660 j++; 661 } 662 if (flags & (D_FOLDBLANKS|D_IGNOREBLANKS|D_IGNORECASE)) { 663 for (;;) { 664 c = getc(f1); 665 d = getc(f2); 666 /* 667 * GNU diff ignores a missing newline 668 * in one file for -b or -w. 669 */ 670 if ((flags & (D_FOLDBLANKS|D_IGNOREBLANKS)) && 671 ((c == EOF && d == '\n') || 672 (c == '\n' && d == EOF))) { 673 break; 674 } 675 ctold++; 676 ctnew++; 677 if ((flags & D_FOLDBLANKS) && isspace(c) && 678 isspace(d)) { 679 do { 680 if (c == '\n') 681 break; 682 ctold++; 683 } while (isspace(c = getc(f1))); 684 do { 685 if (d == '\n') 686 break; 687 ctnew++; 688 } while (isspace(d = getc(f2))); 689 } else if ((flags & D_IGNOREBLANKS)) { 690 while (isspace(c) && c != '\n') { 691 c = getc(f1); 692 ctold++; 693 } 694 while (isspace(d) && d != '\n') { 695 d = getc(f2); 696 ctnew++; 697 } 698 } 699 if (chrtran[c] != chrtran[d]) { 700 jackpot++; 701 J[i] = 0; 702 if (c != '\n' && c != EOF) 703 ctold += skipline(f1); 704 if (d != '\n' && c != EOF) 705 ctnew += skipline(f2); 706 break; 707 } 708 if (c == '\n' || c == EOF) 709 break; 710 } 711 } else { 712 for (;;) { 713 ctold++; 714 ctnew++; 715 if ((c = getc(f1)) != (d = getc(f2))) { 716 /* jackpot++; */ 717 J[i] = 0; 718 if (c != '\n' && c != EOF) 719 ctold += skipline(f1); 720 if (d != '\n' && c != EOF) 721 ctnew += skipline(f2); 722 break; 723 } 724 if (c == '\n' || c == EOF) 725 break; 726 } 727 } 728 ixold[i] = ctold; 729 ixnew[j] = ctnew; 730 j++; 731 } 732 for (; j <= len[1]; j++) 733 ixnew[j] = ctnew += skipline(f2); 734 /* 735 * if (jackpot) 736 * fprintf(stderr, "jackpot\n"); 737 */ 738 } 739 740 /* shellsort CACM #201 */ 741 static void 742 sort(struct line *a, int n) 743 { 744 struct line *ai, *aim, w; 745 int j, m = 0, k; 746 747 if (n == 0) 748 return; 749 for (j = 1; j <= n; j *= 2) 750 m = 2 * j - 1; 751 for (m /= 2; m != 0; m /= 2) { 752 k = n - m; 753 for (j = 1; j <= k; j++) { 754 for (ai = &a[j]; ai > a; ai -= m) { 755 aim = &ai[m]; 756 if (aim < ai) 757 break; /* wraparound */ 758 if (aim->value > ai[0].value || 759 (aim->value == ai[0].value && 760 aim->serial > ai[0].serial)) 761 break; 762 w.value = ai[0].value; 763 ai[0].value = aim->value; 764 aim->value = w.value; 765 w.serial = ai[0].serial; 766 ai[0].serial = aim->serial; 767 aim->serial = w.serial; 768 } 769 } 770 } 771 } 772 773 static void 774 unsort(struct line *f, int l, int *b) 775 { 776 int *a, i; 777 778 a = xcalloc(l + 1, sizeof(*a)); 779 for (i = 1; i <= l; i++) 780 a[f[i].serial] = f[i].value; 781 for (i = 1; i <= l; i++) 782 b[i] = a[i]; 783 xfree(a); 784 } 785 786 static int 787 skipline(FILE *f) 788 { 789 int i, c; 790 791 for (i = 1; (c = getc(f)) != '\n' && c != EOF; i++) 792 continue; 793 return (i); 794 } 795 796 static void 797 output(FILE *f1, FILE *f2, int flags) 798 { 799 int m, i0, i1, j0, j1; 800 801 rewind(f1); 802 rewind(f2); 803 m = len[0]; 804 J[0] = 0; 805 J[m + 1] = len[1] + 1; 806 for (i0 = 1; i0 <= m; i0 = i1 + 1) { 807 while (i0 <= m && J[i0] == J[i0 - 1] + 1) 808 i0++; 809 j0 = J[i0 - 1] + 1; 810 i1 = i0 - 1; 811 while (i1 < m && J[i1 + 1] == 0) 812 i1++; 813 j1 = J[i1 + 1] - 1; 814 J[i1] = j1; 815 change(f1, f2, i0, i1, j0, j1, flags); 816 } 817 if (m == 0) 818 change(f1, f2, 1, 0, 1, len[1], flags); 819 if (diff_format == D_IFDEF) { 820 for (;;) { 821 #define c i0 822 if ((c = getc(f1)) == EOF) 823 return; 824 diff_output("%c", c); 825 } 826 #undef c 827 } 828 if (anychange != 0) { 829 if (diff_format == D_CONTEXT) 830 dump_context_vec(f1, f2, flags); 831 else if (diff_format == D_UNIFIED) 832 dump_unified_vec(f1, f2, flags); 833 } 834 } 835 836 static void 837 range(int a, int b, char *separator) 838 { 839 diff_output("%d", a > b ? b : a); 840 if (a < b) 841 diff_output("%s%d", separator, b); 842 } 843 844 static void 845 uni_range(int a, int b) 846 { 847 if (a < b) 848 diff_output("%d,%d", a, b - a + 1); 849 else if (a == b) 850 diff_output("%d", b); 851 else 852 diff_output("%d,0", b); 853 } 854 855 static char * 856 preadline(int fd, size_t rlen, off_t off) 857 { 858 char *line; 859 ssize_t nr; 860 861 line = xmalloc(rlen + 1); 862 if ((nr = pread(fd, line, rlen, off)) < 0) 863 fatal("preadline: %s", strerror(errno)); 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, int flags) 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 * diff_context) + 1 && 1015 c > context_vec_ptr->d + (2 * diff_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, flags); 1022 else 1023 dump_unified_vec(f1, f2, flags); 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, flags); 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, flags); 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, int flags) 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' && (flags & D_EXPANDTABS)) { 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, int flags) 1138 { 1139 int i, t, space; 1140 int sum; 1141 1142 sum = 1; 1143 space = 0; 1144 if ((flags & (D_FOLDBLANKS|D_IGNOREBLANKS)) == 0) { 1145 if (flags & D_IGNORECASE) 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 && (flags & D_IGNOREBLANKS) == 0) { 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 (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 *state = NULL; 1224 1225 lastline = pos; 1226 while (pos > last) { 1227 fseek(fp, f[pos - 1], SEEK_SET); 1228 nc = f[pos] - f[pos - 1]; 1229 if (nc >= sizeof(buf)) 1230 nc = sizeof(buf) - 1; 1231 nc = fread(buf, 1, nc, fp); 1232 if (nc > 0) { 1233 buf[nc] = '\0'; 1234 buf[strcspn(buf, "\n")] = '\0'; 1235 if (isalpha(buf[0]) || buf[0] == '_' || buf[0] == '$') { 1236 if (begins_with(buf, "private:")) { 1237 if (!state) 1238 state = " (private)"; 1239 } else if (begins_with(buf, "protected:")) { 1240 if (!state) 1241 state = " (protected)"; 1242 } else if (begins_with(buf, "public:")) { 1243 if (!state) 1244 state = " (public)"; 1245 } else { 1246 strlcpy(lastbuf, buf, sizeof lastbuf); 1247 if (state) 1248 strlcat(lastbuf, state, 1249 sizeof lastbuf); 1250 lastmatchline = pos; 1251 return lastbuf; 1252 } 1253 } 1254 } 1255 pos--; 1256 } 1257 return lastmatchline > 0 ? lastbuf : NULL; 1258 } 1259 1260 /* dump accumulated "context" diff changes */ 1261 static void 1262 dump_context_vec(FILE *f1, FILE *f2, int flags) 1263 { 1264 struct context_vec *cvp = context_vec_start; 1265 int lowa, upb, lowc, upd, do_output; 1266 int a, b, c, d; 1267 char ch, *f; 1268 1269 if (context_vec_start > context_vec_ptr) 1270 return; 1271 1272 b = d = 0; /* gcc */ 1273 lowa = MAX(1, cvp->a - diff_context); 1274 upb = MIN(len[0], context_vec_ptr->b + diff_context); 1275 lowc = MAX(1, cvp->c - diff_context); 1276 upd = MIN(len[1], context_vec_ptr->d + diff_context); 1277 1278 diff_output("***************"); 1279 if ((flags & D_PROTOTYPE)) { 1280 f = match_function(ixold, lowa-1, f1); 1281 if (f != NULL) 1282 diff_output(" %s", f); 1283 } 1284 diff_output("\n*** "); 1285 range(lowa, upb, ","); 1286 diff_output(" ****\n"); 1287 1288 /* 1289 * Output changes to the "old" file. The first loop suppresses 1290 * output if there were no changes to the "old" file (we'll see 1291 * the "old" lines as context in the "new" list). 1292 */ 1293 do_output = 0; 1294 for (; cvp <= context_vec_ptr; cvp++) 1295 if (cvp->a <= cvp->b) { 1296 cvp = context_vec_start; 1297 do_output++; 1298 break; 1299 } 1300 if (do_output) { 1301 while (cvp <= context_vec_ptr) { 1302 a = cvp->a; 1303 b = cvp->b; 1304 c = cvp->c; 1305 d = cvp->d; 1306 1307 if (a <= b && c <= d) 1308 ch = 'c'; 1309 else 1310 ch = (a <= b) ? 'd' : 'a'; 1311 1312 if (ch == 'a') 1313 fetch(ixold, lowa, b, f1, ' ', 0, flags); 1314 else { 1315 fetch(ixold, lowa, a - 1, f1, ' ', 0, flags); 1316 fetch(ixold, a, b, f1, 1317 ch == 'c' ? '!' : '-', 0, flags); 1318 } 1319 lowa = b + 1; 1320 cvp++; 1321 } 1322 fetch(ixold, b + 1, upb, f1, ' ', 0, flags); 1323 } 1324 /* output changes to the "new" file */ 1325 diff_output("--- "); 1326 range(lowc, upd, ","); 1327 diff_output(" ----\n"); 1328 1329 do_output = 0; 1330 for (cvp = context_vec_start; cvp <= context_vec_ptr; cvp++) 1331 if (cvp->c <= cvp->d) { 1332 cvp = context_vec_start; 1333 do_output++; 1334 break; 1335 } 1336 if (do_output) { 1337 while (cvp <= context_vec_ptr) { 1338 a = cvp->a; 1339 b = cvp->b; 1340 c = cvp->c; 1341 d = cvp->d; 1342 1343 if (a <= b && c <= d) 1344 ch = 'c'; 1345 else 1346 ch = (a <= b) ? 'd' : 'a'; 1347 1348 if (ch == 'd') 1349 fetch(ixnew, lowc, d, f2, ' ', 0, flags); 1350 else { 1351 fetch(ixnew, lowc, c - 1, f2, ' ', 0, flags); 1352 fetch(ixnew, c, d, f2, 1353 ch == 'c' ? '!' : '+', 0, flags); 1354 } 1355 lowc = d + 1; 1356 cvp++; 1357 } 1358 fetch(ixnew, d + 1, upd, f2, ' ', 0, flags); 1359 } 1360 context_vec_ptr = context_vec_start - 1; 1361 } 1362 1363 /* dump accumulated "unified" diff changes */ 1364 static void 1365 dump_unified_vec(FILE *f1, FILE *f2, int flags) 1366 { 1367 struct context_vec *cvp = context_vec_start; 1368 int lowa, upb, lowc, upd; 1369 int a, b, c, d; 1370 char ch, *f; 1371 1372 if (context_vec_start > context_vec_ptr) 1373 return; 1374 1375 b = d = 0; /* gcc */ 1376 lowa = MAX(1, cvp->a - diff_context); 1377 upb = MIN(len[0], context_vec_ptr->b + diff_context); 1378 lowc = MAX(1, cvp->c - diff_context); 1379 upd = MIN(len[1], context_vec_ptr->d + diff_context); 1380 1381 diff_output("@@ -"); 1382 uni_range(lowa, upb); 1383 diff_output(" +"); 1384 uni_range(lowc, upd); 1385 diff_output(" @@"); 1386 if ((flags & D_PROTOTYPE)) { 1387 f = match_function(ixold, lowa-1, f1); 1388 if (f != NULL) 1389 diff_output(" %s", f); 1390 } 1391 diff_output("\n"); 1392 1393 /* 1394 * Output changes in "unified" diff format--the old and new lines 1395 * are printed together. 1396 */ 1397 for (; cvp <= context_vec_ptr; cvp++) { 1398 a = cvp->a; 1399 b = cvp->b; 1400 c = cvp->c; 1401 d = cvp->d; 1402 1403 /* 1404 * c: both new and old changes 1405 * d: only changes in the old file 1406 * a: only changes in the new file 1407 */ 1408 if (a <= b && c <= d) 1409 ch = 'c'; 1410 else 1411 ch = (a <= b) ? 'd' : 'a'; 1412 1413 switch (ch) { 1414 case 'c': 1415 fetch(ixold, lowa, a - 1, f1, ' ', 0, flags); 1416 fetch(ixold, a, b, f1, '-', 0, flags); 1417 fetch(ixnew, c, d, f2, '+', 0, flags); 1418 break; 1419 case 'd': 1420 fetch(ixold, lowa, a - 1, f1, ' ', 0, flags); 1421 fetch(ixold, a, b, f1, '-', 0, flags); 1422 break; 1423 case 'a': 1424 fetch(ixnew, lowc, c - 1, f2, ' ', 0, flags); 1425 fetch(ixnew, c, d, f2, '+', 0, flags); 1426 break; 1427 } 1428 lowa = b + 1; 1429 lowc = d + 1; 1430 } 1431 fetch(ixnew, d + 1, upd, f2, ' ', 0, flags); 1432 1433 context_vec_ptr = context_vec_start - 1; 1434 } 1435 1436 void 1437 diff_output(const char *fmt, ...) 1438 { 1439 va_list vap; 1440 int i; 1441 char *str; 1442 1443 va_start(vap, fmt); 1444 i = vasprintf(&str, fmt, vap); 1445 va_end(vap); 1446 if (i == -1) 1447 fatal("diff_output: could not allocate memory"); 1448 if (diffbuf != NULL) 1449 buf_puts(diffbuf, str); 1450 else 1451 cvs_printf("%s", str); 1452 xfree(str); 1453 } 1454