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