diff3.c revision 44852
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 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#include "diffrun.h" 26 27/* diff3.c has a real initialize_main function. */ 28#ifdef initialize_main 29#undef initialize_main 30#endif 31 32extern char const diff_version_string[]; 33 34extern FILE *outfile; 35 36extern const struct diff_callbacks *callbacks; 37 38void write_output PARAMS((char const *, size_t)); 39void printf_output PARAMS((char const *, ...)) 40#if __GNUC__ > 2 || (__GNUC__ == 2 && __GNUC_MINOR__ > 6) 41 __attribute__ ((__format__ (__printf__, 1, 2))) 42#endif 43 ; 44void flush_output PARAMS((void)); 45 46/* 47 * Internal data structures and macros for the diff3 program; includes 48 * data structures for both diff3 diffs and normal diffs. 49 */ 50 51/* Different files within a three way diff. */ 52#define FILE0 0 53#define FILE1 1 54#define FILE2 2 55 56/* 57 * A three way diff is built from two two-way diffs; the file which 58 * the two two-way diffs share is: 59 */ 60#define FILEC FILE2 61 62/* 63 * Different files within a two way diff. 64 * FC is the common file, FO the other file. 65 */ 66#define FO 0 67#define FC 1 68 69/* The ranges are indexed by */ 70#define START 0 71#define END 1 72 73enum diff_type { 74 ERROR, /* Should not be used */ 75 ADD, /* Two way diff add */ 76 CHANGE, /* Two way diff change */ 77 DELETE, /* Two way diff delete */ 78 DIFF_ALL, /* All three are different */ 79 DIFF_1ST, /* Only the first is different */ 80 DIFF_2ND, /* Only the second */ 81 DIFF_3RD /* Only the third */ 82}; 83 84/* Two way diff */ 85struct diff_block { 86 int ranges[2][2]; /* Ranges are inclusive */ 87 char **lines[2]; /* The actual lines (may contain nulls) */ 88 size_t *lengths[2]; /* Line lengths (including newlines, if any) */ 89 struct diff_block *next; 90}; 91 92/* Three way diff */ 93 94struct diff3_block { 95 enum diff_type correspond; /* Type of diff */ 96 int ranges[3][2]; /* Ranges are inclusive */ 97 char **lines[3]; /* The actual lines (may contain nulls) */ 98 size_t *lengths[3]; /* Line lengths (including newlines, if any) */ 99 struct diff3_block *next; 100}; 101 102/* 103 * Access the ranges on a diff block. 104 */ 105#define D_LOWLINE(diff, filenum) \ 106 ((diff)->ranges[filenum][START]) 107#define D_HIGHLINE(diff, filenum) \ 108 ((diff)->ranges[filenum][END]) 109#define D_NUMLINES(diff, filenum) \ 110 (D_HIGHLINE (diff, filenum) - D_LOWLINE (diff, filenum) + 1) 111 112/* 113 * Access the line numbers in a file in a diff by relative line 114 * numbers (i.e. line number within the diff itself). Note that these 115 * are lvalues and can be used for assignment. 116 */ 117#define D_RELNUM(diff, filenum, linenum) \ 118 ((diff)->lines[filenum][linenum]) 119#define D_RELLEN(diff, filenum, linenum) \ 120 ((diff)->lengths[filenum][linenum]) 121 122/* 123 * And get at them directly, when that should be necessary. 124 */ 125#define D_LINEARRAY(diff, filenum) \ 126 ((diff)->lines[filenum]) 127#define D_LENARRAY(diff, filenum) \ 128 ((diff)->lengths[filenum]) 129 130/* 131 * Next block. 132 */ 133#define D_NEXT(diff) ((diff)->next) 134 135/* 136 * Access the type of a diff3 block. 137 */ 138#define D3_TYPE(diff) ((diff)->correspond) 139 140/* 141 * Line mappings based on diffs. The first maps off the top of the 142 * diff, the second off of the bottom. 143 */ 144#define D_HIGH_MAPLINE(diff, fromfile, tofile, lineno) \ 145 ((lineno) \ 146 - D_HIGHLINE ((diff), (fromfile)) \ 147 + D_HIGHLINE ((diff), (tofile))) 148 149#define D_LOW_MAPLINE(diff, fromfile, tofile, lineno) \ 150 ((lineno) \ 151 - D_LOWLINE ((diff), (fromfile)) \ 152 + D_LOWLINE ((diff), (tofile))) 153 154/* 155 * General memory allocation function. 156 */ 157#define ALLOCATE(number, type) \ 158 (type *) xmalloc ((number) * sizeof (type)) 159 160/* Options variables for flags set on command line. */ 161 162/* If nonzero, treat all files as text files, never as binary. */ 163static int always_text; 164 165/* If nonzero, write out an ed script instead of the standard diff3 format. */ 166static int edscript; 167 168/* If nonzero, in the case of overlapping diffs (type DIFF_ALL), 169 preserve the lines which would normally be deleted from 170 file 1 with a special flagging mechanism. */ 171static int flagging; 172 173/* Number of lines to keep in identical prefix and suffix. */ 174static int horizon_lines = 10; 175 176/* Use a tab to align output lines (-T). */ 177static int tab_align_flag; 178 179/* If nonzero, do not output information for overlapping diffs. */ 180static int simple_only; 181 182/* If nonzero, do not output information for non-overlapping diffs. */ 183static int overlap_only; 184 185/* If nonzero, show information for DIFF_2ND diffs. */ 186static int show_2nd; 187 188/* If nonzero, include `:wq' at the end of the script 189 to write out the file being edited. */ 190static int finalwrite; 191 192/* If nonzero, output a merged file. */ 193static int merge; 194 195extern char *diff_program_name; 196 197static char *read_diff PARAMS((char const *, char const *, char **)); 198static char *scan_diff_line PARAMS((char *, char **, size_t *, char *, int)); 199static enum diff_type process_diff_control PARAMS((char **, struct diff_block *)); 200static int compare_line_list PARAMS((char * const[], size_t const[], char * const[], size_t const[], int)); 201static int copy_stringlist PARAMS((char * const[], size_t const[], char *[], size_t[], int)); 202static int dotlines PARAMS((struct diff3_block *, int)); 203static int output_diff3_edscript PARAMS((struct diff3_block *, int const[3], int const[3], char const *, char const *, char const *)); 204static int output_diff3_merge PARAMS((FILE *, struct diff3_block *, int const[3], int const[3], char const *, char const *, char const *)); 205static size_t myread PARAMS((int, char *, size_t)); 206static struct diff3_block *create_diff3_block PARAMS((int, int, int, int, int, int)); 207static struct diff3_block *make_3way_diff PARAMS((struct diff_block *, struct diff_block *)); 208static struct diff3_block *reverse_diff3_blocklist PARAMS((struct diff3_block *)); 209static struct diff3_block *using_to_diff3_block PARAMS((struct diff_block *[2], struct diff_block *[2], int, int, struct diff3_block const *)); 210static struct diff_block *process_diff PARAMS((char const *, char const *, struct diff_block **, char **)); 211static void check_output PARAMS((FILE *)); 212static void diff3_fatal PARAMS((char const *)); 213static void output_diff3 PARAMS((struct diff3_block *, int const[3], int const[3])); 214static void diff3_perror_with_exit PARAMS((char const *)); 215static int try_help PARAMS((char const *)); 216static void undotlines PARAMS((int, int, int)); 217static void usage PARAMS((void)); 218static void initialize_main PARAMS((int *, char ***)); 219static void free_diff_blocks PARAMS((struct diff_block *)); 220static void free_diff3_blocks PARAMS((struct diff3_block *)); 221 222/* Functions provided in libdiff.a or other external sources. */ 223VOID *xmalloc PARAMS((size_t)); 224VOID *xrealloc PARAMS((VOID *, size_t)); 225void perror_with_name PARAMS((char const *)); 226void diff_error PARAMS((char const *, char const *, char const *)); 227 228/* Permit non-local exits from diff3. */ 229static jmp_buf diff3_abort_buf; 230#define DIFF3_ABORT(retval) longjmp(diff3_abort_buf, retval) 231 232static struct option const longopts[] = 233{ 234 {"text", 0, 0, 'a'}, 235 {"show-all", 0, 0, 'A'}, 236 {"ed", 0, 0, 'e'}, 237 {"show-overlap", 0, 0, 'E'}, 238 {"label", 1, 0, 'L'}, 239 {"merge", 0, 0, 'm'}, 240 {"initial-tab", 0, 0, 'T'}, 241 {"overlap-only", 0, 0, 'x'}, 242 {"easy-only", 0, 0, '3'}, 243 {"version", 0, 0, 'v'}, 244 {"help", 0, 0, 129}, 245 {0, 0, 0, 0} 246}; 247 248/* 249 * Main program. Calls diff twice on two pairs of input files, 250 * combines the two diffs, and outputs them. 251 */ 252int 253diff3_run (argc, argv, out, callbacks_arg) 254 int argc; 255 char **argv; 256 char *out; 257 const struct diff_callbacks *callbacks_arg; 258{ 259 int c, i; 260 int mapping[3]; 261 int rev_mapping[3]; 262 int incompat = 0; 263 int conflicts_found; 264 int status; 265 struct diff_block *thread0, *thread1, *last_block; 266 char *content0, *content1; 267 struct diff3_block *diff3; 268 int tag_count = 0; 269 char *tag_strings[3]; 270 char *commonname; 271 char **file; 272 struct stat statb; 273 int optind_old; 274 int opened_file = 0; 275 276 callbacks = callbacks_arg; 277 278 initialize_main (&argc, &argv); 279 280 optind_old = optind; 281 optind = 0; 282 while ((c = getopt_long (argc, argv, "aeimvx3AEL:TX", longopts, 0)) != EOF) 283 { 284 switch (c) 285 { 286 case 'a': 287 always_text = 1; 288 break; 289 case 'A': 290 show_2nd = 1; 291 flagging = 1; 292 incompat++; 293 break; 294 case 'x': 295 overlap_only = 1; 296 incompat++; 297 break; 298 case '3': 299 simple_only = 1; 300 incompat++; 301 break; 302 case 'i': 303 finalwrite = 1; 304 break; 305 case 'm': 306 merge = 1; 307 break; 308 case 'X': 309 overlap_only = 1; 310 /* Falls through */ 311 case 'E': 312 flagging = 1; 313 /* Falls through */ 314 case 'e': 315 incompat++; 316 break; 317 case 'T': 318 tab_align_flag = 1; 319 break; 320 case 'v': 321 if (callbacks && callbacks->write_stdout) 322 { 323 (*callbacks->write_stdout) ("diff3 - GNU diffutils version "); 324 (*callbacks->write_stdout) (diff_version_string); 325 (*callbacks->write_stdout) ("\n"); 326 } 327 else 328 printf ("diff3 - GNU diffutils version %s\n", diff_version_string); 329 return 0; 330 case 129: 331 usage (); 332 if (! callbacks || ! callbacks->write_stdout) 333 check_output (stdout); 334 return 0; 335 case 'L': 336 /* Handle up to three -L options. */ 337 if (tag_count < 3) 338 { 339 tag_strings[tag_count++] = optarg; 340 break; 341 } 342 return try_help ("Too many labels were given. The limit is 3."); 343 default: 344 return try_help (0); 345 } 346 } 347 348 edscript = incompat & ~merge; /* -AeExX3 without -m implies ed script. */ 349 show_2nd |= ~incompat & merge; /* -m without -AeExX3 implies -A. */ 350 flagging |= ~incompat & merge; 351 352 if (incompat > 1 /* Ensure at most one of -AeExX3. */ 353 || finalwrite & merge /* -i -m would rewrite input file. */ 354 || (tag_count && ! flagging)) /* -L requires one of -AEX. */ 355 return try_help ("incompatible options"); 356 357 if (argc - optind != 3) 358 return try_help (argc - optind < 3 ? "missing operand" : "extra operand"); 359 360 file = &argv[optind]; 361 362 optind = optind_old; 363 364 for (i = tag_count; i < 3; i++) 365 tag_strings[i] = file[i]; 366 367 /* Always compare file1 to file2, even if file2 is "-". 368 This is needed for -mAeExX3. Using the file0 as 369 the common file would produce wrong results, because if the 370 file0-file1 diffs didn't line up with the file0-file2 diffs 371 (which is entirely possible since we don't use diff's -n option), 372 diff3 might report phantom changes from file1 to file2. */ 373 374 if (strcmp (file[2], "-") == 0) 375 { 376 /* Sigh. We've got standard input as the last arg. We can't 377 call diff twice on stdin. Use the middle arg as the common 378 file instead. */ 379 if (strcmp (file[0], "-") == 0 || strcmp (file[1], "-") == 0) 380 { 381 diff_error ("%s", "`-' specified for more than one input file", 0); 382 return 2; 383 } 384 mapping[0] = 0; 385 mapping[1] = 2; 386 mapping[2] = 1; 387 } 388 else 389 { 390 /* Normal, what you'd expect */ 391 mapping[0] = 0; 392 mapping[1] = 1; 393 mapping[2] = 2; 394 } 395 396 for (i = 0; i < 3; i++) 397 rev_mapping[mapping[i]] = i; 398 399 for (i = 0; i < 3; i++) 400 if (strcmp (file[i], "-") != 0) 401 { 402 if (stat (file[i], &statb) < 0) 403 { 404 perror_with_name (file[i]); 405 return 2; 406 } 407 else if (S_ISDIR(statb.st_mode)) 408 { 409 diff_error ("%s: Is a directory", file[i], 0); 410 return 2; 411 } 412 } 413 414 if (callbacks && callbacks->write_output) 415 { 416 if (out != NULL) 417 { 418 diff_error ("write callback with output file", 0, 0); 419 return 2; 420 } 421 } 422 else 423 { 424 if (out == NULL) 425 outfile = stdout; 426 else 427 { 428 outfile = fopen (out, "w"); 429 if (outfile == NULL) 430 { 431 perror_with_name ("could not open output file"); 432 return 2; 433 } 434 opened_file = 1; 435 } 436 } 437 438 /* Set the jump buffer, so that diff may abort execution without 439 terminating the process. */ 440 status = setjmp (diff3_abort_buf); 441 if (status != 0) 442 return status; 443 444 commonname = file[rev_mapping[FILEC]]; 445 thread1 = process_diff (file[rev_mapping[FILE1]], commonname, &last_block, 446 &content1); 447 if (thread1) 448 for (i = 0; i < 2; i++) 449 { 450 horizon_lines = max (horizon_lines, D_NUMLINES (thread1, i)); 451 horizon_lines = max (horizon_lines, D_NUMLINES (last_block, i)); 452 } 453 thread0 = process_diff (file[rev_mapping[FILE0]], commonname, &last_block, 454 &content0); 455 diff3 = make_3way_diff (thread0, thread1); 456 if (edscript) 457 conflicts_found 458 = output_diff3_edscript (diff3, mapping, rev_mapping, 459 tag_strings[0], tag_strings[1], tag_strings[2]); 460 else if (merge) 461 { 462 if (! freopen (file[rev_mapping[FILE0]], "r", stdin)) 463 diff3_perror_with_exit (file[rev_mapping[FILE0]]); 464 conflicts_found 465 = output_diff3_merge (stdin, diff3, mapping, rev_mapping, 466 tag_strings[0], tag_strings[1], tag_strings[2]); 467 if (ferror (stdin)) 468 diff3_fatal ("read error"); 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 492static int 493try_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 502static void 503check_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 */ 513static void 514usage () 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 */ 621static struct diff3_block * 622make_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 */ 802static struct diff3_block * 803using_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 */ 926static int 927copy_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 */ 956static struct diff3_block * 957create_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 */ 1025static int 1026compare_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 1049extern char **environ; 1050 1051static struct diff_block * 1052process_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 1168static enum diff_type 1169process_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 1243static char * 1244read_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 */ 1351static char * 1352scan_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 */ 1411static void 1412output_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 */ 1499static int 1500dotlines (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 */ 1528static void 1529undotlines (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 1562static int 1563output_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 1685static int 1686output_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 */ 1804static struct diff3_block * 1805reverse_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 1820static size_t 1821myread (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 1832static void 1833diff3_fatal (string) 1834 char const *string; 1835{ 1836 diff_error ("%s", string, 0); 1837 DIFF3_ABORT (2); 1838} 1839 1840static void 1841diff3_perror_with_exit (string) 1842 char const *string; 1843{ 1844 perror_with_name (string); 1845 DIFF3_ABORT (2); 1846} 1847 1848static void 1849initialize_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 1867static void 1868free_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 1885static void 1886free_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