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