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