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