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