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