1 /* Three way file comparison program (diff3) for Project GNU. 2 Copyright (C) 1988, 1989, 1992, 1993, 1994, 1997, 1998 Free Software Foundation, Inc. 3 4 This program is free software; you can redistribute it and/or modify 5 it under the terms of the GNU General Public License as published by 6 the Free Software Foundation; either version 2, or (at your option) 7 any later version. 8 9 This program is distributed in the hope that it will be useful, 10 but WITHOUT ANY WARRANTY; without even the implied warranty of 11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 GNU General Public License for more details. 13 14 */ 15 16 /* Written by Randy Smith */ 17 /* Librarification by Tim Pierce */ 18 19 #include "system.h" 20 #include <stdio.h> 21 #include <setjmp.h> 22 #include "getopt.h" 23 #include "diffrun.h" 24 25 /* diff3.c has a real initialize_main function. */ 26 #ifdef initialize_main 27 #undef initialize_main 28 #endif 29 30 extern char const diff_version_string[]; 31 32 extern FILE *outfile; 33 34 extern const struct diff_callbacks *callbacks; 35 36 void write_output PARAMS((char const *, size_t)); 37 void printf_output PARAMS((char const *, ...)) 38 #if __GNUC__ > 2 || (__GNUC__ == 2 && __GNUC_MINOR__ > 6) 39 __attribute__ ((__format__ (__printf__, 1, 2))) 40 #endif 41 ; 42 void flush_output PARAMS((void)); 43 44 char * cvs_temp_name PARAMS((void)); 45 46 /* 47 * Internal data structures and macros for the diff3 program; includes 48 * data structures for both diff3 diffs and normal diffs. 49 */ 50 51 /* Different files within a three way diff. */ 52 #define FILE0 0 53 #define FILE1 1 54 #define FILE2 2 55 56 /* 57 * A three way diff is built from two two-way diffs; the file which 58 * the two two-way diffs share is: 59 */ 60 #define FILEC FILE2 61 62 /* 63 * Different files within a two way diff. 64 * FC is the common file, FO the other file. 65 */ 66 #define FO 0 67 #define FC 1 68 69 /* The ranges are indexed by */ 70 #define START 0 71 #define END 1 72 73 enum diff_type { 74 ERROR, /* Should not be used */ 75 ADD, /* Two way diff add */ 76 CHANGE, /* Two way diff change */ 77 DELETE, /* Two way diff delete */ 78 DIFF_ALL, /* All three are different */ 79 DIFF_1ST, /* Only the first is different */ 80 DIFF_2ND, /* Only the second */ 81 DIFF_3RD /* Only the third */ 82 }; 83 84 /* Two way diff */ 85 struct diff_block { 86 int ranges[2][2]; /* Ranges are inclusive */ 87 char **lines[2]; /* The actual lines (may contain nulls) */ 88 size_t *lengths[2]; /* Line lengths (including newlines, if any) */ 89 struct diff_block *next; 90 }; 91 92 /* Three way diff */ 93 94 struct diff3_block { 95 enum diff_type correspond; /* Type of diff */ 96 int ranges[3][2]; /* Ranges are inclusive */ 97 char **lines[3]; /* The actual lines (may contain nulls) */ 98 size_t *lengths[3]; /* Line lengths (including newlines, if any) */ 99 struct diff3_block *next; 100 }; 101 102 /* 103 * Access the ranges on a diff block. 104 */ 105 #define D_LOWLINE(diff, filenum) \ 106 ((diff)->ranges[filenum][START]) 107 #define D_HIGHLINE(diff, filenum) \ 108 ((diff)->ranges[filenum][END]) 109 #define D_NUMLINES(diff, filenum) \ 110 (D_HIGHLINE (diff, filenum) - D_LOWLINE (diff, filenum) + 1) 111 112 /* 113 * Access the line numbers in a file in a diff by relative line 114 * numbers (i.e. line number within the diff itself). Note that these 115 * are lvalues and can be used for assignment. 116 */ 117 #define D_RELNUM(diff, filenum, linenum) \ 118 ((diff)->lines[filenum][linenum]) 119 #define D_RELLEN(diff, filenum, linenum) \ 120 ((diff)->lengths[filenum][linenum]) 121 122 /* 123 * And get at them directly, when that should be necessary. 124 */ 125 #define D_LINEARRAY(diff, filenum) \ 126 ((diff)->lines[filenum]) 127 #define D_LENARRAY(diff, filenum) \ 128 ((diff)->lengths[filenum]) 129 130 /* 131 * Next block. 132 */ 133 #define D_NEXT(diff) ((diff)->next) 134 135 /* 136 * Access the type of a diff3 block. 137 */ 138 #define D3_TYPE(diff) ((diff)->correspond) 139 140 /* 141 * Line mappings based on diffs. The first maps off the top of the 142 * diff, the second off of the bottom. 143 */ 144 #define D_HIGH_MAPLINE(diff, fromfile, tofile, lineno) \ 145 ((lineno) \ 146 - D_HIGHLINE ((diff), (fromfile)) \ 147 + D_HIGHLINE ((diff), (tofile))) 148 149 #define D_LOW_MAPLINE(diff, fromfile, tofile, lineno) \ 150 ((lineno) \ 151 - D_LOWLINE ((diff), (fromfile)) \ 152 + D_LOWLINE ((diff), (tofile))) 153 154 /* 155 * General memory allocation function. 156 */ 157 #define ALLOCATE(number, type) \ 158 (type *) xmalloc ((number) * sizeof (type)) 159 160 /* Options variables for flags set on command line. */ 161 162 /* If nonzero, treat all files as text files, never as binary. */ 163 static int always_text; 164 165 /* If nonzero, write out an ed script instead of the standard diff3 format. */ 166 static int edscript; 167 168 /* If nonzero, in the case of overlapping diffs (type DIFF_ALL), 169 preserve the lines which would normally be deleted from 170 file 1 with a special flagging mechanism. */ 171 static int flagging; 172 173 /* Number of lines to keep in identical prefix and suffix. */ 174 static int horizon_lines = 10; 175 176 /* Use a tab to align output lines (-T). */ 177 static int tab_align_flag; 178 179 /* If nonzero, do not output information for overlapping diffs. */ 180 static int simple_only; 181 182 /* If nonzero, do not output information for non-overlapping diffs. */ 183 static int overlap_only; 184 185 /* If nonzero, show information for DIFF_2ND diffs. */ 186 static int show_2nd; 187 188 /* If nonzero, include `:wq' at the end of the script 189 to write out the file being edited. */ 190 static int finalwrite; 191 192 /* If nonzero, output a merged file. */ 193 static int merge; 194 195 extern char *diff_program_name; 196 197 static char *read_diff PARAMS((char const *, char const *, char **)); 198 static char *scan_diff_line PARAMS((char *, char **, size_t *, char *, int)); 199 static enum diff_type process_diff_control PARAMS((char **, struct diff_block *)); 200 static int compare_line_list PARAMS((char * const[], size_t const[], char * const[], size_t const[], int)); 201 static int copy_stringlist PARAMS((char * const[], size_t const[], char *[], size_t[], int)); 202 static int dotlines PARAMS((struct diff3_block *, int)); 203 static int output_diff3_edscript PARAMS((struct diff3_block *, int const[3], int const[3], char const *, char const *, char const *)); 204 static int output_diff3_merge PARAMS((FILE *, struct diff3_block *, int const[3], int const[3], char const *, char const *, char const *)); 205 static size_t myread PARAMS((int, char *, size_t)); 206 static struct diff3_block *create_diff3_block PARAMS((int, int, int, int, int, int)); 207 static struct diff3_block *make_3way_diff PARAMS((struct diff_block *, struct diff_block *)); 208 static struct diff3_block *reverse_diff3_blocklist PARAMS((struct diff3_block *)); 209 static struct diff3_block *using_to_diff3_block PARAMS((struct diff_block *[2], struct diff_block *[2], int, int, struct diff3_block const *)); 210 static struct diff_block *process_diff PARAMS((char const *, char const *, struct diff_block **, char **)); 211 static void check_output PARAMS((FILE *)); 212 static void diff3_fatal PARAMS((char const *)); 213 static void output_diff3 PARAMS((struct diff3_block *, int const[3], int const[3])); 214 static void diff3_perror_with_exit PARAMS((char const *)); 215 static int try_help PARAMS((char const *)); 216 static void undotlines PARAMS((int, int, int)); 217 static void usage PARAMS((void)); 218 static void initialize_main PARAMS((int *, char ***)); 219 static void free_diff_blocks PARAMS((struct diff_block *)); 220 static void free_diff3_blocks PARAMS((struct diff3_block *)); 221 222 /* Functions provided in libdiff.a or other external sources. */ 223 VOID *xmalloc PARAMS((size_t)); 224 VOID *xrealloc PARAMS((VOID *, size_t)); 225 void perror_with_name PARAMS((char const *)); 226 void diff_error PARAMS((char const *, char const *, char const *)); 227 228 /* Permit non-local exits from diff3. */ 229 static jmp_buf diff3_abort_buf; 230 #define DIFF3_ABORT(retval) longjmp(diff3_abort_buf, retval) 231 232 static struct option const longopts[] = 233 { 234 {"text", 0, 0, 'a'}, 235 {"show-all", 0, 0, 'A'}, 236 {"ed", 0, 0, 'e'}, 237 {"show-overlap", 0, 0, 'E'}, 238 {"label", 1, 0, 'L'}, 239 {"merge", 0, 0, 'm'}, 240 {"initial-tab", 0, 0, 'T'}, 241 {"overlap-only", 0, 0, 'x'}, 242 {"easy-only", 0, 0, '3'}, 243 {"version", 0, 0, 'v'}, 244 {"help", 0, 0, 129}, 245 {0, 0, 0, 0} 246 }; 247 248 /* 249 * Main program. Calls diff twice on two pairs of input files, 250 * combines the two diffs, and outputs them. 251 */ 252 int 253 diff3_run (argc, argv, out, callbacks_arg) 254 int argc; 255 char **argv; 256 char *out; 257 const struct diff_callbacks *callbacks_arg; 258 { 259 int c, i; 260 int mapping[3]; 261 int rev_mapping[3]; 262 int incompat = 0; 263 int conflicts_found; 264 int status; 265 struct diff_block *thread0, *thread1, *last_block; 266 char *content0, *content1; 267 struct diff3_block *diff3; 268 int tag_count = 0; 269 char *tag_strings[3]; 270 char *commonname; 271 char **file; 272 struct stat statb; 273 int optind_old; 274 int opened_file = 0; 275 276 callbacks = callbacks_arg; 277 278 initialize_main (&argc, &argv); 279 280 optind_old = optind; 281 optind = 0; 282 while ((c = getopt_long (argc, argv, "aeimvx3AEL:TX", longopts, 0)) != EOF) 283 { 284 switch (c) 285 { 286 case 'a': 287 always_text = 1; 288 break; 289 case 'A': 290 show_2nd = 1; 291 flagging = 1; 292 incompat++; 293 break; 294 case 'x': 295 overlap_only = 1; 296 incompat++; 297 break; 298 case '3': 299 simple_only = 1; 300 incompat++; 301 break; 302 case 'i': 303 finalwrite = 1; 304 break; 305 case 'm': 306 merge = 1; 307 break; 308 case 'X': 309 overlap_only = 1; 310 /* Falls through */ 311 case 'E': 312 flagging = 1; 313 /* Falls through */ 314 case 'e': 315 incompat++; 316 break; 317 case 'T': 318 tab_align_flag = 1; 319 break; 320 case 'v': 321 if (callbacks && callbacks->write_stdout) 322 { 323 (*callbacks->write_stdout) ("diff3 - GNU diffutils version "); 324 (*callbacks->write_stdout) (diff_version_string); 325 (*callbacks->write_stdout) ("\n"); 326 } 327 else 328 printf ("diff3 - GNU diffutils version %s\n", diff_version_string); 329 return 0; 330 case 129: 331 usage (); 332 if (! callbacks || ! callbacks->write_stdout) 333 check_output (stdout); 334 return 0; 335 case 'L': 336 /* Handle up to three -L options. */ 337 if (tag_count < 3) 338 { 339 tag_strings[tag_count++] = optarg; 340 break; 341 } 342 return try_help ("Too many labels were given. The limit is 3."); 343 default: 344 return try_help (0); 345 } 346 } 347 348 edscript = incompat & ~merge; /* -AeExX3 without -m implies ed script. */ 349 show_2nd |= ~incompat & merge; /* -m without -AeExX3 implies -A. */ 350 flagging |= ~incompat & merge; 351 352 if (incompat > 1 /* Ensure at most one of -AeExX3. */ 353 || finalwrite & merge /* -i -m would rewrite input file. */ 354 || (tag_count && ! flagging)) /* -L requires one of -AEX. */ 355 return try_help ("incompatible options"); 356 357 if (argc - optind != 3) 358 return try_help (argc - optind < 3 ? "missing operand" : "extra operand"); 359 360 file = &argv[optind]; 361 362 optind = optind_old; 363 364 for (i = tag_count; i < 3; i++) 365 tag_strings[i] = file[i]; 366 367 /* Always compare file1 to file2, even if file2 is "-". 368 This is needed for -mAeExX3. Using the file0 as 369 the common file would produce wrong results, because if the 370 file0-file1 diffs didn't line up with the file0-file2 diffs 371 (which is entirely possible since we don't use diff's -n option), 372 diff3 might report phantom changes from file1 to file2. */ 373 374 if (strcmp (file[2], "-") == 0) 375 { 376 /* Sigh. We've got standard input as the last arg. We can't 377 call diff twice on stdin. Use the middle arg as the common 378 file instead. */ 379 if (strcmp (file[0], "-") == 0 || strcmp (file[1], "-") == 0) 380 { 381 diff_error ("%s", "`-' specified for more than one input file", 0); 382 return 2; 383 } 384 mapping[0] = 0; 385 mapping[1] = 2; 386 mapping[2] = 1; 387 } 388 else 389 { 390 /* Normal, what you'd expect */ 391 mapping[0] = 0; 392 mapping[1] = 1; 393 mapping[2] = 2; 394 } 395 396 for (i = 0; i < 3; i++) 397 rev_mapping[mapping[i]] = i; 398 399 for (i = 0; i < 3; i++) 400 if (strcmp (file[i], "-") != 0) 401 { 402 if (stat (file[i], &statb) < 0) 403 { 404 perror_with_name (file[i]); 405 return 2; 406 } 407 else if (S_ISDIR(statb.st_mode)) 408 { 409 diff_error ("%s: Is a directory", file[i], 0); 410 return 2; 411 } 412 } 413 414 if (callbacks && callbacks->write_output) 415 { 416 if (out != NULL) 417 { 418 diff_error ("write callback with output file", 0, 0); 419 return 2; 420 } 421 } 422 else 423 { 424 if (out == NULL) 425 outfile = stdout; 426 else 427 { 428 outfile = fopen (out, "w"); 429 if (outfile == NULL) 430 { 431 perror_with_name ("could not open output file"); 432 return 2; 433 } 434 opened_file = 1; 435 } 436 } 437 438 /* Set the jump buffer, so that diff may abort execution without 439 terminating the process. */ 440 status = setjmp (diff3_abort_buf); 441 if (status != 0) 442 return status; 443 444 commonname = file[rev_mapping[FILEC]]; 445 thread1 = process_diff (file[rev_mapping[FILE1]], commonname, &last_block, 446 &content1); 447 if (thread1) 448 for (i = 0; i < 2; i++) 449 { 450 horizon_lines = max (horizon_lines, D_NUMLINES (thread1, i)); 451 horizon_lines = max (horizon_lines, D_NUMLINES (last_block, i)); 452 } 453 thread0 = process_diff (file[rev_mapping[FILE0]], commonname, &last_block, 454 &content0); 455 diff3 = make_3way_diff (thread0, thread1); 456 if (edscript) 457 conflicts_found 458 = output_diff3_edscript (diff3, mapping, rev_mapping, 459 tag_strings[0], tag_strings[1], tag_strings[2]); 460 else if (merge) 461 { 462 FILE *mfp = fopen (file[rev_mapping[FILE0]], "r"); 463 if (! mfp) 464 diff3_perror_with_exit (file[rev_mapping[FILE0]]); 465 conflicts_found = output_diff3_merge (mfp, diff3, mapping, rev_mapping, 466 tag_strings[0], tag_strings[1], tag_strings[2]); 467 if (ferror (mfp)) 468 diff3_fatal ("read error"); 469 if (fclose(mfp) != 0) 470 perror_with_name (file[rev_mapping[FILE0]]); 471 } 472 else 473 { 474 output_diff3 (diff3, mapping, rev_mapping); 475 conflicts_found = 0; 476 } 477 478 free(content0); 479 free(content1); 480 free_diff3_blocks(diff3); 481 482 if (! callbacks || ! callbacks->write_output) 483 check_output (outfile); 484 485 if (opened_file) 486 if (fclose (outfile) != 0) 487 perror_with_name ("close error on output file"); 488 489 return conflicts_found; 490 } 491 492 static int 493 try_help (reason) 494 char const *reason; 495 { 496 if (reason) 497 diff_error ("%s", reason, 0); 498 diff_error ("Try `%s --help' for more information.", diff_program_name, 0); 499 return 2; 500 } 501 502 static void 503 check_output (stream) 504 FILE *stream; 505 { 506 if (ferror (stream) || fflush (stream) != 0) 507 diff3_fatal ("write error"); 508 } 509 510 /* 511 * Explain, patiently and kindly, how to use this program. 512 */ 513 static void 514 usage () 515 { 516 if (callbacks && callbacks->write_stdout) 517 { 518 (*callbacks->write_stdout) ("Usage: "); 519 (*callbacks->write_stdout) (diff_program_name); 520 (*callbacks->write_stdout) (" [OPTION]... MYFILE OLDFILE YOURFILE\n\n"); 521 522 (*callbacks->write_stdout) ("\ 523 -e --ed Output unmerged changes from OLDFILE to YOURFILE into MYFILE.\n\ 524 -E --show-overlap Output unmerged changes, bracketing conflicts.\n\ 525 -A --show-all Output all changes, bracketing conflicts.\n\ 526 -x --overlap-only Output overlapping changes.\n\ 527 -X Output overlapping changes, bracketing them.\n\ 528 -3 --easy-only Output unmerged nonoverlapping changes.\n\n"); 529 (*callbacks->write_stdout) ("\ 530 -m --merge Output merged file instead of ed script (default -A).\n\ 531 -L LABEL --label=LABEL Use LABEL instead of file name.\n\ 532 -i Append `w' and `q' commands to ed scripts.\n\ 533 -a --text Treat all files as text.\n\ 534 -T --initial-tab Make tabs line up by prepending a tab.\n\n"); 535 (*callbacks->write_stdout) ("\ 536 -v --version Output version info.\n\ 537 --help Output this help.\n\n"); 538 (*callbacks->write_stdout) ("If a FILE is `-', read standard input.\n"); 539 } 540 else 541 { 542 printf ("Usage: %s [OPTION]... MYFILE OLDFILE YOURFILE\n\n", diff_program_name); 543 544 printf ("%s", "\ 545 -e --ed Output unmerged changes from OLDFILE to YOURFILE into MYFILE.\n\ 546 -E --show-overlap Output unmerged changes, bracketing conflicts.\n\ 547 -A --show-all Output all changes, bracketing conflicts.\n\ 548 -x --overlap-only Output overlapping changes.\n\ 549 -X Output overlapping changes, bracketing them.\n\ 550 -3 --easy-only Output unmerged nonoverlapping changes.\n\n"); 551 printf ("%s", "\ 552 -m --merge Output merged file instead of ed script (default -A).\n\ 553 -L LABEL --label=LABEL Use LABEL instead of file name.\n\ 554 -i Append `w' and `q' commands to ed scripts.\n\ 555 -a --text Treat all files as text.\n\ 556 -T --initial-tab Make tabs line up by prepending a tab.\n\n"); 557 printf ("%s", "\ 558 -v --version Output version info.\n\ 559 --help Output this help.\n\n"); 560 printf ("If a FILE is `-', read standard input.\n"); 561 } 562 } 563 564 /* 565 * Routines that combine the two diffs together into one. The 566 * algorithm used follows: 567 * 568 * File2 is shared in common between the two diffs. 569 * Diff02 is the diff between 0 and 2. 570 * Diff12 is the diff between 1 and 2. 571 * 572 * 1) Find the range for the first block in File2. 573 * a) Take the lowest of the two ranges (in File2) in the two 574 * current blocks (one from each diff) as being the low 575 * water mark. Assign the upper end of this block as 576 * being the high water mark and move the current block up 577 * one. Mark the block just moved over as to be used. 578 * b) Check the next block in the diff that the high water 579 * mark is *not* from. 580 * 581 * *If* the high water mark is above 582 * the low end of the range in that block, 583 * 584 * mark that block as to be used and move the current 585 * block up. Set the high water mark to the max of 586 * the high end of this block and the current. Repeat b. 587 * 588 * 2) Find the corresponding ranges in File0 (from the blocks 589 * in diff02; line per line outside of diffs) and in File1. 590 * Create a diff3_block, reserving space as indicated by the ranges. 591 * 592 * 3) Copy all of the pointers for file2 in. At least for now, 593 * do memcmp's between corresponding strings in the two diffs. 594 * 595 * 4) Copy all of the pointers for file0 and 1 in. Get what you 596 * need from file2 (when there isn't a diff block, it's 597 * identical to file2 within the range between diff blocks). 598 * 599 * 5) If the diff blocks you used came from only one of the two 600 * strings of diffs, then that file (i.e. the one other than 601 * the common file in that diff) is the odd person out. If you used 602 * diff blocks from both sets, check to see if files 0 and 1 match: 603 * 604 * Same number of lines? If so, do a set of memcmp's (if a 605 * memcmp matches; copy the pointer over; it'll be easier later 606 * if you have to do any compares). If they match, 0 & 1 are 607 * the same. If not, all three different. 608 * 609 * Then you do it again, until you run out of blocks. 610 * 611 */ 612 613 /* 614 * This routine makes a three way diff (chain of diff3_block's) from two 615 * two way diffs (chains of diff_block's). It is assumed that each of 616 * the two diffs passed are onto the same file (i.e. that each of the 617 * diffs were made "to" the same file). The three way diff pointer 618 * returned will have numbering FILE0--the other file in diff02, 619 * FILE1--the other file in diff12, and FILEC--the common file. 620 */ 621 static struct diff3_block * 622 make_3way_diff (thread0, thread1) 623 struct diff_block *thread0, *thread1; 624 { 625 /* 626 * This routine works on the two diffs passed to it as threads. 627 * Thread number 0 is diff02, thread number 1 is diff12. The USING 628 * array is set to the base of the list of blocks to be used to 629 * construct each block of the three way diff; if no blocks from a 630 * particular thread are to be used, that element of the using array 631 * is set to 0. The elements LAST_USING array are set to the last 632 * elements on each of the using lists. 633 * 634 * The HIGH_WATER_MARK is set to the highest line number in the common file 635 * described in any of the diffs in either of the USING lists. The 636 * HIGH_WATER_THREAD names the thread. Similarly the BASE_WATER_MARK 637 * and BASE_WATER_THREAD describe the lowest line number in the common file 638 * described in any of the diffs in either of the USING lists. The 639 * HIGH_WATER_DIFF is the diff from which the HIGH_WATER_MARK was 640 * taken. 641 * 642 * The HIGH_WATER_DIFF should always be equal to LAST_USING 643 * [HIGH_WATER_THREAD]. The OTHER_DIFF is the next diff to check for 644 * higher water, and should always be equal to 645 * CURRENT[HIGH_WATER_THREAD ^ 0x1]. The OTHER_THREAD is the thread 646 * in which the OTHER_DIFF is, and hence should always be equal to 647 * HIGH_WATER_THREAD ^ 0x1. 648 * 649 * The variable LAST_DIFF is kept set to the last diff block produced 650 * by this routine, for line correspondence purposes between that diff 651 * and the one currently being worked on. It is initialized to 652 * ZERO_DIFF before any blocks have been created. 653 */ 654 655 struct diff_block 656 *using[2], 657 *last_using[2], 658 *current[2]; 659 660 int 661 high_water_mark; 662 663 int 664 high_water_thread, 665 base_water_thread, 666 other_thread; 667 668 struct diff_block 669 *high_water_diff, 670 *other_diff; 671 672 struct diff3_block 673 *result, 674 *tmpblock, 675 **result_end; 676 677 struct diff3_block const *last_diff3; 678 679 static struct diff3_block const zero_diff3 = { 0 }; 680 681 /* Initialization */ 682 result = 0; 683 result_end = &result; 684 current[0] = thread0; current[1] = thread1; 685 last_diff3 = &zero_diff3; 686 687 /* Sniff up the threads until we reach the end */ 688 689 while (current[0] || current[1]) 690 { 691 using[0] = using[1] = last_using[0] = last_using[1] = 0; 692 693 /* Setup low and high water threads, diffs, and marks. */ 694 if (!current[0]) 695 base_water_thread = 1; 696 else if (!current[1]) 697 base_water_thread = 0; 698 else 699 base_water_thread = 700 (D_LOWLINE (current[0], FC) > D_LOWLINE (current[1], FC)); 701 702 high_water_thread = base_water_thread; 703 704 high_water_diff = current[high_water_thread]; 705 706 #if 0 707 /* low and high waters start off same diff */ 708 base_water_mark = D_LOWLINE (high_water_diff, FC); 709 #endif 710 711 high_water_mark = D_HIGHLINE (high_water_diff, FC); 712 713 /* Make the diff you just got info from into the using class */ 714 using[high_water_thread] 715 = last_using[high_water_thread] 716 = high_water_diff; 717 current[high_water_thread] = high_water_diff->next; 718 last_using[high_water_thread]->next = 0; 719 720 /* And mark the other diff */ 721 other_thread = high_water_thread ^ 0x1; 722 other_diff = current[other_thread]; 723 724 /* Shuffle up the ladder, checking the other diff to see if it 725 needs to be incorporated. */ 726 while (other_diff 727 && D_LOWLINE (other_diff, FC) <= high_water_mark + 1) 728 { 729 730 /* Incorporate this diff into the using list. Note that 731 this doesn't take it off the current list */ 732 if (using[other_thread]) 733 last_using[other_thread]->next = other_diff; 734 else 735 using[other_thread] = other_diff; 736 last_using[other_thread] = other_diff; 737 738 /* Take it off the current list. Note that this following 739 code assumes that other_diff enters it equal to 740 current[high_water_thread ^ 0x1] */ 741 current[other_thread] = current[other_thread]->next; 742 other_diff->next = 0; 743 744 /* Set the high_water stuff 745 If this comparison is equal, then this is the last pass 746 through this loop; since diff blocks within a given 747 thread cannot overlap, the high_water_mark will be 748 *below* the range_start of either of the next diffs. */ 749 750 if (high_water_mark < D_HIGHLINE (other_diff, FC)) 751 { 752 high_water_thread ^= 1; 753 high_water_diff = other_diff; 754 high_water_mark = D_HIGHLINE (other_diff, FC); 755 } 756 757 /* Set the other diff */ 758 other_thread = high_water_thread ^ 0x1; 759 other_diff = current[other_thread]; 760 } 761 762 /* The using lists contain a list of all of the blocks to be 763 included in this diff3_block. Create it. */ 764 765 tmpblock = using_to_diff3_block (using, last_using, 766 base_water_thread, high_water_thread, 767 last_diff3); 768 free_diff_blocks(using[0]); 769 free_diff_blocks(using[1]); 770 771 if (!tmpblock) 772 diff3_fatal ("internal error: screwup in format of diff blocks"); 773 774 /* Put it on the list. */ 775 *result_end = tmpblock; 776 result_end = &tmpblock->next; 777 778 /* Set up corresponding lines correctly. */ 779 last_diff3 = tmpblock; 780 } 781 return result; 782 } 783 784 /* 785 * using_to_diff3_block: 786 * This routine takes two lists of blocks (from two separate diff 787 * threads) and puts them together into one diff3 block. 788 * It then returns a pointer to this diff3 block or 0 for failure. 789 * 790 * All arguments besides using are for the convenience of the routine; 791 * they could be derived from the using array. 792 * LAST_USING is a pair of pointers to the last blocks in the using 793 * structure. 794 * LOW_THREAD and HIGH_THREAD tell which threads contain the lowest 795 * and highest line numbers for File0. 796 * last_diff3 contains the last diff produced in the calling routine. 797 * This is used for lines mappings which would still be identical to 798 * the state that diff ended in. 799 * 800 * A distinction should be made in this routine between the two diffs 801 * that are part of a normal two diff block, and the three diffs that 802 * are part of a diff3_block. 803 */ 804 static struct diff3_block * 805 using_to_diff3_block (using, last_using, low_thread, high_thread, last_diff3) 806 struct diff_block 807 *using[2], 808 *last_using[2]; 809 int low_thread, high_thread; 810 struct diff3_block const *last_diff3; 811 { 812 int low[2], high[2]; 813 struct diff3_block *result; 814 struct diff_block *ptr; 815 int d, i; 816 817 /* Find the range in the common file. */ 818 int lowc = D_LOWLINE (using[low_thread], FC); 819 int highc = D_HIGHLINE (last_using[high_thread], FC); 820 821 /* Find the ranges in the other files. 822 If using[d] is null, that means that the file to which that diff 823 refers is equivalent to the common file over this range. */ 824 825 for (d = 0; d < 2; d++) 826 if (using[d]) 827 { 828 low[d] = D_LOW_MAPLINE (using[d], FC, FO, lowc); 829 high[d] = D_HIGH_MAPLINE (last_using[d], FC, FO, highc); 830 } 831 else 832 { 833 low[d] = D_HIGH_MAPLINE (last_diff3, FILEC, FILE0 + d, lowc); 834 high[d] = D_HIGH_MAPLINE (last_diff3, FILEC, FILE0 + d, highc); 835 } 836 837 /* Create a block with the appropriate sizes */ 838 result = create_diff3_block (low[0], high[0], low[1], high[1], lowc, highc); 839 840 /* Copy information for the common file. 841 Return with a zero if any of the compares failed. */ 842 843 for (d = 0; d < 2; d++) 844 for (ptr = using[d]; ptr; ptr = D_NEXT (ptr)) 845 { 846 int result_offset = D_LOWLINE (ptr, FC) - lowc; 847 848 if (!copy_stringlist (D_LINEARRAY (ptr, FC), 849 D_LENARRAY (ptr, FC), 850 D_LINEARRAY (result, FILEC) + result_offset, 851 D_LENARRAY (result, FILEC) + result_offset, 852 D_NUMLINES (ptr, FC))) 853 return 0; 854 } 855 856 /* Copy information for file d. First deal with anything that might be 857 before the first diff. */ 858 859 for (d = 0; d < 2; d++) 860 { 861 struct diff_block *u = using[d]; 862 int lo = low[d], hi = high[d]; 863 864 for (i = 0; 865 i + lo < (u ? D_LOWLINE (u, FO) : hi + 1); 866 i++) 867 { 868 D_RELNUM (result, FILE0 + d, i) = D_RELNUM (result, FILEC, i); 869 D_RELLEN (result, FILE0 + d, i) = D_RELLEN (result, FILEC, i); 870 } 871 872 for (ptr = u; ptr; ptr = D_NEXT (ptr)) 873 { 874 int result_offset = D_LOWLINE (ptr, FO) - lo; 875 int linec; 876 877 if (!copy_stringlist (D_LINEARRAY (ptr, FO), 878 D_LENARRAY (ptr, FO), 879 D_LINEARRAY (result, FILE0 + d) + result_offset, 880 D_LENARRAY (result, FILE0 + d) + result_offset, 881 D_NUMLINES (ptr, FO))) 882 return 0; 883 884 /* Catch the lines between here and the next diff */ 885 linec = D_HIGHLINE (ptr, FC) + 1 - lowc; 886 for (i = D_HIGHLINE (ptr, FO) + 1 - lo; 887 i < (D_NEXT (ptr) ? D_LOWLINE (D_NEXT (ptr), FO) : hi + 1) - lo; 888 i++) 889 { 890 D_RELNUM (result, FILE0 + d, i) = D_RELNUM (result, FILEC, linec); 891 D_RELLEN (result, FILE0 + d, i) = D_RELLEN (result, FILEC, linec); 892 linec++; 893 } 894 } 895 } 896 897 /* Set correspond */ 898 if (!using[0]) 899 D3_TYPE (result) = DIFF_2ND; 900 else if (!using[1]) 901 D3_TYPE (result) = DIFF_1ST; 902 else 903 { 904 int nl0 = D_NUMLINES (result, FILE0); 905 int nl1 = D_NUMLINES (result, FILE1); 906 907 if (nl0 != nl1 908 || !compare_line_list (D_LINEARRAY (result, FILE0), 909 D_LENARRAY (result, FILE0), 910 D_LINEARRAY (result, FILE1), 911 D_LENARRAY (result, FILE1), 912 nl0)) 913 D3_TYPE (result) = DIFF_ALL; 914 else 915 D3_TYPE (result) = DIFF_3RD; 916 } 917 918 return result; 919 } 920 921 /* 922 * This routine copies pointers from a list of strings to a different list 923 * of strings. If a spot in the second list is already filled, it 924 * makes sure that it is filled with the same string; if not it 925 * returns 0, the copy incomplete. 926 * Upon successful completion of the copy, it returns 1. 927 */ 928 static int 929 copy_stringlist (fromptrs, fromlengths, toptrs, tolengths, copynum) 930 char * const fromptrs[]; 931 char *toptrs[]; 932 size_t const fromlengths[]; 933 size_t tolengths[]; 934 int copynum; 935 { 936 register char * const *f = fromptrs; 937 register char **t = toptrs; 938 register size_t const *fl = fromlengths; 939 register size_t *tl = tolengths; 940 941 while (copynum--) 942 { 943 if (*t) 944 { if (*fl != *tl || memcmp (*f, *t, *fl)) return 0; } 945 else 946 { *t = *f ; *tl = *fl; } 947 948 t++; f++; tl++; fl++; 949 } 950 return 1; 951 } 952 953 /* 954 * Create a diff3_block, with ranges as specified in the arguments. 955 * Allocate the arrays for the various pointers (and zero them) based 956 * on the arguments passed. Return the block as a result. 957 */ 958 static struct diff3_block * 959 create_diff3_block (low0, high0, low1, high1, low2, high2) 960 register int low0, high0, low1, high1, low2, high2; 961 { 962 struct diff3_block *result = ALLOCATE (1, struct diff3_block); 963 int numlines; 964 965 D3_TYPE (result) = ERROR; 966 D_NEXT (result) = 0; 967 968 /* Assign ranges */ 969 D_LOWLINE (result, FILE0) = low0; 970 D_HIGHLINE (result, FILE0) = high0; 971 D_LOWLINE (result, FILE1) = low1; 972 D_HIGHLINE (result, FILE1) = high1; 973 D_LOWLINE (result, FILE2) = low2; 974 D_HIGHLINE (result, FILE2) = high2; 975 976 /* Allocate and zero space */ 977 numlines = D_NUMLINES (result, FILE0); 978 if (numlines) 979 { 980 D_LINEARRAY (result, FILE0) = ALLOCATE (numlines, char *); 981 D_LENARRAY (result, FILE0) = ALLOCATE (numlines, size_t); 982 bzero (D_LINEARRAY (result, FILE0), (numlines * sizeof (char *))); 983 bzero (D_LENARRAY (result, FILE0), (numlines * sizeof (size_t))); 984 } 985 else 986 { 987 D_LINEARRAY (result, FILE0) = 0; 988 D_LENARRAY (result, FILE0) = 0; 989 } 990 991 numlines = D_NUMLINES (result, FILE1); 992 if (numlines) 993 { 994 D_LINEARRAY (result, FILE1) = ALLOCATE (numlines, char *); 995 D_LENARRAY (result, FILE1) = ALLOCATE (numlines, size_t); 996 bzero (D_LINEARRAY (result, FILE1), (numlines * sizeof (char *))); 997 bzero (D_LENARRAY (result, FILE1), (numlines * sizeof (size_t))); 998 } 999 else 1000 { 1001 D_LINEARRAY (result, FILE1) = 0; 1002 D_LENARRAY (result, FILE1) = 0; 1003 } 1004 1005 numlines = D_NUMLINES (result, FILE2); 1006 if (numlines) 1007 { 1008 D_LINEARRAY (result, FILE2) = ALLOCATE (numlines, char *); 1009 D_LENARRAY (result, FILE2) = ALLOCATE (numlines, size_t); 1010 bzero (D_LINEARRAY (result, FILE2), (numlines * sizeof (char *))); 1011 bzero (D_LENARRAY (result, FILE2), (numlines * sizeof (size_t))); 1012 } 1013 else 1014 { 1015 D_LINEARRAY (result, FILE2) = 0; 1016 D_LENARRAY (result, FILE2) = 0; 1017 } 1018 1019 /* Return */ 1020 return result; 1021 } 1022 1023 /* 1024 * Compare two lists of lines of text. 1025 * Return 1 if they are equivalent, 0 if not. 1026 */ 1027 static int 1028 compare_line_list (list1, lengths1, list2, lengths2, nl) 1029 char * const list1[], * const list2[]; 1030 size_t const lengths1[], lengths2[]; 1031 int nl; 1032 { 1033 char 1034 * const *l1 = list1, 1035 * const *l2 = list2; 1036 size_t const 1037 *lgths1 = lengths1, 1038 *lgths2 = lengths2; 1039 1040 while (nl--) 1041 if (!*l1 || !*l2 || *lgths1 != *lgths2++ 1042 || memcmp (*l1++, *l2++, *lgths1++)) 1043 return 0; 1044 return 1; 1045 } 1046 1047 /* 1048 * Routines to input and parse two way diffs. 1049 */ 1050 1051 extern char **environ; 1052 1053 static struct diff_block * 1054 process_diff (filea, fileb, last_block, diff_contents) 1055 char const *filea, *fileb; 1056 struct diff_block **last_block; 1057 char **diff_contents; 1058 { 1059 char *diff_limit; 1060 char *scan_diff; 1061 enum diff_type dt; 1062 int i; 1063 struct diff_block *block_list, **block_list_end, *bptr; 1064 1065 diff_limit = read_diff (filea, fileb, diff_contents); 1066 scan_diff = *diff_contents; 1067 block_list_end = &block_list; 1068 bptr = 0; /* Pacify `gcc -W'. */ 1069 1070 while (scan_diff < diff_limit) 1071 { 1072 bptr = ALLOCATE (1, struct diff_block); 1073 bptr->lines[0] = bptr->lines[1] = 0; 1074 bptr->lengths[0] = bptr->lengths[1] = 0; 1075 1076 dt = process_diff_control (&scan_diff, bptr); 1077 if (dt == ERROR || *scan_diff != '\n') 1078 { 1079 char *serr; 1080 1081 for (serr = scan_diff; *serr != '\n'; serr++) 1082 ; 1083 *serr = '\0'; 1084 diff_error ("diff error: %s", scan_diff, 0); 1085 *serr = '\n'; 1086 DIFF3_ABORT (2); 1087 } 1088 scan_diff++; 1089 1090 /* Force appropriate ranges to be null, if necessary */ 1091 switch (dt) 1092 { 1093 case ADD: 1094 bptr->ranges[0][0]++; 1095 break; 1096 case DELETE: 1097 bptr->ranges[1][0]++; 1098 break; 1099 case CHANGE: 1100 break; 1101 default: 1102 diff3_fatal ("internal error: invalid diff type in process_diff"); 1103 break; 1104 } 1105 1106 /* Allocate space for the pointers for the lines from filea, and 1107 parcel them out among these pointers */ 1108 if (dt != ADD) 1109 { 1110 int numlines = D_NUMLINES (bptr, 0); 1111 bptr->lines[0] = ALLOCATE (numlines, char *); 1112 bptr->lengths[0] = ALLOCATE (numlines, size_t); 1113 for (i = 0; i < numlines; i++) 1114 scan_diff = scan_diff_line (scan_diff, 1115 &(bptr->lines[0][i]), 1116 &(bptr->lengths[0][i]), 1117 diff_limit, 1118 '<'); 1119 } 1120 1121 /* Get past the separator for changes */ 1122 if (dt == CHANGE) 1123 { 1124 if (strncmp (scan_diff, "---\n", 4)) 1125 diff3_fatal ("invalid diff format; invalid change separator"); 1126 scan_diff += 4; 1127 } 1128 1129 /* Allocate space for the pointers for the lines from fileb, and 1130 parcel them out among these pointers */ 1131 if (dt != DELETE) 1132 { 1133 int numlines = D_NUMLINES (bptr, 1); 1134 bptr->lines[1] = ALLOCATE (numlines, char *); 1135 bptr->lengths[1] = ALLOCATE (numlines, size_t); 1136 for (i = 0; i < numlines; i++) 1137 scan_diff = scan_diff_line (scan_diff, 1138 &(bptr->lines[1][i]), 1139 &(bptr->lengths[1][i]), 1140 diff_limit, 1141 '>'); 1142 } 1143 1144 /* Place this block on the blocklist. */ 1145 *block_list_end = bptr; 1146 block_list_end = &bptr->next; 1147 } 1148 1149 *block_list_end = 0; 1150 *last_block = bptr; 1151 return block_list; 1152 } 1153 1154 /* 1155 * This routine will parse a normal format diff control string. It 1156 * returns the type of the diff (ERROR if the format is bad). All of 1157 * the other important information is filled into to the structure 1158 * pointed to by db, and the string pointer (whose location is passed 1159 * to this routine) is updated to point beyond the end of the string 1160 * parsed. Note that only the ranges in the diff_block will be set by 1161 * this routine. 1162 * 1163 * If some specific pair of numbers has been reduced to a single 1164 * number, then both corresponding numbers in the diff block are set 1165 * to that number. In general these numbers are interpetted as ranges 1166 * inclusive, unless being used by the ADD or DELETE commands. It is 1167 * assumed that these will be special cased in a superior routine. 1168 */ 1169 1170 static enum diff_type 1171 process_diff_control (string, db) 1172 char **string; 1173 struct diff_block *db; 1174 { 1175 char *s = *string; 1176 int holdnum; 1177 enum diff_type type; 1178 1179 /* These macros are defined here because they can use variables 1180 defined in this function. Don't try this at home kids, we're 1181 trained professionals! 1182 1183 Also note that SKIPWHITE only recognizes tabs and spaces, and 1184 that READNUM can only read positive, integral numbers */ 1185 1186 #define SKIPWHITE(s) { while (*s == ' ' || *s == '\t') s++; } 1187 #define READNUM(s, num) \ 1188 { unsigned char c = *s; if (!ISDIGIT (c)) return ERROR; holdnum = 0; \ 1189 do { holdnum = (c - '0' + holdnum * 10); } \ 1190 while (ISDIGIT (c = *++s)); (num) = holdnum; } 1191 1192 /* Read first set of digits */ 1193 SKIPWHITE (s); 1194 READNUM (s, db->ranges[0][START]); 1195 1196 /* Was that the only digit? */ 1197 SKIPWHITE (s); 1198 if (*s == ',') 1199 { 1200 /* Get the next digit */ 1201 s++; 1202 READNUM (s, db->ranges[0][END]); 1203 } 1204 else 1205 db->ranges[0][END] = db->ranges[0][START]; 1206 1207 /* Get the letter */ 1208 SKIPWHITE (s); 1209 switch (*s) 1210 { 1211 case 'a': 1212 type = ADD; 1213 break; 1214 case 'c': 1215 type = CHANGE; 1216 break; 1217 case 'd': 1218 type = DELETE; 1219 break; 1220 default: 1221 return ERROR; /* Bad format */ 1222 } 1223 s++; /* Past letter */ 1224 1225 /* Read second set of digits */ 1226 SKIPWHITE (s); 1227 READNUM (s, db->ranges[1][START]); 1228 1229 /* Was that the only digit? */ 1230 SKIPWHITE (s); 1231 if (*s == ',') 1232 { 1233 /* Get the next digit */ 1234 s++; 1235 READNUM (s, db->ranges[1][END]); 1236 SKIPWHITE (s); /* To move to end */ 1237 } 1238 else 1239 db->ranges[1][END] = db->ranges[1][START]; 1240 1241 *string = s; 1242 return type; 1243 } 1244 1245 static char * 1246 read_diff (filea, fileb, output_placement) 1247 char const *filea, *fileb; 1248 char **output_placement; 1249 { 1250 char *diff_result; 1251 size_t bytes, current_chunk_size, total; 1252 int fd, wstatus; 1253 struct stat pipestat; 1254 FILE *outfile_hold; 1255 const struct diff_callbacks *callbacks_hold; 1256 struct diff_callbacks my_callbacks; 1257 struct diff_callbacks *my_callbacks_arg; 1258 1259 /* 302 / 1000 is log10(2.0) rounded up. Subtract 1 for the sign bit; 1260 add 1 for integer division truncation; add 1 more for a minus sign. */ 1261 #define INT_STRLEN_BOUND(type) ((sizeof(type)*CHAR_BIT - 1) * 302 / 1000 + 2) 1262 1263 char const *argv[7]; 1264 char horizon_arg[17 + INT_STRLEN_BOUND (int)]; 1265 char const **ap; 1266 char *diffout; 1267 1268 ap = argv; 1269 *ap++ = "diff"; 1270 if (always_text) 1271 *ap++ = "-a"; 1272 sprintf (horizon_arg, "--horizon-lines=%d", horizon_lines); 1273 *ap++ = horizon_arg; 1274 *ap++ = "--"; 1275 *ap++ = filea; 1276 *ap++ = fileb; 1277 *ap = 0; 1278 1279 diffout = cvs_temp_name (); 1280 1281 outfile_hold = outfile; 1282 callbacks_hold = callbacks; 1283 1284 /* We want to call diff_run preserving any stdout and stderr 1285 callbacks, but discarding any callbacks to handle file output, 1286 since we want the file output to go to our temporary file. 1287 FIXME: We should use callbacks to just read it into a memory 1288 buffer; that's we do with the temporary file just below anyhow. */ 1289 if (callbacks == NULL) 1290 my_callbacks_arg = NULL; 1291 else 1292 { 1293 my_callbacks = *callbacks; 1294 my_callbacks.write_output = NULL; 1295 my_callbacks.flush_output = NULL; 1296 my_callbacks_arg = &my_callbacks; 1297 } 1298 1299 wstatus = diff_run (ap - argv, (char **) argv, diffout, my_callbacks_arg); 1300 1301 outfile = outfile_hold; 1302 callbacks = callbacks_hold; 1303 1304 if (wstatus == 2) 1305 diff3_fatal ("subsidiary diff failed"); 1306 1307 if (-1 == (fd = open (diffout, O_RDONLY))) 1308 diff3_fatal ("could not open temporary diff file"); 1309 1310 current_chunk_size = 8 * 1024; 1311 if (fstat (fd, &pipestat) == 0) 1312 current_chunk_size = max (current_chunk_size, STAT_BLOCKSIZE (pipestat)); 1313 1314 diff_result = xmalloc (current_chunk_size); 1315 total = 0; 1316 do { 1317 bytes = myread (fd, 1318 diff_result + total, 1319 current_chunk_size - total); 1320 total += bytes; 1321 if (total == current_chunk_size) 1322 { 1323 if (current_chunk_size < 2 * current_chunk_size) 1324 current_chunk_size = 2 * current_chunk_size; 1325 else if (current_chunk_size < (size_t) -1) 1326 current_chunk_size = (size_t) -1; 1327 else 1328 diff3_fatal ("files are too large to fit into memory"); 1329 diff_result = xrealloc (diff_result, (current_chunk_size *= 2)); 1330 } 1331 } while (bytes); 1332 1333 if (total != 0 && diff_result[total-1] != '\n') 1334 diff3_fatal ("invalid diff format; incomplete last line"); 1335 1336 *output_placement = diff_result; 1337 1338 if (close (fd) != 0) 1339 diff3_perror_with_exit ("pipe close"); 1340 unlink (diffout); 1341 1342 return diff_result + total; 1343 } 1344 1345 1346 /* 1347 * Scan a regular diff line (consisting of > or <, followed by a 1348 * space, followed by text (including nulls) up to a newline. 1349 * 1350 * This next routine began life as a macro and many parameters in it 1351 * are used as call-by-reference values. 1352 */ 1353 static char * 1354 scan_diff_line (scan_ptr, set_start, set_length, limit, leadingchar) 1355 char *scan_ptr, **set_start; 1356 size_t *set_length; 1357 char *limit; 1358 int leadingchar; 1359 { 1360 char *line_ptr; 1361 1362 if (!(scan_ptr[0] == leadingchar 1363 && scan_ptr[1] == ' ')) 1364 diff3_fatal ("invalid diff format; incorrect leading line chars"); 1365 1366 *set_start = line_ptr = scan_ptr + 2; 1367 while (*line_ptr++ != '\n') 1368 ; 1369 1370 /* Include newline if the original line ended in a newline, 1371 or if an edit script is being generated. 1372 Copy any missing newline message to stderr if an edit script is being 1373 generated, because edit scripts cannot handle missing newlines. 1374 Return the beginning of the next line. */ 1375 *set_length = line_ptr - *set_start; 1376 if (line_ptr < limit && *line_ptr == '\\') 1377 { 1378 if (! edscript) 1379 { 1380 --*set_length; 1381 line_ptr++; 1382 while (*line_ptr++ != '\n') 1383 ; 1384 } 1385 else 1386 { 1387 char *serr; 1388 1389 line_ptr++; 1390 serr = line_ptr; 1391 while (*line_ptr++ != '\n') 1392 ; 1393 line_ptr[-1] = '\0'; 1394 diff_error ("%s", serr, 0); 1395 line_ptr[-1] = '\n'; 1396 } 1397 } 1398 1399 return line_ptr; 1400 } 1401 1402 /* 1403 * This routine outputs a three way diff passed as a list of 1404 * diff3_block's. 1405 * The argument MAPPING is indexed by external file number (in the 1406 * argument list) and contains the internal file number (from the 1407 * diff passed). This is important because the user expects his 1408 * outputs in terms of the argument list number, and the diff passed 1409 * may have been done slightly differently (if the last argument 1410 * was "-", for example). 1411 * REV_MAPPING is the inverse of MAPPING. 1412 */ 1413 static void 1414 output_diff3 (diff, mapping, rev_mapping) 1415 struct diff3_block *diff; 1416 int const mapping[3], rev_mapping[3]; 1417 { 1418 int i; 1419 int oddoneout; 1420 char *cp; 1421 struct diff3_block *ptr; 1422 int line; 1423 size_t length; 1424 int dontprint; 1425 static int skew_increment[3] = { 2, 3, 1 }; /* 0==>2==>1==>3 */ 1426 char const *line_prefix = tab_align_flag ? "\t" : " "; 1427 1428 for (ptr = diff; ptr; ptr = D_NEXT (ptr)) 1429 { 1430 char x[2]; 1431 1432 switch (ptr->correspond) 1433 { 1434 case DIFF_ALL: 1435 x[0] = '\0'; 1436 dontprint = 3; /* Print them all */ 1437 oddoneout = 3; /* Nobody's odder than anyone else */ 1438 break; 1439 case DIFF_1ST: 1440 case DIFF_2ND: 1441 case DIFF_3RD: 1442 oddoneout = rev_mapping[(int) ptr->correspond - (int) DIFF_1ST]; 1443 1444 x[0] = oddoneout + '1'; 1445 x[1] = '\0'; 1446 dontprint = oddoneout==0; 1447 break; 1448 default: 1449 diff3_fatal ("internal error: invalid diff type passed to output"); 1450 } 1451 printf_output ("====%s\n", x); 1452 1453 /* Go 0, 2, 1 if the first and third outputs are equivalent. */ 1454 for (i = 0; i < 3; 1455 i = (oddoneout == 1 ? skew_increment[i] : i + 1)) 1456 { 1457 int realfile = mapping[i]; 1458 int 1459 lowt = D_LOWLINE (ptr, realfile), 1460 hight = D_HIGHLINE (ptr, realfile); 1461 1462 printf_output ("%d:", i + 1); 1463 switch (lowt - hight) 1464 { 1465 case 1: 1466 printf_output ("%da\n", lowt - 1); 1467 break; 1468 case 0: 1469 printf_output ("%dc\n", lowt); 1470 break; 1471 default: 1472 printf_output ("%d,%dc\n", lowt, hight); 1473 break; 1474 } 1475 1476 if (i == dontprint) continue; 1477 1478 if (lowt <= hight) 1479 { 1480 line = 0; 1481 do 1482 { 1483 printf_output (line_prefix); 1484 cp = D_RELNUM (ptr, realfile, line); 1485 length = D_RELLEN (ptr, realfile, line); 1486 write_output (cp, length); 1487 } 1488 while (++line < hight - lowt + 1); 1489 if (cp[length - 1] != '\n') 1490 printf_output ("\n\\ No newline at end of file\n"); 1491 } 1492 } 1493 } 1494 } 1495 1496 1497 /* 1498 * Output the lines of B taken from FILENUM. 1499 * Double any initial '.'s; yield nonzero if any initial '.'s were doubled. 1500 */ 1501 static int 1502 dotlines (b, filenum) 1503 struct diff3_block *b; 1504 int filenum; 1505 { 1506 int i; 1507 int leading_dot = 0; 1508 1509 for (i = 0; 1510 i < D_NUMLINES (b, filenum); 1511 i++) 1512 { 1513 char *line = D_RELNUM (b, filenum, i); 1514 if (line[0] == '.') 1515 { 1516 leading_dot = 1; 1517 write_output (".", 1); 1518 } 1519 write_output (line, D_RELLEN (b, filenum, i)); 1520 } 1521 1522 return leading_dot; 1523 } 1524 1525 /* 1526 * Output to OUTPUTFILE a '.' line. If LEADING_DOT is nonzero, 1527 * also output a command that removes initial '.'s 1528 * starting with line START and continuing for NUM lines. 1529 */ 1530 static void 1531 undotlines (leading_dot, start, num) 1532 int leading_dot, start, num; 1533 { 1534 write_output (".\n", 2); 1535 if (leading_dot) 1536 if (num == 1) 1537 printf_output ("%ds/^\\.//\n", start); 1538 else 1539 printf_output ("%d,%ds/^\\.//\n", start, start + num - 1); 1540 } 1541 1542 /* 1543 * This routine outputs a diff3 set of blocks as an ed script. This 1544 * script applies the changes between file's 2 & 3 to file 1. It 1545 * takes the precise format of the ed script to be output from global 1546 * variables set during options processing. Note that it does 1547 * destructive things to the set of diff3 blocks it is passed; it 1548 * reverses their order (this gets around the problems involved with 1549 * changing line numbers in an ed script). 1550 * 1551 * Note that this routine has the same problem of mapping as the last 1552 * one did; the variable MAPPING maps from file number according to 1553 * the argument list to file number according to the diff passed. All 1554 * files listed below are in terms of the argument list. 1555 * REV_MAPPING is the inverse of MAPPING. 1556 * 1557 * The arguments FILE0, FILE1 and FILE2 are the strings to print 1558 * as the names of the three files. These may be the actual names, 1559 * or may be the arguments specified with -L. 1560 * 1561 * Returns 1 if conflicts were found. 1562 */ 1563 1564 static int 1565 output_diff3_edscript (diff, mapping, rev_mapping, file0, file1, file2) 1566 struct diff3_block *diff; 1567 int const mapping[3], rev_mapping[3]; 1568 char const *file0, *file1, *file2; 1569 { 1570 int leading_dot; 1571 int conflicts_found = 0, conflict; 1572 struct diff3_block *b; 1573 1574 for (b = reverse_diff3_blocklist (diff); b; b = b->next) 1575 { 1576 /* Must do mapping correctly. */ 1577 enum diff_type type 1578 = ((b->correspond == DIFF_ALL) ? 1579 DIFF_ALL : 1580 ((enum diff_type) 1581 (((int) DIFF_1ST) 1582 + rev_mapping[(int) b->correspond - (int) DIFF_1ST]))); 1583 1584 /* If we aren't supposed to do this output block, skip it. */ 1585 switch (type) 1586 { 1587 default: continue; 1588 case DIFF_2ND: if (!show_2nd) continue; conflict = 1; break; 1589 case DIFF_3RD: if (overlap_only) continue; conflict = 0; break; 1590 case DIFF_ALL: if (simple_only) continue; conflict = flagging; break; 1591 } 1592 1593 if (conflict) 1594 { 1595 conflicts_found = 1; 1596 1597 1598 /* Mark end of conflict. */ 1599 1600 printf_output ("%da\n", D_HIGHLINE (b, mapping[FILE0])); 1601 leading_dot = 0; 1602 if (type == DIFF_ALL) 1603 { 1604 if (show_2nd) 1605 { 1606 /* Append lines from FILE1. */ 1607 printf_output ("||||||| %s\n", file1); 1608 leading_dot = dotlines (b, mapping[FILE1]); 1609 } 1610 /* Append lines from FILE2. */ 1611 printf_output ("=======\n"); 1612 leading_dot |= dotlines (b, mapping[FILE2]); 1613 } 1614 printf_output (">>>>>>> %s\n", file2); 1615 undotlines (leading_dot, 1616 D_HIGHLINE (b, mapping[FILE0]) + 2, 1617 (D_NUMLINES (b, mapping[FILE1]) 1618 + D_NUMLINES (b, mapping[FILE2]) + 1)); 1619 1620 1621 /* Mark start of conflict. */ 1622 1623 printf_output ("%da\n<<<<<<< %s\n", 1624 D_LOWLINE (b, mapping[FILE0]) - 1, 1625 type == DIFF_ALL ? file0 : file1); 1626 leading_dot = 0; 1627 if (type == DIFF_2ND) 1628 { 1629 /* Prepend lines from FILE1. */ 1630 leading_dot = dotlines (b, mapping[FILE1]); 1631 printf_output ("=======\n"); 1632 } 1633 undotlines (leading_dot, 1634 D_LOWLINE (b, mapping[FILE0]) + 1, 1635 D_NUMLINES (b, mapping[FILE1])); 1636 } 1637 else if (D_NUMLINES (b, mapping[FILE2]) == 0) 1638 /* Write out a delete */ 1639 { 1640 if (D_NUMLINES (b, mapping[FILE0]) == 1) 1641 printf_output ("%dd\n", D_LOWLINE (b, mapping[FILE0])); 1642 else 1643 printf_output ("%d,%dd\n", 1644 D_LOWLINE (b, mapping[FILE0]), 1645 D_HIGHLINE (b, mapping[FILE0])); 1646 } 1647 else 1648 /* Write out an add or change */ 1649 { 1650 switch (D_NUMLINES (b, mapping[FILE0])) 1651 { 1652 case 0: 1653 printf_output ("%da\n", D_HIGHLINE (b, mapping[FILE0])); 1654 break; 1655 case 1: 1656 printf_output ("%dc\n", D_HIGHLINE (b, mapping[FILE0])); 1657 break; 1658 default: 1659 printf_output ("%d,%dc\n", 1660 D_LOWLINE (b, mapping[FILE0]), 1661 D_HIGHLINE (b, mapping[FILE0])); 1662 break; 1663 } 1664 1665 undotlines (dotlines (b, mapping[FILE2]), 1666 D_LOWLINE (b, mapping[FILE0]), 1667 D_NUMLINES (b, mapping[FILE2])); 1668 } 1669 } 1670 if (finalwrite) printf_output ("w\nq\n"); 1671 return conflicts_found; 1672 } 1673 1674 /* 1675 * Read from INFILE and output to the standard output file a set of 1676 * diff3_ blocks DIFF as a merged file. This acts like 'ed file0 1677 * <[output_diff3_edscript]', except that it works even for binary 1678 * data or incomplete lines. 1679 * 1680 * As before, MAPPING maps from arg list file number to diff file number, 1681 * REV_MAPPING is its inverse, 1682 * and FILE0, FILE1, and FILE2 are the names of the files. 1683 * 1684 * Returns 1 if conflicts were found. 1685 */ 1686 1687 static int 1688 output_diff3_merge (infile, diff, mapping, rev_mapping, 1689 file0, file1, file2) 1690 FILE *infile; 1691 struct diff3_block *diff; 1692 int const mapping[3], rev_mapping[3]; 1693 char const *file0, *file1, *file2; 1694 { 1695 int c, i; 1696 char cc; 1697 int conflicts_found = 0, conflict; 1698 struct diff3_block *b; 1699 int linesread = 0; 1700 1701 for (b = diff; b; b = b->next) 1702 { 1703 /* Must do mapping correctly. */ 1704 enum diff_type type 1705 = ((b->correspond == DIFF_ALL) ? 1706 DIFF_ALL : 1707 ((enum diff_type) 1708 (((int) DIFF_1ST) 1709 + rev_mapping[(int) b->correspond - (int) DIFF_1ST]))); 1710 char const *format_2nd = "<<<<<<< %s\n"; 1711 1712 /* If we aren't supposed to do this output block, skip it. */ 1713 switch (type) 1714 { 1715 default: continue; 1716 case DIFF_2ND: if (!show_2nd) continue; conflict = 1; break; 1717 case DIFF_3RD: if (overlap_only) continue; conflict = 0; break; 1718 case DIFF_ALL: if (simple_only) continue; conflict = flagging; 1719 format_2nd = "||||||| %s\n"; 1720 break; 1721 } 1722 1723 /* Copy I lines from file 0. */ 1724 i = D_LOWLINE (b, FILE0) - linesread - 1; 1725 linesread += i; 1726 while (0 <= --i) 1727 do 1728 { 1729 c = getc (infile); 1730 if (c == EOF) 1731 if (ferror (infile)) 1732 diff3_perror_with_exit ("input file"); 1733 else if (feof (infile)) 1734 diff3_fatal ("input file shrank"); 1735 cc = c; 1736 write_output (&cc, 1); 1737 } 1738 while (c != '\n'); 1739 1740 if (conflict) 1741 { 1742 conflicts_found = 1; 1743 1744 if (type == DIFF_ALL) 1745 { 1746 /* Put in lines from FILE0 with bracket. */ 1747 printf_output ("<<<<<<< %s\n", file0); 1748 for (i = 0; 1749 i < D_NUMLINES (b, mapping[FILE0]); 1750 i++) 1751 write_output (D_RELNUM (b, mapping[FILE0], i), 1752 D_RELLEN (b, mapping[FILE0], i)); 1753 } 1754 1755 if (show_2nd) 1756 { 1757 /* Put in lines from FILE1 with bracket. */ 1758 printf_output (format_2nd, file1); 1759 for (i = 0; 1760 i < D_NUMLINES (b, mapping[FILE1]); 1761 i++) 1762 write_output (D_RELNUM (b, mapping[FILE1], i), 1763 D_RELLEN (b, mapping[FILE1], i)); 1764 } 1765 1766 printf_output ("=======\n"); 1767 } 1768 1769 /* Put in lines from FILE2. */ 1770 for (i = 0; 1771 i < D_NUMLINES (b, mapping[FILE2]); 1772 i++) 1773 write_output (D_RELNUM (b, mapping[FILE2], i), 1774 D_RELLEN (b, mapping[FILE2], i)); 1775 1776 if (conflict) 1777 printf_output (">>>>>>> %s\n", file2); 1778 1779 /* Skip I lines in file 0. */ 1780 i = D_NUMLINES (b, FILE0); 1781 linesread += i; 1782 while (0 <= --i) 1783 while ((c = getc (infile)) != '\n') 1784 if (c == EOF) 1785 if (ferror (infile)) 1786 diff3_perror_with_exit ("input file"); 1787 else if (feof (infile)) 1788 { 1789 if (i || b->next) 1790 diff3_fatal ("input file shrank"); 1791 return conflicts_found; 1792 } 1793 } 1794 /* Copy rest of common file. */ 1795 while ((c = getc (infile)) != EOF || !(ferror (infile) | feof (infile))) 1796 { 1797 cc = c; 1798 write_output (&cc, 1); 1799 } 1800 return conflicts_found; 1801 } 1802 1803 /* 1804 * Reverse the order of the list of diff3 blocks. 1805 */ 1806 static struct diff3_block * 1807 reverse_diff3_blocklist (diff) 1808 struct diff3_block *diff; 1809 { 1810 register struct diff3_block *tmp, *next, *prev; 1811 1812 for (tmp = diff, prev = 0; tmp; tmp = next) 1813 { 1814 next = tmp->next; 1815 tmp->next = prev; 1816 prev = tmp; 1817 } 1818 1819 return prev; 1820 } 1821 1822 static size_t 1823 myread (fd, ptr, size) 1824 int fd; 1825 char *ptr; 1826 size_t size; 1827 { 1828 size_t result = read (fd, ptr, size); 1829 if (result == -1) 1830 diff3_perror_with_exit ("read failed"); 1831 return result; 1832 } 1833 1834 static void 1835 diff3_fatal (string) 1836 char const *string; 1837 { 1838 diff_error ("%s", string, 0); 1839 DIFF3_ABORT (2); 1840 } 1841 1842 static void 1843 diff3_perror_with_exit (string) 1844 char const *string; 1845 { 1846 perror_with_name (string); 1847 DIFF3_ABORT (2); 1848 } 1849 1850 static void 1851 initialize_main (argcp, argvp) 1852 int *argcp; 1853 char ***argvp; 1854 { 1855 always_text = 0; 1856 edscript = 0; 1857 flagging = 0; 1858 horizon_lines = 10; 1859 tab_align_flag = 0; 1860 simple_only = 0; 1861 overlap_only = 0; 1862 show_2nd = 0; 1863 finalwrite = 0; 1864 merge = 0; 1865 diff_program_name = (*argvp)[0]; 1866 outfile = NULL; 1867 } 1868 1869 static void 1870 free_diff_blocks(p) 1871 struct diff_block *p; 1872 { 1873 register struct diff_block *next; 1874 1875 while (p) 1876 { 1877 next = p->next; 1878 if (p->lines[0]) free(p->lines[0]); 1879 if (p->lines[1]) free(p->lines[1]); 1880 if (p->lengths[0]) free(p->lengths[0]); 1881 if (p->lengths[1]) free(p->lengths[1]); 1882 free(p); 1883 p = next; 1884 } 1885 } 1886 1887 static void 1888 free_diff3_blocks(p) 1889 struct diff3_block *p; 1890 { 1891 register struct diff3_block *next; 1892 1893 while (p) 1894 { 1895 next = p->next; 1896 if (p->lines[0]) free(p->lines[0]); 1897 if (p->lines[1]) free(p->lines[1]); 1898 if (p->lines[2]) free(p->lines[2]); 1899 if (p->lengths[0]) free(p->lengths[0]); 1900 if (p->lengths[1]) free(p->lengths[1]); 1901 if (p->lengths[2]) free(p->lengths[2]); 1902 free(p); 1903 p = next; 1904 } 1905 } 1906