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