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