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