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