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