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