1 /* $OpenBSD: diff_internals.c,v 1.28 2009/06/07 08:39:13 ray 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 static int 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[128]; 208 static struct stat stb1, stb2; 209 static char *ifdefname, *ignore_pats; 210 regex_t ignore_re; 211 212 static int *J; /* will be overlaid on class */ 213 static int *class; /* will be overlaid on file[0] */ 214 static int *klist; /* will be overlaid on file[0] after class */ 215 static int *member; /* will be overlaid on file[1] */ 216 static int clen; 217 static int inifdef; /* whether or not we are in a #ifdef block */ 218 static int len[2]; 219 static int pref, suff; /* length of prefix and suffix */ 220 static int slen[2]; 221 static int anychange; 222 static long *ixnew; /* will be overlaid on file[1] */ 223 static long *ixold; /* will be overlaid on klist */ 224 static struct cand *clist; /* merely a free storage pot for candidates */ 225 static int clistlen; /* the length of clist */ 226 static struct line *sfile[2]; /* shortened by pruning common prefix/suffix */ 227 static u_char *chrtran; /* translation table for case-folding */ 228 static struct context_vec *context_vec_start; 229 static struct context_vec *context_vec_end; 230 static struct context_vec *context_vec_ptr; 231 232 #define FUNCTION_CONTEXT_SIZE 55 233 static char lastbuf[FUNCTION_CONTEXT_SIZE]; 234 static int lastline; 235 static int lastmatchline; 236 BUF *diffbuf = NULL; 237 238 239 /* 240 * chrtran points to one of 2 translation tables: cup2low if folding upper to 241 * lower case clow2low if not folding case 242 */ 243 u_char clow2low[256] = { 244 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 245 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 246 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20, 247 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b, 248 0x2c, 0x2d, 0x2e, 0x2f, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 249 0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, 0x40, 0x41, 250 0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49, 0x4a, 0x4b, 0x4c, 251 0x4d, 0x4e, 0x4f, 0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57, 252 0x58, 0x59, 0x5a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f, 0x60, 0x61, 0x62, 253 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 254 0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, 255 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x80, 0x81, 0x82, 0x83, 256 0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 257 0x8f, 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99, 258 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f, 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 259 0xa5, 0xa6, 0xa7, 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf, 260 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba, 261 0xbb, 0xbc, 0xbd, 0xbe, 0xbf, 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 262 0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, 0xd0, 263 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, 0xdb, 264 0xdc, 0xdd, 0xde, 0xdf, 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 265 0xe7, 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef, 0xf0, 0xf1, 266 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 267 0xfd, 0xfe, 0xff 268 }; 269 270 u_char cup2low[256] = { 271 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 272 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 273 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20, 274 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b, 275 0x2c, 0x2d, 0x2e, 0x2f, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 276 0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, 0x60, 0x61, 277 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 278 0x6d, 0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 279 0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x60, 0x61, 0x62, 280 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 281 0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, 282 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x80, 0x81, 0x82, 0x83, 283 0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 284 0x8f, 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99, 285 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f, 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 286 0xa5, 0xa6, 0xa7, 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf, 287 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba, 288 0xbb, 0xbc, 0xbd, 0xbe, 0xbf, 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 289 0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, 0xd0, 290 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, 0xdb, 291 0xdc, 0xdd, 0xde, 0xdf, 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 292 0xe7, 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef, 0xf0, 0xf1, 293 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 294 0xfd, 0xfe, 0xff 295 }; 296 297 int 298 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 != j) 434 return (1); 435 if (i == 0 && j == 0) { 436 if (ferror(f1) || ferror(f2)) 437 return (1); 438 return (0); 439 } 440 if (memcmp(buf1, buf2, i) != 0) 441 return (1); 442 } 443 } 444 445 static void 446 prepare(int i, FILE *fd, off_t filesize, int flags) 447 { 448 struct line *p; 449 int j, h; 450 size_t sz; 451 452 rewind(fd); 453 454 sz = (filesize <= SIZE_MAX ? filesize : SIZE_MAX) / 25; 455 if (sz < 100) 456 sz = 100; 457 458 p = xcalloc(sz + 3, sizeof(*p)); 459 for (j = 0; (h = readhash(fd, flags));) { 460 if (j == sz) { 461 sz = sz * 3 / 2; 462 p = xrealloc(p, sz + 3, sizeof(*p)); 463 } 464 p[++j].value = h; 465 } 466 len[i] = j; 467 file[i] = p; 468 } 469 470 static void 471 prune(void) 472 { 473 int i, j; 474 475 for (pref = 0; pref < len[0] && pref < len[1] && 476 file[0][pref + 1].value == file[1][pref + 1].value; 477 pref++) 478 ; 479 for (suff = 0; suff < len[0] - pref && suff < len[1] - pref && 480 file[0][len[0] - suff].value == file[1][len[1] - suff].value; 481 suff++) 482 ; 483 for (j = 0; j < 2; j++) { 484 sfile[j] = file[j] + pref; 485 slen[j] = len[j] - pref - suff; 486 for (i = 0; i <= slen[j]; i++) 487 sfile[j][i].serial = i; 488 } 489 } 490 491 static void 492 equiv(struct line *a, int n, struct line *b, int m, int *c) 493 { 494 int i, j; 495 496 i = j = 1; 497 while (i <= n && j <= m) { 498 if (a[i].value < b[j].value) 499 a[i++].value = 0; 500 else if (a[i].value == b[j].value) 501 a[i++].value = j; 502 else 503 j++; 504 } 505 while (i <= n) 506 a[i++].value = 0; 507 b[m + 1].value = 0; 508 j = 0; 509 while (++j <= m) { 510 c[j] = -b[j].serial; 511 while (b[j + 1].value == b[j].value) { 512 j++; 513 c[j] = b[j].serial; 514 } 515 } 516 c[j] = -1; 517 } 518 519 /* Code taken from ping.c */ 520 static int 521 isqrt(int n) 522 { 523 int y, x = 1; 524 525 if (n == 0) 526 return (0); 527 528 do { /* newton was a stinker */ 529 y = x; 530 x = n / x; 531 x += y; 532 x /= 2; 533 } while ((x - y) > 1 || (x - y) < -1); 534 535 return (x); 536 } 537 538 static int 539 stone(int *a, int n, int *b, int *c, int flags) 540 { 541 int i, k, y, j, l; 542 int oldc, tc, oldl; 543 u_int numtries; 544 545 /* XXX move the isqrt() out of the macro to avoid multiple calls */ 546 const u_int bound = (flags & D_MINIMAL) ? UINT_MAX : 547 MAX(256, isqrt(n)); 548 549 k = 0; 550 c[0] = newcand(0, 0, 0); 551 for (i = 1; i <= n; i++) { 552 j = a[i]; 553 if (j == 0) 554 continue; 555 y = -b[j]; 556 oldl = 0; 557 oldc = c[0]; 558 numtries = 0; 559 do { 560 if (y <= clist[oldc].y) 561 continue; 562 l = search(c, k, y); 563 if (l != oldl + 1) 564 oldc = c[l - 1]; 565 if (l <= k) { 566 if (clist[c[l]].y <= y) 567 continue; 568 tc = c[l]; 569 c[l] = newcand(i, y, oldc); 570 oldc = tc; 571 oldl = l; 572 numtries++; 573 } else { 574 c[l] = newcand(i, y, oldc); 575 k++; 576 break; 577 } 578 } while ((y = b[++j]) > 0 && numtries < bound); 579 } 580 return (k); 581 } 582 583 static int 584 newcand(int x, int y, int pred) 585 { 586 struct cand *q; 587 588 if (clen == clistlen) { 589 clistlen = clistlen * 11 / 10; 590 clist = xrealloc(clist, clistlen, sizeof(*clist)); 591 } 592 q = clist + clen; 593 q->x = x; 594 q->y = y; 595 q->pred = pred; 596 return (clen++); 597 } 598 599 static int 600 search(int *c, int k, int y) 601 { 602 int i, j, l, t; 603 604 if (clist[c[k]].y < y) /* quick look for typical case */ 605 return (k + 1); 606 i = 0; 607 j = k + 1; 608 for (;;) { 609 l = (i + j) / 2; 610 if (l <= i) 611 break; 612 t = clist[c[l]].y; 613 if (t > y) 614 j = l; 615 else if (t < y) 616 i = l; 617 else 618 return (l); 619 } 620 return (l + 1); 621 } 622 623 static void 624 unravel(int p) 625 { 626 struct cand *q; 627 int i; 628 629 for (i = 0; i <= len[0]; i++) 630 J[i] = i <= pref ? i : 631 i > len[0] - suff ? i + len[1] - len[0] : 0; 632 for (q = clist + p; q->y != 0; q = clist + q->pred) 633 J[q->x + pref] = q->y + pref; 634 } 635 636 /* 637 * Check does double duty: 638 * 1. ferret out any fortuitous correspondences due 639 * to confounding by hashing (which result in "jackpot") 640 * 2. collect random access indexes to the two files 641 */ 642 static void 643 check(FILE *f1, FILE *f2, int flags) 644 { 645 int i, j, jackpot, c, d; 646 long ctold, ctnew; 647 648 rewind(f1); 649 rewind(f2); 650 j = 1; 651 ixold[0] = ixnew[0] = 0; 652 jackpot = 0; 653 ctold = ctnew = 0; 654 for (i = 1; i <= len[0]; i++) { 655 if (J[i] == 0) { 656 ixold[i] = ctold += skipline(f1); 657 continue; 658 } 659 while (j < J[i]) { 660 ixnew[j] = ctnew += skipline(f2); 661 j++; 662 } 663 if (flags & (D_FOLDBLANKS|D_IGNOREBLANKS|D_IGNORECASE)) { 664 for (;;) { 665 c = getc(f1); 666 d = getc(f2); 667 /* 668 * GNU diff ignores a missing newline 669 * in one file for -b or -w. 670 */ 671 if ((flags & (D_FOLDBLANKS|D_IGNOREBLANKS)) && 672 ((c == EOF && d == '\n') || 673 (c == '\n' && d == EOF))) { 674 break; 675 } 676 ctold++; 677 ctnew++; 678 if ((flags & D_FOLDBLANKS) && isspace(c) && 679 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 ((flags & D_IGNOREBLANKS)) { 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, int flags) 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, flags); 817 } 818 if (m == 0) 819 change(f1, f2, 1, 0, 1, len[1], flags); 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, flags); 832 else if (diff_format == D_UNIFIED) 833 dump_unified_vec(f1, f2, flags); 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, int flags) 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, flags); 1026 else 1027 dump_unified_vec(f1, f2, flags); 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, flags); 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, flags); 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, int flags) 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' && (flags & D_EXPANDTABS)) { 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, int flags) 1142 { 1143 int i, t, space; 1144 int sum; 1145 1146 sum = 1; 1147 space = 0; 1148 if ((flags & (D_FOLDBLANKS|D_IGNOREBLANKS)) == 0) { 1149 if (flags & D_IGNORECASE) 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 && (flags & D_IGNOREBLANKS) == 0) { 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 (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 *state = NULL; 1228 1229 lastline = pos; 1230 while (pos > last) { 1231 fseek(fp, f[pos - 1], SEEK_SET); 1232 nc = f[pos] - f[pos - 1]; 1233 if (nc >= sizeof(buf)) 1234 nc = sizeof(buf) - 1; 1235 nc = fread(buf, 1, nc, fp); 1236 if (nc > 0) { 1237 buf[nc] = '\0'; 1238 buf[strcspn(buf, "\n")] = '\0'; 1239 if (isalpha(buf[0]) || buf[0] == '_' || buf[0] == '$') { 1240 if (begins_with(buf, "private:")) { 1241 if (!state) 1242 state = " (private)"; 1243 } else if (begins_with(buf, "protected:")) { 1244 if (!state) 1245 state = " (protected)"; 1246 } else if (begins_with(buf, "public:")) { 1247 if (!state) 1248 state = " (public)"; 1249 } else { 1250 strlcpy(lastbuf, buf, sizeof lastbuf); 1251 if (state) 1252 strlcat(lastbuf, state, 1253 sizeof lastbuf); 1254 lastmatchline = pos; 1255 return lastbuf; 1256 } 1257 } 1258 } 1259 pos--; 1260 } 1261 return lastmatchline > 0 ? lastbuf : NULL; 1262 } 1263 1264 /* dump accumulated "context" diff changes */ 1265 static void 1266 dump_context_vec(FILE *f1, FILE *f2, int flags) 1267 { 1268 struct context_vec *cvp = context_vec_start; 1269 int lowa, upb, lowc, upd, do_output; 1270 int a, b, c, d; 1271 char ch, *f; 1272 1273 if (context_vec_start > context_vec_ptr) 1274 return; 1275 1276 b = d = 0; /* gcc */ 1277 lowa = MAX(1, cvp->a - context); 1278 upb = MIN(len[0], context_vec_ptr->b + context); 1279 lowc = MAX(1, cvp->c - context); 1280 upd = MIN(len[1], context_vec_ptr->d + context); 1281 1282 diff_output("***************"); 1283 if ((flags & D_PROTOTYPE)) { 1284 f = match_function(ixold, lowa-1, f1); 1285 if (f != NULL) { 1286 diff_output(" "); 1287 diff_output("%s", f); 1288 } 1289 } 1290 diff_output("\n*** "); 1291 range(lowa, upb, ","); 1292 diff_output(" ****\n"); 1293 1294 /* 1295 * Output changes to the "old" file. The first loop suppresses 1296 * output if there were no changes to the "old" file (we'll see 1297 * the "old" lines as context in the "new" list). 1298 */ 1299 do_output = 0; 1300 for (; cvp <= context_vec_ptr; cvp++) 1301 if (cvp->a <= cvp->b) { 1302 cvp = context_vec_start; 1303 do_output++; 1304 break; 1305 } 1306 if (do_output) { 1307 while (cvp <= context_vec_ptr) { 1308 a = cvp->a; 1309 b = cvp->b; 1310 c = cvp->c; 1311 d = cvp->d; 1312 1313 if (a <= b && c <= d) 1314 ch = 'c'; 1315 else 1316 ch = (a <= b) ? 'd' : 'a'; 1317 1318 if (ch == 'a') 1319 fetch(ixold, lowa, b, f1, ' ', 0, flags); 1320 else { 1321 fetch(ixold, lowa, a - 1, f1, ' ', 0, flags); 1322 fetch(ixold, a, b, f1, 1323 ch == 'c' ? '!' : '-', 0, flags); 1324 } 1325 lowa = b + 1; 1326 cvp++; 1327 } 1328 fetch(ixold, b + 1, upb, f1, ' ', 0, flags); 1329 } 1330 /* output changes to the "new" file */ 1331 diff_output("--- "); 1332 range(lowc, upd, ","); 1333 diff_output(" ----\n"); 1334 1335 do_output = 0; 1336 for (cvp = context_vec_start; cvp <= context_vec_ptr; cvp++) 1337 if (cvp->c <= cvp->d) { 1338 cvp = context_vec_start; 1339 do_output++; 1340 break; 1341 } 1342 if (do_output) { 1343 while (cvp <= context_vec_ptr) { 1344 a = cvp->a; 1345 b = cvp->b; 1346 c = cvp->c; 1347 d = cvp->d; 1348 1349 if (a <= b && c <= d) 1350 ch = 'c'; 1351 else 1352 ch = (a <= b) ? 'd' : 'a'; 1353 1354 if (ch == 'd') 1355 fetch(ixnew, lowc, d, f2, ' ', 0, flags); 1356 else { 1357 fetch(ixnew, lowc, c - 1, f2, ' ', 0, flags); 1358 fetch(ixnew, c, d, f2, 1359 ch == 'c' ? '!' : '+', 0, flags); 1360 } 1361 lowc = d + 1; 1362 cvp++; 1363 } 1364 fetch(ixnew, d + 1, upd, f2, ' ', 0, flags); 1365 } 1366 context_vec_ptr = context_vec_start - 1; 1367 } 1368 1369 /* dump accumulated "unified" diff changes */ 1370 static void 1371 dump_unified_vec(FILE *f1, FILE *f2, int flags) 1372 { 1373 struct context_vec *cvp = context_vec_start; 1374 int lowa, upb, lowc, upd; 1375 int a, b, c, d; 1376 char ch, *f; 1377 1378 if (context_vec_start > context_vec_ptr) 1379 return; 1380 1381 b = d = 0; /* gcc */ 1382 lowa = MAX(1, cvp->a - context); 1383 upb = MIN(len[0], context_vec_ptr->b + context); 1384 lowc = MAX(1, cvp->c - context); 1385 upd = MIN(len[1], context_vec_ptr->d + context); 1386 1387 diff_output("@@ -"); 1388 uni_range(lowa, upb); 1389 diff_output(" +"); 1390 uni_range(lowc, upd); 1391 diff_output(" @@"); 1392 if ((flags & D_PROTOTYPE)) { 1393 f = match_function(ixold, lowa-1, f1); 1394 if (f != NULL) { 1395 diff_output(" "); 1396 diff_output("%s", f); 1397 } 1398 } 1399 diff_output("\n"); 1400 1401 /* 1402 * Output changes in "unified" diff format--the old and new lines 1403 * are printed together. 1404 */ 1405 for (; cvp <= context_vec_ptr; cvp++) { 1406 a = cvp->a; 1407 b = cvp->b; 1408 c = cvp->c; 1409 d = cvp->d; 1410 1411 /* 1412 * c: both new and old changes 1413 * d: only changes in the old file 1414 * a: only changes in the new file 1415 */ 1416 if (a <= b && c <= d) 1417 ch = 'c'; 1418 else 1419 ch = (a <= b) ? 'd' : 'a'; 1420 1421 switch (ch) { 1422 case 'c': 1423 fetch(ixold, lowa, a - 1, f1, ' ', 0, flags); 1424 fetch(ixold, a, b, f1, '-', 0, flags); 1425 fetch(ixnew, c, d, f2, '+', 0, flags); 1426 break; 1427 case 'd': 1428 fetch(ixold, lowa, a - 1, f1, ' ', 0, flags); 1429 fetch(ixold, a, b, f1, '-', 0, flags); 1430 break; 1431 case 'a': 1432 fetch(ixnew, lowc, c - 1, f2, ' ', 0, flags); 1433 fetch(ixnew, c, d, f2, '+', 0, flags); 1434 break; 1435 } 1436 lowa = b + 1; 1437 lowc = d + 1; 1438 } 1439 fetch(ixnew, d + 1, upd, f2, ' ', 0, flags); 1440 1441 context_vec_ptr = context_vec_start - 1; 1442 } 1443 1444 void 1445 diff_output(const char *fmt, ...) 1446 { 1447 va_list vap; 1448 int i; 1449 char *str; 1450 1451 va_start(vap, fmt); 1452 i = vasprintf(&str, fmt, vap); 1453 va_end(vap); 1454 if (i == -1) 1455 fatal("diff_output: could not allocate memory"); 1456 if (diffbuf != NULL) 1457 cvs_buf_puts(diffbuf, str); 1458 else 1459 cvs_printf("%s", str); 1460 xfree(str); 1461 } 1462