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