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