1176491Smarcel/* Three way file comparison program (diff3) for Project GNU. 2176491Smarcel Copyright (C) 1988, 1989, 1992, 1993, 1994, 1997, 1998 Free Software Foundation, Inc. 3176491Smarcel 4176491Smarcel This program is free software; you can redistribute it and/or modify 5176491Smarcel it under the terms of the GNU General Public License as published by 6176491Smarcel the Free Software Foundation; either version 2, or (at your option) 7176491Smarcel any later version. 8176491Smarcel 9176491Smarcel This program is distributed in the hope that it will be useful, 10176491Smarcel but WITHOUT ANY WARRANTY; without even the implied warranty of 11176491Smarcel MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12176491Smarcel GNU General Public License for more details. 13176491Smarcel 14176491Smarcel */ 15176491Smarcel/* 16176491Smarcel * $FreeBSD$ 17176491Smarcel */ 18176491Smarcel 19176491Smarcel/* Written by Randy Smith */ 20176491Smarcel/* Librarification by Tim Pierce */ 21176491Smarcel 22176491Smarcel#include "system.h" 23176491Smarcel#include <stdio.h> 24176491Smarcel#include <setjmp.h> 25176491Smarcel#include "getopt.h" 26176491Smarcel#include "diffrun.h" 27176491Smarcel 28176491Smarcel/* diff3.c has a real initialize_main function. */ 29176491Smarcel#ifdef initialize_main 30176491Smarcel#undef initialize_main 31176491Smarcel#endif 32176491Smarcel 33176491Smarcelextern char const diff_version_string[]; 34176491Smarcel 35176491Smarcelextern FILE *outfile; 36176491Smarcel 37176491Smarcelextern const struct diff_callbacks *callbacks; 38176491Smarcel 39176491Smarcelvoid write_output PARAMS((char const *, size_t)); 40176491Smarcelvoid printf_output PARAMS((char const *, ...)) 41176491Smarcel#if __GNUC__ > 2 || (__GNUC__ == 2 && __GNUC_MINOR__ > 6) 42176491Smarcel __attribute__ ((__format__ (__printf__, 1, 2))) 43176491Smarcel#endif 44176491Smarcel ; 45176491Smarcelvoid flush_output PARAMS((void)); 46176491Smarcel 47176491Smarcelchar * cvs_temp_name PARAMS((void)); 48176491Smarcel 49176491Smarcel/* 50176491Smarcel * Internal data structures and macros for the diff3 program; includes 51176491Smarcel * data structures for both diff3 diffs and normal diffs. 52176491Smarcel */ 53178030Sgrehan 54176491Smarcel/* Different files within a three way diff. */ 55176491Smarcel#define FILE0 0 56176491Smarcel#define FILE1 1 57176491Smarcel#define FILE2 2 58176491Smarcel 59176491Smarcel/* 60176491Smarcel * A three way diff is built from two two-way diffs; the file which 61176491Smarcel * the two two-way diffs share is: 62176491Smarcel */ 63176491Smarcel#define FILEC FILE2 64176491Smarcel 65176491Smarcel/* 66176491Smarcel * Different files within a two way diff. 67176491Smarcel * FC is the common file, FO the other file. 68176491Smarcel */ 69176491Smarcel#define FO 0 70176491Smarcel#define FC 1 71176491Smarcel 72176491Smarcel/* The ranges are indexed by */ 73176491Smarcel#define START 0 74176491Smarcel#define END 1 75176491Smarcel 76176491Smarcelenum diff_type { 77176491Smarcel ERROR, /* Should not be used */ 78176491Smarcel ADD, /* Two way diff add */ 79176491Smarcel CHANGE, /* Two way diff change */ 80176491Smarcel DELETE, /* Two way diff delete */ 81176491Smarcel DIFF_ALL, /* All three are different */ 82176491Smarcel DIFF_1ST, /* Only the first is different */ 83176491Smarcel DIFF_2ND, /* Only the second */ 84176491Smarcel DIFF_3RD /* Only the third */ 85176491Smarcel}; 86176491Smarcel 87176491Smarcel/* Two way diff */ 88176491Smarcelstruct diff_block { 89176491Smarcel int ranges[2][2]; /* Ranges are inclusive */ 90176491Smarcel char **lines[2]; /* The actual lines (may contain nulls) */ 91176491Smarcel size_t *lengths[2]; /* Line lengths (including newlines, if any) */ 92176491Smarcel struct diff_block *next; 93176491Smarcel}; 94176491Smarcel 95176491Smarcel/* Three way diff */ 96176491Smarcel 97176491Smarcelstruct diff3_block { 98176491Smarcel enum diff_type correspond; /* Type of diff */ 99176491Smarcel int ranges[3][2]; /* Ranges are inclusive */ 100176491Smarcel char **lines[3]; /* The actual lines (may contain nulls) */ 101176491Smarcel size_t *lengths[3]; /* Line lengths (including newlines, if any) */ 102176491Smarcel struct diff3_block *next; 103176491Smarcel}; 104176491Smarcel 105176491Smarcel/* 106176491Smarcel * Access the ranges on a diff block. 107176491Smarcel */ 108176491Smarcel#define D_LOWLINE(diff, filenum) \ 109176491Smarcel ((diff)->ranges[filenum][START]) 110176491Smarcel#define D_HIGHLINE(diff, filenum) \ 111176491Smarcel ((diff)->ranges[filenum][END]) 112176491Smarcel#define D_NUMLINES(diff, filenum) \ 113176491Smarcel (D_HIGHLINE (diff, filenum) - D_LOWLINE (diff, filenum) + 1) 114176491Smarcel 115176491Smarcel/* 116176491Smarcel * Access the line numbers in a file in a diff by relative line 117176491Smarcel * numbers (i.e. line number within the diff itself). Note that these 118176491Smarcel * are lvalues and can be used for assignment. 119176491Smarcel */ 120176491Smarcel#define D_RELNUM(diff, filenum, linenum) \ 121176491Smarcel ((diff)->lines[filenum][linenum]) 122176491Smarcel#define D_RELLEN(diff, filenum, linenum) \ 123176491Smarcel ((diff)->lengths[filenum][linenum]) 124176491Smarcel 125176491Smarcel/* 126176491Smarcel * And get at them directly, when that should be necessary. 127176491Smarcel */ 128176491Smarcel#define D_LINEARRAY(diff, filenum) \ 129176491Smarcel ((diff)->lines[filenum]) 130176491Smarcel#define D_LENARRAY(diff, filenum) \ 131176491Smarcel ((diff)->lengths[filenum]) 132176491Smarcel 133176491Smarcel/* 134176491Smarcel * Next block. 135176491Smarcel */ 136176491Smarcel#define D_NEXT(diff) ((diff)->next) 137176491Smarcel 138176491Smarcel/* 139176491Smarcel * Access the type of a diff3 block. 140176491Smarcel */ 141176491Smarcel#define D3_TYPE(diff) ((diff)->correspond) 142176491Smarcel 143176491Smarcel/* 144176491Smarcel * Line mappings based on diffs. The first maps off the top of the 145176491Smarcel * diff, the second off of the bottom. 146176491Smarcel */ 147176491Smarcel#define D_HIGH_MAPLINE(diff, fromfile, tofile, lineno) \ 148176491Smarcel ((lineno) \ 149176491Smarcel - D_HIGHLINE ((diff), (fromfile)) \ 150176491Smarcel + D_HIGHLINE ((diff), (tofile))) 151176491Smarcel 152176491Smarcel#define D_LOW_MAPLINE(diff, fromfile, tofile, lineno) \ 153176491Smarcel ((lineno) \ 154176491Smarcel - D_LOWLINE ((diff), (fromfile)) \ 155176491Smarcel + D_LOWLINE ((diff), (tofile))) 156176491Smarcel 157176491Smarcel/* 158176491Smarcel * General memory allocation function. 159176491Smarcel */ 160176491Smarcel#define ALLOCATE(number, type) \ 161176491Smarcel (type *) xmalloc ((number) * sizeof (type)) 162176491Smarcel 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 const 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 /* Also try to compare file0 to file1 because this is the where 377 changes are expected to come from. Diffing between these pairs 378 of files is is most likely to return the intended changes. There 379 can also be the same problem with phantom changes from file0 to 380 file1. */ 381 /* Historically, the default common file was file2. Ediff for emacs 382 and possibly other applications, have therefore made file2 the 383 ancestor. So, for compatibility, if this is simply a three 384 way diff (not a merge or edscript) then use the old way with 385 file2 as the common file. */ 386 387 { 388 int common; 389 if (edscript || merge ) 390 { 391 common = 1; 392 } 393 else 394 { 395 common = 2; 396 } 397 if (strcmp (file[common], "-") == 0) 398 { 399 /* Sigh. We've got standard input as the arg corresponding to 400 the desired common file. We can't call diff twice on 401 stdin. Use another arg as the common file instead. */ 402 common = 3 - common; 403 if (strcmp (file[0], "-") == 0 || strcmp (file[common], "-") == 0) 404 { 405 diff_error ("%s", "`-' specified for more than one input file", 0); 406 return 2; 407 } 408 } 409 410 mapping[0] = 0; 411 mapping[1] = 3 - common; 412 mapping[2] = common; 413 } 414 415 for (i = 0; i < 3; i++) 416 rev_mapping[mapping[i]] = i; 417 418 for (i = 0; i < 3; i++) 419 if (strcmp (file[i], "-") != 0) 420 { 421 if (stat (file[i], &statb) < 0) 422 { 423 perror_with_name (file[i]); 424 return 2; 425 } 426 else if (S_ISDIR(statb.st_mode)) 427 { 428 diff_error ("%s: Is a directory", file[i], 0); 429 return 2; 430 } 431 } 432 433 if (callbacks && callbacks->write_output) 434 { 435 if (out != NULL) 436 { 437 diff_error ("write callback with output file", 0, 0); 438 return 2; 439 } 440 } 441 else 442 { 443 if (out == NULL) 444 outfile = stdout; 445 else 446 { 447 outfile = fopen (out, "w"); 448 if (outfile == NULL) 449 { 450 perror_with_name (out); 451 return 2; 452 } 453 opened_file = 1; 454 } 455 } 456 457 /* Set the jump buffer, so that diff may abort execution without 458 terminating the process. */ 459 status = setjmp (diff3_abort_buf); 460 if (status != 0) 461 return status; 462 463 commonname = file[rev_mapping[FILEC]]; 464 thread1 = process_diff (file[rev_mapping[FILE1]], commonname, &last_block, 465 &content1); 466 /* What is the intention behind determining horizon_lines from first 467 diff? I think it is better to use the same parameters for each 468 diff so that equal differences in each diff will appear the 469 same. */ 470 /* 471 if (thread1) 472 for (i = 0; i < 2; i++) 473 { 474 horizon_lines = max (horizon_lines, D_NUMLINES (thread1, i)); 475 horizon_lines = max (horizon_lines, D_NUMLINES (last_block, i)); 476 } 477 */ 478 thread0 = process_diff (file[rev_mapping[FILE0]], commonname, &last_block, 479 &content0); 480 diff3 = make_3way_diff (thread0, thread1); 481 if (edscript) 482 conflicts_found 483 = output_diff3_edscript (diff3, mapping, rev_mapping, 484 tag_strings[0], tag_strings[1], tag_strings[2]); 485 else if (merge) 486 { 487 FILE *mfp = fopen (file[rev_mapping[FILE0]], "r"); 488 if (! mfp) 489 diff3_perror_with_exit (file[rev_mapping[FILE0]]); 490 conflicts_found = output_diff3_merge (mfp, diff3, mapping, rev_mapping, 491 tag_strings[0], tag_strings[1], tag_strings[2]); 492 if (ferror (mfp)) 493 diff3_fatal ("read error"); 494 if (fclose(mfp) != 0) 495 perror_with_name (file[rev_mapping[FILE0]]); 496 } 497 else 498 { 499 output_diff3 (diff3, mapping, rev_mapping); 500 conflicts_found = 0; 501 } 502 503 free(content0); 504 free(content1); 505 free_diff3_blocks(diff3); 506 507 if (! callbacks || ! callbacks->write_output) 508 check_output (outfile); 509 510 if (opened_file) 511 if (fclose (outfile) != 0) 512 perror_with_name ("close error on output file"); 513 514 return conflicts_found; 515} 516 517static int 518try_help (reason) 519 char const *reason; 520{ 521 if (reason) 522 diff_error ("%s", reason, 0); 523 diff_error ("Try `%s --help' for more information.", diff_program_name, 0); 524 return 2; 525} 526 527static void 528check_output (stream) 529 FILE *stream; 530{ 531 if (ferror (stream) || fflush (stream) != 0) 532 diff3_fatal ("write error"); 533} 534 535/* 536 * Explain, patiently and kindly, how to use this program. 537 */ 538static void 539usage () 540{ 541 if (callbacks && callbacks->write_stdout) 542 { 543 (*callbacks->write_stdout) ("Usage: "); 544 (*callbacks->write_stdout) (diff_program_name); 545 (*callbacks->write_stdout) (" [OPTION]... MYFILE OLDFILE YOURFILE\n\n"); 546 547 (*callbacks->write_stdout) ("\ 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 (*callbacks->write_stdout) ("\ 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 (*callbacks->write_stdout) ("\ 561 -v --version Output version info.\n\ 562 --help Output this help.\n\n"); 563 (*callbacks->write_stdout) ("If a FILE is `-', read standard input.\n"); 564 } 565 else 566 { 567 printf ("Usage: %s [OPTION]... MYFILE OLDFILE YOURFILE\n\n", diff_program_name); 568 569 printf ("%s", "\ 570 -e --ed Output unmerged changes from OLDFILE to YOURFILE into MYFILE.\n\ 571 -E --show-overlap Output unmerged changes, bracketing conflicts.\n\ 572 -A --show-all Output all changes, bracketing conflicts.\n\ 573 -x --overlap-only Output overlapping changes.\n\ 574 -X Output overlapping changes, bracketing them.\n\ 575 -3 --easy-only Output unmerged nonoverlapping changes.\n\n"); 576 printf ("%s", "\ 577 -m --merge Output merged file instead of ed script (default -A).\n\ 578 -L LABEL --label=LABEL Use LABEL instead of file name.\n\ 579 -i Append `w' and `q' commands to ed scripts.\n\ 580 -a --text Treat all files as text.\n\ 581 -T --initial-tab Make tabs line up by prepending a tab.\n\n"); 582 printf ("%s", "\ 583 -v --version Output version info.\n\ 584 --help Output this help.\n\n"); 585 printf ("If a FILE is `-', read standard input.\n"); 586 } 587} 588 589/* 590 * Routines that combine the two diffs together into one. The 591 * algorithm used follows: 592 * 593 * File2 is shared in common between the two diffs. 594 * Diff02 is the diff between 0 and 2. 595 * Diff12 is the diff between 1 and 2. 596 * 597 * 1) Find the range for the first block in File2. 598 * a) Take the lowest of the two ranges (in File2) in the two 599 * current blocks (one from each diff) as being the low 600 * water mark. Assign the upper end of this block as 601 * being the high water mark and move the current block up 602 * one. Mark the block just moved over as to be used. 603 * b) Check the next block in the diff that the high water 604 * mark is *not* from. 605 * 606 * *If* the high water mark is above 607 * the low end of the range in that block, 608 * 609 * mark that block as to be used and move the current 610 * block up. Set the high water mark to the max of 611 * the high end of this block and the current. Repeat b. 612 * 613 * 2) Find the corresponding ranges in File0 (from the blocks 614 * in diff02; line per line outside of diffs) and in File1. 615 * Create a diff3_block, reserving space as indicated by the ranges. 616 * 617 * 3) Copy all of the pointers for file2 in. At least for now, 618 * do memcmp's between corresponding strings in the two diffs. 619 * 620 * 4) Copy all of the pointers for file0 and 1 in. Get what you 621 * need from file2 (when there isn't a diff block, it's 622 * identical to file2 within the range between diff blocks). 623 * 624 * 5) If the diff blocks you used came from only one of the two 625 * strings of diffs, then that file (i.e. the one other than 626 * the common file in that diff) is the odd person out. If you used 627 * diff blocks from both sets, check to see if files 0 and 1 match: 628 * 629 * Same number of lines? If so, do a set of memcmp's (if a 630 * memcmp matches; copy the pointer over; it'll be easier later 631 * if you have to do any compares). If they match, 0 & 1 are 632 * the same. If not, all three different. 633 * 634 * Then you do it again, until you run out of blocks. 635 * 636 */ 637 638/* 639 * This routine makes a three way diff (chain of diff3_block's) from two 640 * two way diffs (chains of diff_block's). It is assumed that each of 641 * the two diffs passed are onto the same file (i.e. that each of the 642 * diffs were made "to" the same file). The three way diff pointer 643 * returned will have numbering FILE0--the other file in diff02, 644 * FILE1--the other file in diff12, and FILEC--the common file. 645 */ 646static struct diff3_block * 647make_3way_diff (thread0, thread1) 648 struct diff_block *thread0, *thread1; 649{ 650/* 651 * This routine works on the two diffs passed to it as threads. 652 * Thread number 0 is diff02, thread number 1 is diff12. The USING 653 * array is set to the base of the list of blocks to be used to 654 * construct each block of the three way diff; if no blocks from a 655 * particular thread are to be used, that element of the using array 656 * is set to 0. The elements LAST_USING array are set to the last 657 * elements on each of the using lists. 658 * 659 * The HIGH_WATER_MARK is set to the highest line number in the common file 660 * described in any of the diffs in either of the USING lists. The 661 * HIGH_WATER_THREAD names the thread. Similarly the BASE_WATER_MARK 662 * and BASE_WATER_THREAD describe the lowest line number in the common file 663 * described in any of the diffs in either of the USING lists. The 664 * HIGH_WATER_DIFF is the diff from which the HIGH_WATER_MARK was 665 * taken. 666 * 667 * The HIGH_WATER_DIFF should always be equal to LAST_USING 668 * [HIGH_WATER_THREAD]. The OTHER_DIFF is the next diff to check for 669 * higher water, and should always be equal to 670 * CURRENT[HIGH_WATER_THREAD ^ 0x1]. The OTHER_THREAD is the thread 671 * in which the OTHER_DIFF is, and hence should always be equal to 672 * HIGH_WATER_THREAD ^ 0x1. 673 * 674 * The variable LAST_DIFF is kept set to the last diff block produced 675 * by this routine, for line correspondence purposes between that diff 676 * and the one currently being worked on. It is initialized to 677 * ZERO_DIFF before any blocks have been created. 678 */ 679 680 struct diff_block 681 *using[2], 682 *last_using[2], 683 *current[2]; 684 685 int 686 high_water_mark; 687 688 int 689 high_water_thread, 690 base_water_thread, 691 other_thread; 692 693 struct diff_block 694 *high_water_diff, 695 *other_diff; 696 697 struct diff3_block 698 *result, 699 *tmpblock, 700 **result_end; 701 702 struct diff3_block const *last_diff3; 703 704 static struct diff3_block const zero_diff3 = { 0 }; 705 706 /* Initialization */ 707 result = 0; 708 result_end = &result; 709 current[0] = thread0; current[1] = thread1; 710 last_diff3 = &zero_diff3; 711 712 /* Sniff up the threads until we reach the end */ 713 714 while (current[0] || current[1]) 715 { 716 using[0] = using[1] = last_using[0] = last_using[1] = 0; 717 718 /* Setup low and high water threads, diffs, and marks. */ 719 if (!current[0]) 720 base_water_thread = 1; 721 else if (!current[1]) 722 base_water_thread = 0; 723 else 724 base_water_thread = 725 (D_LOWLINE (current[0], FC) > D_LOWLINE (current[1], FC)); 726 727 high_water_thread = base_water_thread; 728 729 high_water_diff = current[high_water_thread]; 730 731#if 0 732 /* low and high waters start off same diff */ 733 base_water_mark = D_LOWLINE (high_water_diff, FC); 734#endif 735 736 high_water_mark = D_HIGHLINE (high_water_diff, FC); 737 738 /* Make the diff you just got info from into the using class */ 739 using[high_water_thread] 740 = last_using[high_water_thread] 741 = high_water_diff; 742 current[high_water_thread] = high_water_diff->next; 743 last_using[high_water_thread]->next = 0; 744 745 /* And mark the other diff */ 746 other_thread = high_water_thread ^ 0x1; 747 other_diff = current[other_thread]; 748 749 /* Shuffle up the ladder, checking the other diff to see if it 750 needs to be incorporated. */ 751 while (other_diff 752 && D_LOWLINE (other_diff, FC) <= high_water_mark + 1) 753 { 754 755 /* Incorporate this diff into the using list. Note that 756 this doesn't take it off the current list */ 757 if (using[other_thread]) 758 last_using[other_thread]->next = other_diff; 759 else 760 using[other_thread] = other_diff; 761 last_using[other_thread] = other_diff; 762 763 /* Take it off the current list. Note that this following 764 code assumes that other_diff enters it equal to 765 current[high_water_thread ^ 0x1] */ 766 current[other_thread] = current[other_thread]->next; 767 other_diff->next = 0; 768 769 /* Set the high_water stuff 770 If this comparison is equal, then this is the last pass 771 through this loop; since diff blocks within a given 772 thread cannot overlap, the high_water_mark will be 773 *below* the range_start of either of the next diffs. */ 774 775 if (high_water_mark < D_HIGHLINE (other_diff, FC)) 776 { 777 high_water_thread ^= 1; 778 high_water_diff = other_diff; 779 high_water_mark = D_HIGHLINE (other_diff, FC); 780 } 781 782 /* Set the other diff */ 783 other_thread = high_water_thread ^ 0x1; 784 other_diff = current[other_thread]; 785 } 786 787 /* The using lists contain a list of all of the blocks to be 788 included in this diff3_block. Create it. */ 789 790 tmpblock = using_to_diff3_block (using, last_using, 791 base_water_thread, high_water_thread, 792 last_diff3); 793 free_diff_blocks(using[0]); 794 free_diff_blocks(using[1]); 795 796 if (!tmpblock) 797 diff3_fatal ("internal error: screwup in format of diff blocks"); 798 799 /* Put it on the list. */ 800 *result_end = tmpblock; 801 result_end = &tmpblock->next; 802 803 /* Set up corresponding lines correctly. */ 804 last_diff3 = tmpblock; 805 } 806 return result; 807} 808 809/* 810 * using_to_diff3_block: 811 * This routine takes two lists of blocks (from two separate diff 812 * threads) and puts them together into one diff3 block. 813 * It then returns a pointer to this diff3 block or 0 for failure. 814 * 815 * All arguments besides using are for the convenience of the routine; 816 * they could be derived from the using array. 817 * LAST_USING is a pair of pointers to the last blocks in the using 818 * structure. 819 * LOW_THREAD and HIGH_THREAD tell which threads contain the lowest 820 * and highest line numbers for File0. 821 * last_diff3 contains the last diff produced in the calling routine. 822 * This is used for lines mappings which would still be identical to 823 * the state that diff ended in. 824 * 825 * A distinction should be made in this routine between the two diffs 826 * that are part of a normal two diff block, and the three diffs that 827 * are part of a diff3_block. 828 */ 829static struct diff3_block * 830using_to_diff3_block (using, last_using, low_thread, high_thread, last_diff3) 831 struct diff_block 832 *using[2], 833 *last_using[2]; 834 int low_thread, high_thread; 835 struct diff3_block const *last_diff3; 836{ 837 int low[2], high[2]; 838 struct diff3_block *result; 839 struct diff_block *ptr; 840 int d, i; 841 842 /* Find the range in the common file. */ 843 int lowc = D_LOWLINE (using[low_thread], FC); 844 int highc = D_HIGHLINE (last_using[high_thread], FC); 845 846 /* Find the ranges in the other files. 847 If using[d] is null, that means that the file to which that diff 848 refers is equivalent to the common file over this range. */ 849 850 for (d = 0; d < 2; d++) 851 if (using[d]) 852 { 853 low[d] = D_LOW_MAPLINE (using[d], FC, FO, lowc); 854 high[d] = D_HIGH_MAPLINE (last_using[d], FC, FO, highc); 855 } 856 else 857 { 858 low[d] = D_HIGH_MAPLINE (last_diff3, FILEC, FILE0 + d, lowc); 859 high[d] = D_HIGH_MAPLINE (last_diff3, FILEC, FILE0 + d, highc); 860 } 861 862 /* Create a block with the appropriate sizes */ 863 result = create_diff3_block (low[0], high[0], low[1], high[1], lowc, highc); 864 865 /* Copy information for the common file. 866 Return with a zero if any of the compares failed. */ 867 868 for (d = 0; d < 2; d++) 869 for (ptr = using[d]; ptr; ptr = D_NEXT (ptr)) 870 { 871 int result_offset = D_LOWLINE (ptr, FC) - lowc; 872 873 if (!copy_stringlist (D_LINEARRAY (ptr, FC), 874 D_LENARRAY (ptr, FC), 875 D_LINEARRAY (result, FILEC) + result_offset, 876 D_LENARRAY (result, FILEC) + result_offset, 877 D_NUMLINES (ptr, FC))) 878 return 0; 879 } 880 881 /* Copy information for file d. First deal with anything that might be 882 before the first diff. */ 883 884 for (d = 0; d < 2; d++) 885 { 886 struct diff_block *u = using[d]; 887 int lo = low[d], hi = high[d]; 888 889 for (i = 0; 890 i + lo < (u ? D_LOWLINE (u, FO) : hi + 1); 891 i++) 892 { 893 D_RELNUM (result, FILE0 + d, i) = D_RELNUM (result, FILEC, i); 894 D_RELLEN (result, FILE0 + d, i) = D_RELLEN (result, FILEC, i); 895 } 896 897 for (ptr = u; ptr; ptr = D_NEXT (ptr)) 898 { 899 int result_offset = D_LOWLINE (ptr, FO) - lo; 900 int linec; 901 902 if (!copy_stringlist (D_LINEARRAY (ptr, FO), 903 D_LENARRAY (ptr, FO), 904 D_LINEARRAY (result, FILE0 + d) + result_offset, 905 D_LENARRAY (result, FILE0 + d) + result_offset, 906 D_NUMLINES (ptr, FO))) 907 return 0; 908 909 /* Catch the lines between here and the next diff */ 910 linec = D_HIGHLINE (ptr, FC) + 1 - lowc; 911 for (i = D_HIGHLINE (ptr, FO) + 1 - lo; 912 i < (D_NEXT (ptr) ? D_LOWLINE (D_NEXT (ptr), FO) : hi + 1) - lo; 913 i++) 914 { 915 D_RELNUM (result, FILE0 + d, i) = D_RELNUM (result, FILEC, linec); 916 D_RELLEN (result, FILE0 + d, i) = D_RELLEN (result, FILEC, linec); 917 linec++; 918 } 919 } 920 } 921 922 /* Set correspond */ 923 if (!using[0]) 924 D3_TYPE (result) = DIFF_2ND; 925 else if (!using[1]) 926 D3_TYPE (result) = DIFF_1ST; 927 else 928 { 929 int nl0 = D_NUMLINES (result, FILE0); 930 int nl1 = D_NUMLINES (result, FILE1); 931 932 if (nl0 != nl1 933 || !compare_line_list (D_LINEARRAY (result, FILE0), 934 D_LENARRAY (result, FILE0), 935 D_LINEARRAY (result, FILE1), 936 D_LENARRAY (result, FILE1), 937 nl0)) 938 D3_TYPE (result) = DIFF_ALL; 939 else 940 D3_TYPE (result) = DIFF_3RD; 941 } 942 943 return result; 944} 945 946/* 947 * This routine copies pointers from a list of strings to a different list 948 * of strings. If a spot in the second list is already filled, it 949 * makes sure that it is filled with the same string; if not it 950 * returns 0, the copy incomplete. 951 * Upon successful completion of the copy, it returns 1. 952 */ 953static int 954copy_stringlist (fromptrs, fromlengths, toptrs, tolengths, copynum) 955 char * const fromptrs[]; 956 char *toptrs[]; 957 size_t const fromlengths[]; 958 size_t tolengths[]; 959 int copynum; 960{ 961 register char * const *f = fromptrs; 962 register char **t = toptrs; 963 register size_t const *fl = fromlengths; 964 register size_t *tl = tolengths; 965 966 while (copynum--) 967 { 968 if (*t) 969 { if (*fl != *tl || memcmp (*f, *t, *fl)) return 0; } 970 else 971 { *t = *f ; *tl = *fl; } 972 973 t++; f++; tl++; fl++; 974 } 975 return 1; 976} 977 978/* 979 * Create a diff3_block, with ranges as specified in the arguments. 980 * Allocate the arrays for the various pointers (and zero them) based 981 * on the arguments passed. Return the block as a result. 982 */ 983static struct diff3_block * 984create_diff3_block (low0, high0, low1, high1, low2, high2) 985 register int low0, high0, low1, high1, low2, high2; 986{ 987 struct diff3_block *result = ALLOCATE (1, struct diff3_block); 988 int numlines; 989 990 D3_TYPE (result) = ERROR; 991 D_NEXT (result) = 0; 992 993 /* Assign ranges */ 994 D_LOWLINE (result, FILE0) = low0; 995 D_HIGHLINE (result, FILE0) = high0; 996 D_LOWLINE (result, FILE1) = low1; 997 D_HIGHLINE (result, FILE1) = high1; 998 D_LOWLINE (result, FILE2) = low2; 999 D_HIGHLINE (result, FILE2) = high2; 1000 1001 /* Allocate and zero space */ 1002 numlines = D_NUMLINES (result, FILE0); 1003 if (numlines) 1004 { 1005 D_LINEARRAY (result, FILE0) = ALLOCATE (numlines, char *); 1006 D_LENARRAY (result, FILE0) = ALLOCATE (numlines, size_t); 1007 bzero (D_LINEARRAY (result, FILE0), (numlines * sizeof (char *))); 1008 bzero (D_LENARRAY (result, FILE0), (numlines * sizeof (size_t))); 1009 } 1010 else 1011 { 1012 D_LINEARRAY (result, FILE0) = 0; 1013 D_LENARRAY (result, FILE0) = 0; 1014 } 1015 1016 numlines = D_NUMLINES (result, FILE1); 1017 if (numlines) 1018 { 1019 D_LINEARRAY (result, FILE1) = ALLOCATE (numlines, char *); 1020 D_LENARRAY (result, FILE1) = ALLOCATE (numlines, size_t); 1021 bzero (D_LINEARRAY (result, FILE1), (numlines * sizeof (char *))); 1022 bzero (D_LENARRAY (result, FILE1), (numlines * sizeof (size_t))); 1023 } 1024 else 1025 { 1026 D_LINEARRAY (result, FILE1) = 0; 1027 D_LENARRAY (result, FILE1) = 0; 1028 } 1029 1030 numlines = D_NUMLINES (result, FILE2); 1031 if (numlines) 1032 { 1033 D_LINEARRAY (result, FILE2) = ALLOCATE (numlines, char *); 1034 D_LENARRAY (result, FILE2) = ALLOCATE (numlines, size_t); 1035 bzero (D_LINEARRAY (result, FILE2), (numlines * sizeof (char *))); 1036 bzero (D_LENARRAY (result, FILE2), (numlines * sizeof (size_t))); 1037 } 1038 else 1039 { 1040 D_LINEARRAY (result, FILE2) = 0; 1041 D_LENARRAY (result, FILE2) = 0; 1042 } 1043 1044 /* Return */ 1045 return result; 1046} 1047 1048/* 1049 * Compare two lists of lines of text. 1050 * Return 1 if they are equivalent, 0 if not. 1051 */ 1052static int 1053compare_line_list (list1, lengths1, list2, lengths2, nl) 1054 char * const list1[], * const list2[]; 1055 size_t const lengths1[], lengths2[]; 1056 int nl; 1057{ 1058 char 1059 * const *l1 = list1, 1060 * const *l2 = list2; 1061 size_t const 1062 *lgths1 = lengths1, 1063 *lgths2 = lengths2; 1064 1065 while (nl--) 1066 if (!*l1 || !*l2 || *lgths1 != *lgths2++ 1067 || memcmp (*l1++, *l2++, *lgths1++)) 1068 return 0; 1069 return 1; 1070} 1071 1072/* 1073 * Routines to input and parse two way diffs. 1074 */ 1075 1076extern char **environ; 1077 1078static struct diff_block * 1079process_diff (filea, fileb, last_block, diff_contents) 1080 char const *filea, *fileb; 1081 struct diff_block **last_block; 1082 char **diff_contents; 1083{ 1084 char *diff_limit; 1085 char *scan_diff; 1086 enum diff_type dt; 1087 int i; 1088 struct diff_block *block_list, **block_list_end, *bptr; 1089 1090 diff_limit = read_diff (filea, fileb, diff_contents); 1091 scan_diff = *diff_contents; 1092 block_list_end = &block_list; 1093 bptr = 0; /* Pacify `gcc -W'. */ 1094 1095 while (scan_diff < diff_limit) 1096 { 1097 bptr = ALLOCATE (1, struct diff_block); 1098 bptr->lines[0] = bptr->lines[1] = 0; 1099 bptr->lengths[0] = bptr->lengths[1] = 0; 1100 1101 dt = process_diff_control (&scan_diff, bptr); 1102 if (dt == ERROR || *scan_diff != '\n') 1103 { 1104 char *serr; 1105 1106 for (serr = scan_diff; *serr != '\n'; serr++) 1107 ; 1108 *serr = '\0'; 1109 diff_error ("diff error: %s", scan_diff, 0); 1110 *serr = '\n'; 1111 DIFF3_ABORT (2); 1112 } 1113 scan_diff++; 1114 1115 /* Force appropriate ranges to be null, if necessary */ 1116 switch (dt) 1117 { 1118 case ADD: 1119 bptr->ranges[0][0]++; 1120 break; 1121 case DELETE: 1122 bptr->ranges[1][0]++; 1123 break; 1124 case CHANGE: 1125 break; 1126 default: 1127 diff3_fatal ("internal error: invalid diff type in process_diff"); 1128 break; 1129 } 1130 1131 /* Allocate space for the pointers for the lines from filea, and 1132 parcel them out among these pointers */ 1133 if (dt != ADD) 1134 { 1135 int numlines = D_NUMLINES (bptr, 0); 1136 bptr->lines[0] = ALLOCATE (numlines, char *); 1137 bptr->lengths[0] = ALLOCATE (numlines, size_t); 1138 for (i = 0; i < numlines; i++) 1139 scan_diff = scan_diff_line (scan_diff, 1140 &(bptr->lines[0][i]), 1141 &(bptr->lengths[0][i]), 1142 diff_limit, 1143 '<'); 1144 } 1145 1146 /* Get past the separator for changes */ 1147 if (dt == CHANGE) 1148 { 1149 if (strncmp (scan_diff, "---\n", 4)) 1150 diff3_fatal ("invalid diff format; invalid change separator"); 1151 scan_diff += 4; 1152 } 1153 1154 /* Allocate space for the pointers for the lines from fileb, and 1155 parcel them out among these pointers */ 1156 if (dt != DELETE) 1157 { 1158 int numlines = D_NUMLINES (bptr, 1); 1159 bptr->lines[1] = ALLOCATE (numlines, char *); 1160 bptr->lengths[1] = ALLOCATE (numlines, size_t); 1161 for (i = 0; i < numlines; i++) 1162 scan_diff = scan_diff_line (scan_diff, 1163 &(bptr->lines[1][i]), 1164 &(bptr->lengths[1][i]), 1165 diff_limit, 1166 '>'); 1167 } 1168 1169 /* Place this block on the blocklist. */ 1170 *block_list_end = bptr; 1171 block_list_end = &bptr->next; 1172 } 1173 1174 *block_list_end = 0; 1175 *last_block = bptr; 1176 return block_list; 1177} 1178 1179/* 1180 * This routine will parse a normal format diff control string. It 1181 * returns the type of the diff (ERROR if the format is bad). All of 1182 * the other important information is filled into to the structure 1183 * pointed to by db, and the string pointer (whose location is passed 1184 * to this routine) is updated to point beyond the end of the string 1185 * parsed. Note that only the ranges in the diff_block will be set by 1186 * this routine. 1187 * 1188 * If some specific pair of numbers has been reduced to a single 1189 * number, then both corresponding numbers in the diff block are set 1190 * to that number. In general these numbers are interpetted as ranges 1191 * inclusive, unless being used by the ADD or DELETE commands. It is 1192 * assumed that these will be special cased in a superior routine. 1193 */ 1194 1195static enum diff_type 1196process_diff_control (string, db) 1197 char **string; 1198 struct diff_block *db; 1199{ 1200 char *s = *string; 1201 int holdnum; 1202 enum diff_type type; 1203 1204/* These macros are defined here because they can use variables 1205 defined in this function. Don't try this at home kids, we're 1206 trained professionals! 1207 1208 Also note that SKIPWHITE only recognizes tabs and spaces, and 1209 that READNUM can only read positive, integral numbers */ 1210 1211#define SKIPWHITE(s) { while (*s == ' ' || *s == '\t') s++; } 1212#define READNUM(s, num) \ 1213 { unsigned char c = *s; if (!ISDIGIT (c)) return ERROR; holdnum = 0; \ 1214 do { holdnum = (c - '0' + holdnum * 10); } \ 1215 while (ISDIGIT (c = *++s)); (num) = holdnum; } 1216 1217 /* Read first set of digits */ 1218 SKIPWHITE (s); 1219 READNUM (s, db->ranges[0][START]); 1220 1221 /* Was that the only digit? */ 1222 SKIPWHITE (s); 1223 if (*s == ',') 1224 { 1225 /* Get the next digit */ 1226 s++; 1227 READNUM (s, db->ranges[0][END]); 1228 } 1229 else 1230 db->ranges[0][END] = db->ranges[0][START]; 1231 1232 /* Get the letter */ 1233 SKIPWHITE (s); 1234 switch (*s) 1235 { 1236 case 'a': 1237 type = ADD; 1238 break; 1239 case 'c': 1240 type = CHANGE; 1241 break; 1242 case 'd': 1243 type = DELETE; 1244 break; 1245 default: 1246 return ERROR; /* Bad format */ 1247 } 1248 s++; /* Past letter */ 1249 1250 /* Read second set of digits */ 1251 SKIPWHITE (s); 1252 READNUM (s, db->ranges[1][START]); 1253 1254 /* Was that the only digit? */ 1255 SKIPWHITE (s); 1256 if (*s == ',') 1257 { 1258 /* Get the next digit */ 1259 s++; 1260 READNUM (s, db->ranges[1][END]); 1261 SKIPWHITE (s); /* To move to end */ 1262 } 1263 else 1264 db->ranges[1][END] = db->ranges[1][START]; 1265 1266 *string = s; 1267 return type; 1268} 1269 1270static char * 1271read_diff (filea, fileb, output_placement) 1272 char const *filea, *fileb; 1273 char **output_placement; 1274{ 1275 char *diff_result; 1276 size_t bytes, current_chunk_size, total; 1277 int fd, wstatus; 1278 struct stat pipestat; 1279 FILE *outfile_hold; 1280 const struct diff_callbacks *callbacks_hold; 1281 struct diff_callbacks my_callbacks; 1282 struct diff_callbacks *my_callbacks_arg; 1283 1284 /* 302 / 1000 is log10(2.0) rounded up. Subtract 1 for the sign bit; 1285 add 1 for integer division truncation; add 1 more for a minus sign. */ 1286#define INT_STRLEN_BOUND(type) ((sizeof(type)*CHAR_BIT - 1) * 302 / 1000 + 2) 1287 1288 char const *argv[7]; 1289 char horizon_arg[17 + INT_STRLEN_BOUND (int)]; 1290 char const **ap; 1291 char *diffout; 1292 1293 ap = argv; 1294 *ap++ = "diff"; 1295 if (always_text) 1296 *ap++ = "-a"; 1297 sprintf (horizon_arg, "--horizon-lines=%d", horizon_lines); 1298 *ap++ = horizon_arg; 1299 *ap++ = "--"; 1300 *ap++ = filea; 1301 *ap++ = fileb; 1302 *ap = 0; 1303 1304 diffout = cvs_temp_name (); 1305 1306 outfile_hold = outfile; 1307 callbacks_hold = callbacks; 1308 1309 /* We want to call diff_run preserving any stdout and stderr 1310 callbacks, but discarding any callbacks to handle file output, 1311 since we want the file output to go to our temporary file. 1312 FIXME: We should use callbacks to just read it into a memory 1313 buffer; that's we do with the temporary file just below anyhow. */ 1314 if (callbacks == NULL) 1315 my_callbacks_arg = NULL; 1316 else 1317 { 1318 my_callbacks = *callbacks; 1319 my_callbacks.write_output = NULL; 1320 my_callbacks.flush_output = NULL; 1321 my_callbacks_arg = &my_callbacks; 1322 } 1323 1324 wstatus = diff_run (ap - argv, (char **) argv, diffout, my_callbacks_arg); 1325 1326 outfile = outfile_hold; 1327 callbacks = callbacks_hold; 1328 1329 if (wstatus == 2) 1330 diff3_fatal ("subsidiary diff failed"); 1331 1332 if (-1 == (fd = open (diffout, O_RDONLY))) 1333 diff3_fatal ("could not open temporary diff file"); 1334 1335 current_chunk_size = 8 * 1024; 1336 if (fstat (fd, &pipestat) == 0) 1337 current_chunk_size = max (current_chunk_size, STAT_BLOCKSIZE (pipestat)); 1338 1339 diff_result = xmalloc (current_chunk_size); 1340 total = 0; 1341 do { 1342 bytes = myread (fd, 1343 diff_result + total, 1344 current_chunk_size - total); 1345 total += bytes; 1346 if (total == current_chunk_size) 1347 { 1348 if (current_chunk_size < 2 * current_chunk_size) 1349 current_chunk_size = 2 * current_chunk_size; 1350 else if (current_chunk_size < (size_t) -1) 1351 current_chunk_size = (size_t) -1; 1352 else 1353 diff3_fatal ("files are too large to fit into memory"); 1354 diff_result = xrealloc (diff_result, (current_chunk_size *= 2)); 1355 } 1356 } while (bytes); 1357 1358 if (total != 0 && diff_result[total-1] != '\n') 1359 diff3_fatal ("invalid diff format; incomplete last line"); 1360 1361 *output_placement = diff_result; 1362 1363 if (close (fd) != 0) 1364 diff3_perror_with_exit ("pipe close"); 1365 unlink (diffout); 1366 free( diffout ); 1367 1368 return diff_result + total; 1369} 1370 1371 1372/* 1373 * Scan a regular diff line (consisting of > or <, followed by a 1374 * space, followed by text (including nulls) up to a newline. 1375 * 1376 * This next routine began life as a macro and many parameters in it 1377 * are used as call-by-reference values. 1378 */ 1379static char * 1380scan_diff_line (scan_ptr, set_start, set_length, limit, leadingchar) 1381 char *scan_ptr, **set_start; 1382 size_t *set_length; 1383 char *limit; 1384 int leadingchar; 1385{ 1386 char *line_ptr; 1387 1388 if (!(scan_ptr[0] == leadingchar 1389 && scan_ptr[1] == ' ')) 1390 diff3_fatal ("invalid diff format; incorrect leading line chars"); 1391 1392 *set_start = line_ptr = scan_ptr + 2; 1393 while (*line_ptr++ != '\n') 1394 ; 1395 1396 /* Include newline if the original line ended in a newline, 1397 or if an edit script is being generated. 1398 Copy any missing newline message to stderr if an edit script is being 1399 generated, because edit scripts cannot handle missing newlines. 1400 Return the beginning of the next line. */ 1401 *set_length = line_ptr - *set_start; 1402 if (line_ptr < limit && *line_ptr == '\\') 1403 { 1404 if (! edscript) 1405 { 1406 --*set_length; 1407 line_ptr++; 1408 while (*line_ptr++ != '\n') 1409 ; 1410 } 1411 else 1412 { 1413 char *serr; 1414 1415 line_ptr++; 1416 serr = line_ptr; 1417 while (*line_ptr++ != '\n') 1418 ; 1419 line_ptr[-1] = '\0'; 1420 diff_error ("%s", serr, 0); 1421 line_ptr[-1] = '\n'; 1422 } 1423 } 1424 1425 return line_ptr; 1426} 1427 1428/* 1429 * This routine outputs a three way diff passed as a list of 1430 * diff3_block's. 1431 * The argument MAPPING is indexed by external file number (in the 1432 * argument list) and contains the internal file number (from the 1433 * diff passed). This is important because the user expects his 1434 * outputs in terms of the argument list number, and the diff passed 1435 * may have been done slightly differently (if the last argument 1436 * was "-", for example). 1437 * REV_MAPPING is the inverse of MAPPING. 1438 */ 1439static void 1440output_diff3 (diff, mapping, rev_mapping) 1441 struct diff3_block *diff; 1442 int const mapping[3], rev_mapping[3]; 1443{ 1444 int i; 1445 int oddoneout; 1446 char *cp; 1447 struct diff3_block *ptr; 1448 int line; 1449 size_t length; 1450 int dontprint; 1451 static int skew_increment[3] = { 2, 3, 1 }; /* 0==>2==>1==>3 */ 1452 char const *line_prefix = tab_align_flag ? "\t" : " "; 1453 1454 for (ptr = diff; ptr; ptr = D_NEXT (ptr)) 1455 { 1456 char x[2]; 1457 1458 switch (ptr->correspond) 1459 { 1460 case DIFF_ALL: 1461 x[0] = '\0'; 1462 dontprint = 3; /* Print them all */ 1463 oddoneout = 3; /* Nobody's odder than anyone else */ 1464 break; 1465 case DIFF_1ST: 1466 case DIFF_2ND: 1467 case DIFF_3RD: 1468 oddoneout = rev_mapping[(int) ptr->correspond - (int) DIFF_1ST]; 1469 1470 x[0] = oddoneout + '1'; 1471 x[1] = '\0'; 1472 dontprint = oddoneout==0; 1473 break; 1474 default: 1475 diff3_fatal ("internal error: invalid diff type passed to output"); 1476 } 1477 printf_output ("====%s\n", x); 1478 1479 /* Go 0, 2, 1 if the first and third outputs are equivalent. */ 1480 for (i = 0; i < 3; 1481 i = (oddoneout == 1 ? skew_increment[i] : i + 1)) 1482 { 1483 int realfile = mapping[i]; 1484 int 1485 lowt = D_LOWLINE (ptr, realfile), 1486 hight = D_HIGHLINE (ptr, realfile); 1487 1488 printf_output ("%d:", i + 1); 1489 switch (lowt - hight) 1490 { 1491 case 1: 1492 printf_output ("%da\n", lowt - 1); 1493 break; 1494 case 0: 1495 printf_output ("%dc\n", lowt); 1496 break; 1497 default: 1498 printf_output ("%d,%dc\n", lowt, hight); 1499 break; 1500 } 1501 1502 if (i == dontprint) continue; 1503 1504 if (lowt <= hight) 1505 { 1506 line = 0; 1507 do 1508 { 1509 printf_output (line_prefix); 1510 cp = D_RELNUM (ptr, realfile, line); 1511 length = D_RELLEN (ptr, realfile, line); 1512 write_output (cp, length); 1513 } 1514 while (++line < hight - lowt + 1); 1515 if (cp[length - 1] != '\n') 1516 printf_output ("\n\\ No newline at end of file\n"); 1517 } 1518 } 1519 } 1520} 1521 1522 1523/* 1524 * Output the lines of B taken from FILENUM. 1525 * Double any initial '.'s; yield nonzero if any initial '.'s were doubled. 1526 */ 1527static int 1528dotlines (b, filenum) 1529 struct diff3_block *b; 1530 int filenum; 1531{ 1532 int i; 1533 int leading_dot = 0; 1534 1535 for (i = 0; 1536 i < D_NUMLINES (b, filenum); 1537 i++) 1538 { 1539 char *line = D_RELNUM (b, filenum, i); 1540 if (line[0] == '.') 1541 { 1542 leading_dot = 1; 1543 write_output (".", 1); 1544 } 1545 write_output (line, D_RELLEN (b, filenum, i)); 1546 } 1547 1548 return leading_dot; 1549} 1550 1551/* 1552 * Output to OUTPUTFILE a '.' line. If LEADING_DOT is nonzero, 1553 * also output a command that removes initial '.'s 1554 * starting with line START and continuing for NUM lines. 1555 */ 1556static void 1557undotlines (leading_dot, start, num) 1558 int leading_dot, start, num; 1559{ 1560 write_output (".\n", 2); 1561 if (leading_dot) 1562 if (num == 1) 1563 printf_output ("%ds/^\\.//\n", start); 1564 else 1565 printf_output ("%d,%ds/^\\.//\n", start, start + num - 1); 1566} 1567 1568/* 1569 * This routine outputs a diff3 set of blocks as an ed script. This 1570 * script applies the changes between file's 2 & 3 to file 1. It 1571 * takes the precise format of the ed script to be output from global 1572 * variables set during options processing. Note that it does 1573 * destructive things to the set of diff3 blocks it is passed; it 1574 * reverses their order (this gets around the problems involved with 1575 * changing line numbers in an ed script). 1576 * 1577 * Note that this routine has the same problem of mapping as the last 1578 * one did; the variable MAPPING maps from file number according to 1579 * the argument list to file number according to the diff passed. All 1580 * files listed below are in terms of the argument list. 1581 * REV_MAPPING is the inverse of MAPPING. 1582 * 1583 * The arguments FILE0, FILE1 and FILE2 are the strings to print 1584 * as the names of the three files. These may be the actual names, 1585 * or may be the arguments specified with -L. 1586 * 1587 * Returns 1 if conflicts were found. 1588 */ 1589 1590static int 1591output_diff3_edscript (diff, mapping, rev_mapping, file0, file1, file2) 1592 struct diff3_block *diff; 1593 int const mapping[3], rev_mapping[3]; 1594 char const *file0, *file1, *file2; 1595{ 1596 int leading_dot; 1597 int conflicts_found = 0, conflict; 1598 struct diff3_block *b; 1599 1600 for (b = reverse_diff3_blocklist (diff); b; b = b->next) 1601 { 1602 /* Must do mapping correctly. */ 1603 enum diff_type type 1604 = ((b->correspond == DIFF_ALL) ? 1605 DIFF_ALL : 1606 ((enum diff_type) 1607 (((int) DIFF_1ST) 1608 + rev_mapping[(int) b->correspond - (int) DIFF_1ST]))); 1609 1610 /* If we aren't supposed to do this output block, skip it. */ 1611 switch (type) 1612 { 1613 default: continue; 1614 case DIFF_2ND: if (!show_2nd) continue; conflict = 1; break; 1615 case DIFF_3RD: if (overlap_only) continue; conflict = 0; break; 1616 case DIFF_ALL: if (simple_only) continue; conflict = flagging; break; 1617 } 1618 1619 if (conflict) 1620 { 1621 conflicts_found = 1; 1622 1623 1624 /* Mark end of conflict. */ 1625 1626 printf_output ("%da\n", D_HIGHLINE (b, mapping[FILE0])); 1627 leading_dot = 0; 1628 if (type == DIFF_ALL) 1629 { 1630 if (show_2nd) 1631 { 1632 /* Append lines from FILE1. */ 1633 printf_output ("||||||| %s\n", file1); 1634 leading_dot = dotlines (b, mapping[FILE1]); 1635 } 1636 /* Append lines from FILE2. */ 1637 printf_output ("=======\n"); 1638 leading_dot |= dotlines (b, mapping[FILE2]); 1639 } 1640 printf_output (">>>>>>> %s\n", file2); 1641 undotlines (leading_dot, 1642 D_HIGHLINE (b, mapping[FILE0]) + 2, 1643 (D_NUMLINES (b, mapping[FILE1]) 1644 + D_NUMLINES (b, mapping[FILE2]) + 1)); 1645 1646 1647 /* Mark start of conflict. */ 1648 1649 printf_output ("%da\n<<<<<<< %s\n", 1650 D_LOWLINE (b, mapping[FILE0]) - 1, 1651 type == DIFF_ALL ? file0 : file1); 1652 leading_dot = 0; 1653 if (type == DIFF_2ND) 1654 { 1655 /* Prepend lines from FILE1. */ 1656 leading_dot = dotlines (b, mapping[FILE1]); 1657 printf_output ("=======\n"); 1658 } 1659 undotlines (leading_dot, 1660 D_LOWLINE (b, mapping[FILE0]) + 1, 1661 D_NUMLINES (b, mapping[FILE1])); 1662 } 1663 else if (D_NUMLINES (b, mapping[FILE2]) == 0) 1664 /* Write out a delete */ 1665 { 1666 if (D_NUMLINES (b, mapping[FILE0]) == 1) 1667 printf_output ("%dd\n", D_LOWLINE (b, mapping[FILE0])); 1668 else 1669 printf_output ("%d,%dd\n", 1670 D_LOWLINE (b, mapping[FILE0]), 1671 D_HIGHLINE (b, mapping[FILE0])); 1672 } 1673 else 1674 /* Write out an add or change */ 1675 { 1676 switch (D_NUMLINES (b, mapping[FILE0])) 1677 { 1678 case 0: 1679 printf_output ("%da\n", D_HIGHLINE (b, mapping[FILE0])); 1680 break; 1681 case 1: 1682 printf_output ("%dc\n", D_HIGHLINE (b, mapping[FILE0])); 1683 break; 1684 default: 1685 printf_output ("%d,%dc\n", 1686 D_LOWLINE (b, mapping[FILE0]), 1687 D_HIGHLINE (b, mapping[FILE0])); 1688 break; 1689 } 1690 1691 undotlines (dotlines (b, mapping[FILE2]), 1692 D_LOWLINE (b, mapping[FILE0]), 1693 D_NUMLINES (b, mapping[FILE2])); 1694 } 1695 } 1696 if (finalwrite) printf_output ("w\nq\n"); 1697 return conflicts_found; 1698} 1699 1700/* 1701 * Read from INFILE and output to the standard output file a set of 1702 * diff3_ blocks DIFF as a merged file. This acts like 'ed file0 1703 * <[output_diff3_edscript]', except that it works even for binary 1704 * data or incomplete lines. 1705 * 1706 * As before, MAPPING maps from arg list file number to diff file number, 1707 * REV_MAPPING is its inverse, 1708 * and FILE0, FILE1, and FILE2 are the names of the files. 1709 * 1710 * Returns 1 if conflicts were found. 1711 */ 1712 1713static int 1714output_diff3_merge (infile, diff, mapping, rev_mapping, 1715 file0, file1, file2) 1716 FILE *infile; 1717 struct diff3_block *diff; 1718 int const mapping[3], rev_mapping[3]; 1719 char const *file0, *file1, *file2; 1720{ 1721 int c, i; 1722 char cc; 1723 int conflicts_found = 0, conflict; 1724 struct diff3_block *b; 1725 int linesread = 0; 1726 1727 for (b = diff; b; b = b->next) 1728 { 1729 /* Must do mapping correctly. */ 1730 enum diff_type type 1731 = ((b->correspond == DIFF_ALL) ? 1732 DIFF_ALL : 1733 ((enum diff_type) 1734 (((int) DIFF_1ST) 1735 + rev_mapping[(int) b->correspond - (int) DIFF_1ST]))); 1736 char const *format_2nd = "<<<<<<< %s\n"; 1737 1738 /* If we aren't supposed to do this output block, skip it. */ 1739 switch (type) 1740 { 1741 default: continue; 1742 case DIFF_2ND: if (!show_2nd) continue; conflict = 1; break; 1743 case DIFF_3RD: if (overlap_only) continue; conflict = 0; break; 1744 case DIFF_ALL: if (simple_only) continue; conflict = flagging; 1745 format_2nd = "||||||| %s\n"; 1746 break; 1747 } 1748 1749 /* Copy I lines from file 0. */ 1750 i = D_LOWLINE (b, FILE0) - linesread - 1; 1751 linesread += i; 1752 while (0 <= --i) 1753 do 1754 { 1755 c = getc (infile); 1756 if (c == EOF) 1757 if (ferror (infile)) 1758 diff3_perror_with_exit ("input file"); 1759 else if (feof (infile)) 1760 diff3_fatal ("input file shrank"); 1761 cc = c; 1762 write_output (&cc, 1); 1763 } 1764 while (c != '\n'); 1765 1766 if (conflict) 1767 { 1768 conflicts_found = 1; 1769 1770 if (type == DIFF_ALL) 1771 { 1772 /* Put in lines from FILE0 with bracket. */ 1773 printf_output ("<<<<<<< %s\n", file0); 1774 for (i = 0; 1775 i < D_NUMLINES (b, mapping[FILE0]); 1776 i++) 1777 write_output (D_RELNUM (b, mapping[FILE0], i), 1778 D_RELLEN (b, mapping[FILE0], i)); 1779 } 1780 1781 if (show_2nd) 1782 { 1783 /* Put in lines from FILE1 with bracket. */ 1784 printf_output (format_2nd, file1); 1785 for (i = 0; 1786 i < D_NUMLINES (b, mapping[FILE1]); 1787 i++) 1788 write_output (D_RELNUM (b, mapping[FILE1], i), 1789 D_RELLEN (b, mapping[FILE1], i)); 1790 } 1791 1792 printf_output ("=======\n"); 1793 } 1794 1795 /* Put in lines from FILE2. */ 1796 for (i = 0; 1797 i < D_NUMLINES (b, mapping[FILE2]); 1798 i++) 1799 write_output (D_RELNUM (b, mapping[FILE2], i), 1800 D_RELLEN (b, mapping[FILE2], i)); 1801 1802 if (conflict) 1803 printf_output (">>>>>>> %s\n", file2); 1804 1805 /* Skip I lines in file 0. */ 1806 i = D_NUMLINES (b, FILE0); 1807 linesread += i; 1808 while (0 <= --i) 1809 while ((c = getc (infile)) != '\n') 1810 if (c == EOF) 1811 if (ferror (infile)) 1812 diff3_perror_with_exit ("input file"); 1813 else if (feof (infile)) 1814 { 1815 if (i || b->next) 1816 diff3_fatal ("input file shrank"); 1817 return conflicts_found; 1818 } 1819 } 1820 /* Copy rest of common file. */ 1821 while ((c = getc (infile)) != EOF || !(ferror (infile) | feof (infile))) 1822 { 1823 cc = c; 1824 write_output (&cc, 1); 1825 } 1826 return conflicts_found; 1827} 1828 1829/* 1830 * Reverse the order of the list of diff3 blocks. 1831 */ 1832static struct diff3_block * 1833reverse_diff3_blocklist (diff) 1834 struct diff3_block *diff; 1835{ 1836 register struct diff3_block *tmp, *next, *prev; 1837 1838 for (tmp = diff, prev = 0; tmp; tmp = next) 1839 { 1840 next = tmp->next; 1841 tmp->next = prev; 1842 prev = tmp; 1843 } 1844 1845 return prev; 1846} 1847 1848static size_t 1849myread (fd, ptr, size) 1850 int fd; 1851 char *ptr; 1852 size_t size; 1853{ 1854 ssize_t result = read (fd, ptr, size); 1855 if (result == -1) 1856 diff3_perror_with_exit ("read failed"); 1857 return (size_t)result; 1858} 1859 1860static void 1861diff3_fatal (string) 1862 char const *string; 1863{ 1864 diff_error ("%s", string, 0); 1865 DIFF3_ABORT (2); 1866} 1867 1868static void 1869diff3_perror_with_exit (string) 1870 char const *string; 1871{ 1872 perror_with_name (string); 1873 DIFF3_ABORT (2); 1874} 1875 1876static void 1877initialize_main (argcp, argvp) 1878 int *argcp; 1879 char ***argvp; 1880{ 1881 always_text = 0; 1882 edscript = 0; 1883 flagging = 0; 1884 tab_align_flag = 0; 1885 simple_only = 0; 1886 overlap_only = 0; 1887 show_2nd = 0; 1888 finalwrite = 0; 1889 merge = 0; 1890 diff_program_name = (*argvp)[0]; 1891 outfile = NULL; 1892} 1893 1894static void 1895free_diff_blocks(p) 1896 struct diff_block *p; 1897{ 1898 register struct diff_block *next; 1899 1900 while (p) 1901 { 1902 next = p->next; 1903 if (p->lines[0]) free(p->lines[0]); 1904 if (p->lines[1]) free(p->lines[1]); 1905 if (p->lengths[0]) free(p->lengths[0]); 1906 if (p->lengths[1]) free(p->lengths[1]); 1907 free(p); 1908 p = next; 1909 } 1910} 1911 1912static void 1913free_diff3_blocks(p) 1914 struct diff3_block *p; 1915{ 1916 register struct diff3_block *next; 1917 1918 while (p) 1919 { 1920 next = p->next; 1921 if (p->lines[0]) free(p->lines[0]); 1922 if (p->lines[1]) free(p->lines[1]); 1923 if (p->lines[2]) free(p->lines[2]); 1924 if (p->lengths[0]) free(p->lengths[0]); 1925 if (p->lengths[1]) free(p->lengths[1]); 1926 if (p->lengths[2]) free(p->lengths[2]); 1927 free(p); 1928 p = next; 1929 } 1930} 1931