diff3.c revision 170754
113044Sasami/* diff3 - compare three files line by line 213044Sasami 313044Sasami Copyright (C) 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1998, 2001, 413044Sasami 2002, 2004 Free Software Foundation, Inc. 513044Sasami 613044Sasami This program is free software; you can redistribute it and/or modify 713044Sasami it under the terms of the GNU General Public License as published by 813044Sasami the Free Software Foundation; either version 2, or (at your option) 913044Sasami any later version. 1013044Sasami 1113044Sasami This program is distributed in the hope that it will be useful, 1213044Sasami but WITHOUT ANY WARRANTY; without even the implied warranty of 1313044Sasami MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 1413044Sasami See the GNU General Public License for more details. 1513044Sasami 1613044Sasami You should have received a copy of the GNU General Public License 1713044Sasami along with this program; see the file COPYING. 1813044Sasami If not, write to the Free Software Foundation, 1913044Sasami 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ 2013044Sasami 2113044Sasami#include "system.h" 2213044Sasami#include "paths.h" 2313044Sasami 2413044Sasami#include <stdio.h> 2513044Sasami#include <unlocked-io.h> 2613044Sasami 2713044Sasami#include <c-stack.h> 2813044Sasami#include <cmpbuf.h> 2913044Sasami#include <error.h> 3013044Sasami#include <exitfail.h> 3113044Sasami#include <file-type.h> 3213044Sasami#include <getopt.h> 3313044Sasami#include <inttostr.h> 3413044Sasami#include <quotesys.h> 3536628Scharnier#include <version-etc.h> 3636628Scharnier#include <xalloc.h> 3750476Speter 3836628Scharnier/* Internal data structures and macros for the diff3 program; includes 3936628Scharnier data structures for both diff3 diffs and normal diffs. */ 4013044Sasami 4148568Sbillf/* Different files within a three way diff. */ 4213044Sasami#define FILE0 0 4313044Sasami#define FILE1 1 4413044Sasami#define FILE2 2 4545329Speter 4613044Sasami/* A three way diff is built from two two-way diffs; the file which 4713044Sasami the two two-way diffs share is: */ 4813044Sasami#define FILEC FILE2 4913044Sasami 5013044Sasami/* Different files within a two way diff. 5113044Sasami FC is the common file, FO the other file. */ 5213044Sasami#define FO 0 5313044Sasami#define FC 1 5413044Sasami 5513044Sasami/* The ranges are indexed by */ 5613044Sasami#define RANGE_START 0 5739228Sgibbs#define RANGE_END 1 5813052Sasami 5913044Sasamienum diff_type { 6013044Sasami ERROR, /* Should not be used */ 6113044Sasami ADD, /* Two way diff add */ 6213044Sasami CHANGE, /* Two way diff change */ 6313044Sasami DELETE, /* Two way diff delete */ 6413044Sasami DIFF_ALL, /* All three are different */ 6513044Sasami DIFF_1ST, /* Only the first is different */ 6613044Sasami DIFF_2ND, /* Only the second */ 6713044Sasami DIFF_3RD /* Only the third */ 6813044Sasami}; 6913044Sasami 7013044Sasami/* Two way diff */ 7113044Sasamistruct diff_block { 7213044Sasami lin ranges[2][2]; /* Ranges are inclusive */ 7313044Sasami char **lines[2]; /* The actual lines (may contain nulls) */ 7413044Sasami size_t *lengths[2]; /* Line lengths (including newlines, if any) */ 7513762Sasami struct diff_block *next; 7613762Sasami}; 7713044Sasami 7813044Sasami/* Three way diff */ 7913044Sasami 8013044Sasamistruct diff3_block { 8113044Sasami enum diff_type correspond; /* Type of diff */ 8213044Sasami lin ranges[3][2]; /* Ranges are inclusive */ 8313044Sasami char **lines[3]; /* The actual lines (may contain nulls) */ 8413044Sasami size_t *lengths[3]; /* Line lengths (including newlines, if any) */ 8513044Sasami struct diff3_block *next; 8613044Sasami}; 8713044Sasami 8813044Sasami/* Access the ranges on a diff block. */ 8913044Sasami#define D_LOWLINE(diff, filenum) \ 9013044Sasami ((diff)->ranges[filenum][RANGE_START]) 9113044Sasami#define D_HIGHLINE(diff, filenum) \ 9213044Sasami ((diff)->ranges[filenum][RANGE_END]) 9313044Sasami#define D_NUMLINES(diff, filenum) \ 9413044Sasami (D_HIGHLINE (diff, filenum) - D_LOWLINE (diff, filenum) + 1) 9513044Sasami 9613044Sasami/* Access the line numbers in a file in a diff by relative line 9713044Sasami numbers (i.e. line number within the diff itself). Note that these 9813044Sasami are lvalues and can be used for assignment. */ 9913044Sasami#define D_RELNUM(diff, filenum, linenum) \ 10013044Sasami ((diff)->lines[filenum][linenum]) 10113044Sasami#define D_RELLEN(diff, filenum, linenum) \ 10213044Sasami ((diff)->lengths[filenum][linenum]) 10313044Sasami 10413044Sasami/* And get at them directly, when that should be necessary. */ 10513044Sasami#define D_LINEARRAY(diff, filenum) \ 10613044Sasami ((diff)->lines[filenum]) 10713044Sasami#define D_LENARRAY(diff, filenum) \ 10813044Sasami ((diff)->lengths[filenum]) 10913044Sasami 11013044Sasami/* Next block. */ 11113044Sasami#define D_NEXT(diff) ((diff)->next) 11213044Sasami 11313044Sasami/* Access the type of a diff3 block. */ 11413044Sasami#define D3_TYPE(diff) ((diff)->correspond) 11513044Sasami 11613044Sasami/* Line mappings based on diffs. The first maps off the top of the 11713044Sasami diff, the second off of the bottom. */ 11813044Sasami#define D_HIGH_MAPLINE(diff, fromfile, tofile, linenum) \ 11913044Sasami ((linenum) \ 12013044Sasami - D_HIGHLINE ((diff), (fromfile)) \ 12113044Sasami + D_HIGHLINE ((diff), (tofile))) 12213044Sasami 12313044Sasami#define D_LOW_MAPLINE(diff, fromfile, tofile, linenum) \ 12413044Sasami ((linenum) \ 12513044Sasami - D_LOWLINE ((diff), (fromfile)) \ 12613044Sasami + D_LOWLINE ((diff), (tofile))) 12713044Sasami 12813044Sasami/* Options variables for flags set on command line. */ 12913044Sasami 13013044Sasami/* If nonzero, treat all files as text files, never as binary. */ 13113044Sasamistatic bool text; 13213044Sasami 13313044Sasami/* Remove trailing carriage returns from input. */ 13413044Sasamistatic bool strip_trailing_cr; 13513044Sasami 13613044Sasami/* If nonzero, write out an ed script instead of the standard diff3 format. */ 13713044Sasamistatic bool edscript; 13813044Sasami 13913044Sasami/* If nonzero, in the case of overlapping diffs (type DIFF_ALL), 14013044Sasami preserve the lines which would normally be deleted from 14113044Sasami file 1 with a special flagging mechanism. */ 14213044Sasamistatic bool flagging; 14313044Sasami 14413044Sasami/* Use a tab to align output lines (-T). */ 14513044Sasamistatic bool initial_tab; 14613044Sasami 14713044Sasami/* If nonzero, do not output information for overlapping diffs. */ 14813044Sasamistatic bool simple_only; 14913044Sasami 15013044Sasami/* If nonzero, do not output information for non-overlapping diffs. */ 15113044Sasamistatic bool overlap_only; 15213044Sasami 15313044Sasami/* If nonzero, show information for DIFF_2ND diffs. */ 15413044Sasamistatic bool show_2nd; 15513044Sasami 15613044Sasami/* If nonzero, include `:wq' at the end of the script 15713044Sasami to write out the file being edited. */ 15813044Sasamistatic bool finalwrite; 15913044Sasami 16013044Sasami/* If nonzero, output a merged file. */ 16113044Sasamistatic bool merge; 16213044Sasami 16313044Sasamichar *program_name; 16413044Sasami 16532116Simpstatic char *read_diff (char const *, char const *, char **); 16632116Simpstatic char *scan_diff_line (char *, char **, size_t *, char *, char); 16732116Simpstatic enum diff_type process_diff_control (char **, struct diff_block *); 16832116Simpstatic bool compare_line_list (char * const[], size_t const[], char * const[], size_t const[], lin); 16932116Simpstatic bool copy_stringlist (char * const[], size_t const[], char *[], size_t[], lin); 17032116Simpstatic bool output_diff3_edscript (FILE *, struct diff3_block *, int const[3], int const[3], char const *, char const *, char const *); 17132116Simpstatic bool output_diff3_merge (FILE *, FILE *, struct diff3_block *, int const[3], int const[3], char const *, char const *, char const *); 17232116Simpstatic struct diff3_block *create_diff3_block (lin, lin, lin, lin, lin, lin); 17332116Simpstatic struct diff3_block *make_3way_diff (struct diff_block *, struct diff_block *); 17445329Speterstatic struct diff3_block *reverse_diff3_blocklist (struct diff3_block *); 17545329Speterstatic struct diff3_block *using_to_diff3_block (struct diff_block *[2], struct diff_block *[2], int, int, struct diff3_block const *); 17645329Speterstatic struct diff_block *process_diff (char const *, char const *, struct diff_block **); 17745329Speterstatic void check_stdout (void); 17845329Speterstatic void fatal (char const *) __attribute__((noreturn)); 17945329Speterstatic void output_diff3 (FILE *, struct diff3_block *, int const[3], int const[3]); 18013044Sasamistatic void perror_with_exit (char const *) __attribute__((noreturn)); 18113044Sasamistatic void try_help (char const *, char const *) __attribute__((noreturn)); 18213044Sasamistatic void usage (void); 18313044Sasami 18413044Sasamistatic char const *diff_program = DEFAULT_DIFF_PROGRAM; 18513044Sasami 18613044Sasami/* Values for long options that do not have single-letter equivalents. */ 18713044Sasamienum 18813044Sasami{ 18913044Sasami DIFF_PROGRAM_OPTION = CHAR_MAX + 1, 19013044Sasami HELP_OPTION, 19113044Sasami STRIP_TRAILING_CR_OPTION 19213044Sasami}; 19313044Sasami 19413044Sasamistatic struct option const longopts[] = 19513044Sasami{ 19636628Scharnier {"diff-program", 1, 0, DIFF_PROGRAM_OPTION}, 19713044Sasami {"easy-only", 0, 0, '3'}, 19813044Sasami {"ed", 0, 0, 'e'}, 19913044Sasami {"help", 0, 0, HELP_OPTION}, 20013044Sasami {"initial-tab", 0, 0, 'T'}, 20113044Sasami {"label", 1, 0, 'L'}, 20213044Sasami {"merge", 0, 0, 'm'}, 20313044Sasami {"overlap-only", 0, 0, 'x'}, 20413044Sasami {"show-all", 0, 0, 'A'}, 20513044Sasami {"show-overlap", 0, 0, 'E'}, 20613044Sasami {"strip-trailing-cr", 0, 0, STRIP_TRAILING_CR_OPTION}, 20751690Sbillf {"text", 0, 0, 'a'}, 20813044Sasami {"version", 0, 0, 'v'}, 20913044Sasami {0, 0, 0, 0} 21013044Sasami}; 21113044Sasami 21213044Sasamiint 21313044Sasamimain (int argc, char **argv) 21413044Sasami{ 21513044Sasami int c, i; 21613044Sasami int common; 21713044Sasami int mapping[3]; 21813044Sasami int rev_mapping[3]; 21913044Sasami int incompat = 0; 22013044Sasami bool conflicts_found; 22113044Sasami struct diff_block *thread0, *thread1, *last_block; 22213044Sasami struct diff3_block *diff3; 22313044Sasami int tag_count = 0; 22413044Sasami char *tag_strings[3]; 22513044Sasami char *commonname; 22613044Sasami char **file; 22713044Sasami struct stat statb; 22813044Sasami 22913044Sasami exit_failure = 2; 23013044Sasami initialize_main (&argc, &argv); 23113044Sasami program_name = argv[0]; 23248568Sbillf setlocale (LC_ALL, ""); 23313044Sasami bindtextdomain (PACKAGE, LOCALEDIR); 23413044Sasami textdomain (PACKAGE); 23513044Sasami c_stack_action (0); 23613044Sasami 23713044Sasami while ((c = getopt_long (argc, argv, "aeimvx3AEL:TX", longopts, 0)) != -1) 23813044Sasami { 23913044Sasami switch (c) 24013044Sasami { 24113044Sasami case 'a': 24213044Sasami text = true; 24348568Sbillf break; 24413044Sasami case 'A': 24513044Sasami show_2nd = true; 24613044Sasami flagging = true; 24713044Sasami incompat++; 24813044Sasami break; 24913044Sasami case 'x': 25013044Sasami overlap_only = true; 25113044Sasami incompat++; 25213044Sasami break; 25313044Sasami case '3': 25413044Sasami simple_only = true; 25513044Sasami incompat++; 25613044Sasami break; 25713044Sasami case 'i': 25813044Sasami finalwrite = true; 25913044Sasami break; 26013044Sasami case 'm': 26113044Sasami merge = true; 26213044Sasami break; 26313044Sasami case 'X': 26413044Sasami overlap_only = true; 26513044Sasami /* Fall through. */ 26613044Sasami case 'E': 26713044Sasami flagging = true; 26813044Sasami /* Fall through. */ 26913044Sasami case 'e': 27013044Sasami incompat++; 27113044Sasami break; 27213044Sasami case 'T': 27313044Sasami initial_tab = true; 27413044Sasami break; 27513044Sasami case STRIP_TRAILING_CR_OPTION: 27613044Sasami strip_trailing_cr = true; 27713044Sasami break; 27813044Sasami case 'v': 27913044Sasami version_etc (stdout, "diff3", PACKAGE_NAME, PACKAGE_VERSION, 28013044Sasami "Randy Smith", (char *) 0); 28113044Sasami check_stdout (); 28213044Sasami return EXIT_SUCCESS; 28313044Sasami case DIFF_PROGRAM_OPTION: 28413044Sasami diff_program = optarg; 28513044Sasami break; 28613044Sasami case HELP_OPTION: 28713044Sasami usage (); 28813044Sasami check_stdout (); 28913044Sasami return EXIT_SUCCESS; 29013044Sasami case 'L': 29113044Sasami /* Handle up to three -L options. */ 29213044Sasami if (tag_count < 3) 29313044Sasami { 29413044Sasami tag_strings[tag_count++] = optarg; 29513044Sasami break; 29613044Sasami } 29713044Sasami try_help ("too many file label options", 0); 29813044Sasami default: 29913044Sasami try_help (0, 0); 30013044Sasami } 30113044Sasami } 30213044Sasami 30313044Sasami edscript = incompat & ~merge; /* -AeExX3 without -m implies ed script. */ 30413044Sasami show_2nd |= ~incompat & merge; /* -m without -AeExX3 implies -A. */ 30513044Sasami flagging |= ~incompat & merge; 30613044Sasami 30713044Sasami if (incompat > 1 /* Ensure at most one of -AeExX3. */ 30813044Sasami || finalwrite & merge /* -i -m would rewrite input file. */ 30948568Sbillf || (tag_count && ! flagging)) /* -L requires one of -AEX. */ 31013044Sasami try_help ("incompatible options", 0); 31113044Sasami 31213044Sasami if (argc - optind != 3) 31313044Sasami { 31413044Sasami if (argc - optind < 3) 31513044Sasami try_help ("missing operand after `%s'", argv[argc - 1]); 31613044Sasami else 31713044Sasami try_help ("extra operand `%s'", argv[optind + 3]); 31813044Sasami } 31913044Sasami 32013044Sasami file = &argv[optind]; 32113044Sasami 32213044Sasami for (i = tag_count; i < 3; i++) 32313044Sasami tag_strings[i] = file[i]; 32413044Sasami 32513044Sasami /* Always compare file1 to file2, even if file2 is "-". 32613044Sasami This is needed for -mAeExX3. Using the file0 as 32713044Sasami the common file would produce wrong results, because if the 32832116Simp file0-file1 diffs didn't line up with the file0-file2 diffs 32913044Sasami (which is entirely possible since we don't use diff's -n option), 33051690Sbillf diff3 might report phantom changes from file1 to file2. 33132116Simp 33232116Simp Also, try to compare file0 to file1, because this is where 33313044Sasami changes are expected to come from. Diffing between these pairs 33432116Simp of files is more likely to avoid phantom changes from file0 to file1. 33513044Sasami 33613044Sasami Historically, the default common file was file2, so some older 33713044Sasami applications (e.g. Emacs ediff) used file2 as the ancestor. So, 33832116Simp for compatibility, if this is a 3-way diff (not a merge or 33913044Sasami edscript), prefer file2 as the common file. */ 34013044Sasami 34113044Sasami common = 2 - (edscript | merge); 34213044Sasami 34313044Sasami if (strcmp (file[common], "-") == 0) 34413044Sasami { 34513044Sasami /* Sigh. We've got standard input as the common file. We can't 34613044Sasami call diff twice on stdin. Use the other arg as the common 34713044Sasami file instead. */ 34813044Sasami common = 3 - common; 34913044Sasami if (strcmp (file[0], "-") == 0 || strcmp (file[common], "-") == 0) 35013044Sasami fatal ("`-' specified for more than one input file"); 35113044Sasami } 35213044Sasami 35313044Sasami mapping[0] = 0; 35413044Sasami mapping[1] = 3 - common; 35513044Sasami mapping[2] = common; 35613044Sasami 35713044Sasami for (i = 0; i < 3; i++) 35813044Sasami rev_mapping[mapping[i]] = i; 35913044Sasami 36013044Sasami for (i = 0; i < 3; i++) 36113044Sasami if (strcmp (file[i], "-") != 0) 36213044Sasami { 36313044Sasami if (stat (file[i], &statb) < 0) 36413044Sasami perror_with_exit (file[i]); 36513044Sasami else if (S_ISDIR (statb.st_mode)) 36613044Sasami error (EXIT_TROUBLE, EISDIR, "%s", file[i]); 36713044Sasami } 36813044Sasami 36913044Sasami#ifdef SIGCHLD 37013044Sasami /* System V fork+wait does not work if SIGCHLD is ignored. */ 37113044Sasami signal (SIGCHLD, SIG_DFL); 37213044Sasami#endif 37313044Sasami 37413044Sasami /* Invoke diff twice on two pairs of input files, combine the two 37513044Sasami diffs, and output them. */ 37613044Sasami 37713044Sasami commonname = file[rev_mapping[FILEC]]; 37813044Sasami thread1 = process_diff (file[rev_mapping[FILE1]], commonname, &last_block); 37913044Sasami thread0 = process_diff (file[rev_mapping[FILE0]], commonname, &last_block); 38013044Sasami diff3 = make_3way_diff (thread0, thread1); 38113044Sasami if (edscript) 38213044Sasami conflicts_found 38313044Sasami = output_diff3_edscript (stdout, diff3, mapping, rev_mapping, 38413044Sasami tag_strings[0], tag_strings[1], tag_strings[2]); 38513044Sasami else if (merge) 38613044Sasami { 38713044Sasami if (! freopen (file[rev_mapping[FILE0]], "r", stdin)) 38813044Sasami perror_with_exit (file[rev_mapping[FILE0]]); 38913044Sasami conflicts_found 39013044Sasami = output_diff3_merge (stdin, stdout, diff3, mapping, rev_mapping, 39113044Sasami tag_strings[0], tag_strings[1], tag_strings[2]); 39213044Sasami if (ferror (stdin)) 39313044Sasami fatal ("read failed"); 39413044Sasami } 39513044Sasami else 39613044Sasami { 39713044Sasami output_diff3 (stdout, diff3, mapping, rev_mapping); 39813044Sasami conflicts_found = false; 39913044Sasami } 40013044Sasami 40113044Sasami check_stdout (); 40213044Sasami exit (conflicts_found); 40313044Sasami return conflicts_found; 40413044Sasami} 40513044Sasami 40613044Sasamistatic void 40713044Sasamitry_help (char const *reason_msgid, char const *operand) 40813044Sasami{ 40913044Sasami if (reason_msgid) 41013044Sasami error (0, 0, _(reason_msgid), operand); 41113044Sasami error (EXIT_TROUBLE, 0, 41213044Sasami _("Try `%s --help' for more information."), program_name); 41313044Sasami abort (); 41413044Sasami} 41513044Sasami 41613044Sasamistatic void 41713044Sasamicheck_stdout (void) 41813044Sasami{ 41913044Sasami if (ferror (stdout)) 42013044Sasami fatal ("write failed"); 42113044Sasami else if (fclose (stdout) != 0) 42213044Sasami perror_with_exit (_("standard output")); 42313044Sasami} 42413044Sasami 42513044Sasamistatic char const * const option_help_msgid[] = { 42636628Scharnier N_("-e --ed Output unmerged changes from OLDFILE to YOURFILE into MYFILE."), 42713044Sasami N_("-E --show-overlap Output unmerged changes, bracketing conflicts."), 42813044Sasami N_("-A --show-all Output all changes, bracketing conflicts."), 42913044Sasami N_("-x --overlap-only Output overlapping changes."), 43013044Sasami N_("-X Output overlapping changes, bracketing them."), 43113044Sasami N_("-3 --easy-only Output unmerged nonoverlapping changes."), 43213044Sasami "", 43313044Sasami N_("-m --merge Output merged file instead of ed script (default -A)."), 43413044Sasami N_("-L LABEL --label=LABEL Use LABEL instead of file name."), 43513044Sasami N_("-i Append `w' and `q' commands to ed scripts."), 43613044Sasami N_("-a --text Treat all files as text."), 43713044Sasami N_("--strip-trailing-cr Strip trailing carriage return on input."), 43813044Sasami N_("-T --initial-tab Make tabs line up by prepending a tab."), 43913044Sasami N_("--diff-program=PROGRAM Use PROGRAM to compare files."), 44013044Sasami "", 44113044Sasami N_("-v --version Output version info."), 44213044Sasami N_("--help Output this help."), 44313044Sasami 0 44413044Sasami}; 44513044Sasami 44613044Sasamistatic void 44713044Sasamiusage (void) 44813044Sasami{ 44913044Sasami char const * const *p; 45013044Sasami 45113044Sasami printf (_("Usage: %s [OPTION]... MYFILE OLDFILE YOURFILE\n"), 45213044Sasami program_name); 45313044Sasami printf ("%s\n\n", _("Compare three files line by line.")); 45413044Sasami for (p = option_help_msgid; *p; p++) 45513044Sasami if (**p) 45613044Sasami printf (" %s\n", _(*p)); 45713044Sasami else 45813044Sasami putchar ('\n'); 45913044Sasami printf ("\n%s\n%s\n\n%s\n", 46013044Sasami _("If a FILE is `-', read standard input."), 46113044Sasami _("Exit status is 0 if successful, 1 if conflicts, 2 if trouble."), 46213044Sasami _("Report bugs to <bug-gnu-utils@gnu.org>.")); 46313044Sasami} 46413044Sasami 46513044Sasami/* Combine the two diffs together into one. 46613044Sasami Here is the algorithm: 46713044Sasami 46813044Sasami File2 is shared in common between the two diffs. 46913044Sasami Diff02 is the diff between 0 and 2. 47013044Sasami Diff12 is the diff between 1 and 2. 47113044Sasami 47213044Sasami 1) Find the range for the first block in File2. 47313044Sasami a) Take the lowest of the two ranges (in File2) in the two 47413044Sasami current blocks (one from each diff) as being the low 47513044Sasami water mark. Assign the upper end of this block as 47613044Sasami being the high water mark and move the current block up 47713044Sasami one. Mark the block just moved over as to be used. 47813044Sasami b) Check the next block in the diff that the high water 47913044Sasami mark is *not* from. 48013044Sasami 48113044Sasami *If* the high water mark is above 48213044Sasami the low end of the range in that block, 48313044Sasami 48413044Sasami mark that block as to be used and move the current 48513044Sasami block up. Set the high water mark to the max of 48613044Sasami the high end of this block and the current. Repeat b. 48713044Sasami 48813044Sasami 2) Find the corresponding ranges in File0 (from the blocks 48913044Sasami in diff02; line per line outside of diffs) and in File1. 49013044Sasami Create a diff3_block, reserving space as indicated by the ranges. 49113044Sasami 49213044Sasami 3) Copy all of the pointers for file2 in. At least for now, 49313044Sasami do memcmp's between corresponding strings in the two diffs. 49413044Sasami 49513044Sasami 4) Copy all of the pointers for file0 and 1 in. Get what is 49613044Sasami needed from file2 (when there isn't a diff block, it's 49713044Sasami identical to file2 within the range between diff blocks). 49813044Sasami 49913044Sasami 5) If the diff blocks used came from only one of the two 50013044Sasami strings of diffs, then that file (i.e. the one other than 50113044Sasami the common file in that diff) is the odd person out. If 50213044Sasami diff blocks are used from both sets, check to see if files 50313044Sasami 0 and 1 match: 50413044Sasami 50513044Sasami Same number of lines? If so, do a set of memcmp's (if 50613044Sasami a memcmp matches; copy the pointer over; it'll be easier 50713044Sasami later during comparisons). If they match, 0 & 1 are the 50813044Sasami same. If not, all three different. 50913044Sasami 51013044Sasami Then do it again, until the blocks are exhausted. */ 51113044Sasami 51213044Sasami 51313044Sasami/* Make a three way diff (chain of diff3_block's) from two two way 51413044Sasami diffs (chains of diff_block's). Assume that each of the two diffs 51513044Sasami passed are onto the same file (i.e. that each of the diffs were 51613044Sasami made "to" the same file). Return a three way diff pointer with 51713044Sasami numbering FILE0 = the other file in diff02, FILE1 = the other file 51813044Sasami in diff12, and FILEC = the common file. */ 51913044Sasami 52013044Sasamistatic struct diff3_block * 52113044Sasamimake_3way_diff (struct diff_block *thread0, struct diff_block *thread1) 52213044Sasami{ 52313044Sasami /* Work on the two diffs passed to it as threads. Thread number 0 52413044Sasami is diff02, thread number 1 is diff12. USING is the base of the 52513044Sasami list of blocks to be used to construct each block of the three 52613044Sasami way diff; if no blocks from a particular thread are to be used, 52713044Sasami that element of USING is 0. LAST_USING contains the last 52813044Sasami elements on each of the using lists. 52913044Sasami 53013044Sasami HIGH_WATER_MARK is the highest line number in the common file 53113044Sasami described in any of the diffs in either of the USING lists. 53213044Sasami HIGH_WATER_THREAD names the thread. Similarly BASE_WATER_MARK 53313044Sasami and BASE_WATER_THREAD describe the lowest line number in the 53413044Sasami common file described in any of the diffs in either of the USING 53513044Sasami lists. HIGH_WATER_DIFF is the diff from which the 53613044Sasami HIGH_WATER_MARK was taken. 53713044Sasami 53813044Sasami HIGH_WATER_DIFF should always be equal to 53913044Sasami LAST_USING[HIGH_WATER_THREAD]. OTHER_DIFF is the next diff to 54013044Sasami check for higher water, and should always be equal to 54113044Sasami CURRENT[HIGH_WATER_THREAD ^ 1]. OTHER_THREAD is the thread in 54213044Sasami which the OTHER_DIFF is, and hence should always be equal to 54313044Sasami HIGH_WATER_THREAD ^ 1. 54413044Sasami 54513044Sasami LAST_DIFF is the last diff block produced by this routine, for 54613044Sasami line correspondence purposes between that diff and the one 54713044Sasami currently being worked on. It is ZERO_DIFF before any blocks 54813044Sasami have been created. */ 54913044Sasami 55013044Sasami struct diff_block *using[2]; 55113044Sasami struct diff_block *last_using[2]; 55213044Sasami struct diff_block *current[2]; 55313044Sasami 55413044Sasami lin high_water_mark; 55513044Sasami 55613044Sasami int high_water_thread; 55713044Sasami int base_water_thread; 55813044Sasami int other_thread; 55913044Sasami 56013044Sasami struct diff_block *high_water_diff; 56113044Sasami struct diff_block *other_diff; 56213044Sasami 56313044Sasami struct diff3_block *result; 56413044Sasami struct diff3_block *tmpblock; 56513044Sasami struct diff3_block **result_end; 56613044Sasami 56713044Sasami struct diff3_block const *last_diff3; 56813044Sasami 56913044Sasami static struct diff3_block const zero_diff3; 57013044Sasami 57113044Sasami /* Initialization */ 57213044Sasami result = 0; 57313044Sasami result_end = &result; 57413044Sasami current[0] = thread0; current[1] = thread1; 57513044Sasami last_diff3 = &zero_diff3; 57613044Sasami 57713044Sasami /* Sniff up the threads until we reach the end */ 57813044Sasami 57913044Sasami while (current[0] || current[1]) 58013044Sasami { 58113044Sasami using[0] = using[1] = last_using[0] = last_using[1] = 0; 58213044Sasami 58313044Sasami /* Setup low and high water threads, diffs, and marks. */ 58413044Sasami if (!current[0]) 58513044Sasami base_water_thread = 1; 58613044Sasami else if (!current[1]) 58713044Sasami base_water_thread = 0; 58813044Sasami else 58913044Sasami base_water_thread = 59013044Sasami (D_LOWLINE (current[0], FC) > D_LOWLINE (current[1], FC)); 59113044Sasami 59213044Sasami high_water_thread = base_water_thread; 59313044Sasami 59413044Sasami high_water_diff = current[high_water_thread]; 59513044Sasami 59613044Sasami high_water_mark = D_HIGHLINE (high_water_diff, FC); 59713044Sasami 59813044Sasami /* Make the diff you just got info from into the using class */ 59913044Sasami using[high_water_thread] 60013044Sasami = last_using[high_water_thread] 60113044Sasami = high_water_diff; 60213044Sasami current[high_water_thread] = high_water_diff->next; 60313044Sasami last_using[high_water_thread]->next = 0; 60413044Sasami 60513044Sasami /* And mark the other diff */ 60613044Sasami other_thread = high_water_thread ^ 0x1; 60713044Sasami other_diff = current[other_thread]; 60813044Sasami 60913044Sasami /* Shuffle up the ladder, checking the other diff to see if it 61013044Sasami needs to be incorporated. */ 61113044Sasami while (other_diff 61213044Sasami && D_LOWLINE (other_diff, FC) <= high_water_mark + 1) 61313044Sasami { 61413044Sasami 61513044Sasami /* Incorporate this diff into the using list. Note that 61613044Sasami this doesn't take it off the current list */ 61713044Sasami if (using[other_thread]) 61813044Sasami last_using[other_thread]->next = other_diff; 61913044Sasami else 62013044Sasami using[other_thread] = other_diff; 62113044Sasami last_using[other_thread] = other_diff; 62213044Sasami 62313044Sasami /* Take it off the current list. Note that this following 62413044Sasami code assumes that other_diff enters it equal to 62513044Sasami current[high_water_thread ^ 0x1] */ 62613044Sasami current[other_thread] = current[other_thread]->next; 62713044Sasami other_diff->next = 0; 62813044Sasami 62913044Sasami /* Set the high_water stuff 63013044Sasami If this comparison is equal, then this is the last pass 63113044Sasami through this loop; since diff blocks within a given 63213044Sasami thread cannot overlap, the high_water_mark will be 63313044Sasami *below* the range_start of either of the next diffs. */ 63413044Sasami 63513044Sasami if (high_water_mark < D_HIGHLINE (other_diff, FC)) 63613044Sasami { 63713044Sasami high_water_thread ^= 1; 63813044Sasami high_water_diff = other_diff; 63913044Sasami high_water_mark = D_HIGHLINE (other_diff, FC); 64013044Sasami } 64113044Sasami 64213044Sasami /* Set the other diff */ 64313044Sasami other_thread = high_water_thread ^ 0x1; 64413044Sasami other_diff = current[other_thread]; 64513044Sasami } 64613044Sasami 64713044Sasami /* The using lists contain a list of all of the blocks to be 64813044Sasami included in this diff3_block. Create it. */ 64913044Sasami 65013052Sasami tmpblock = using_to_diff3_block (using, last_using, 65113044Sasami base_water_thread, high_water_thread, 65213044Sasami last_diff3); 65313044Sasami 65413044Sasami if (!tmpblock) 65513044Sasami fatal ("internal error: screwup in format of diff blocks"); 65613052Sasami 65713044Sasami /* Put it on the list. */ 65813044Sasami *result_end = tmpblock; 65913044Sasami result_end = &tmpblock->next; 66013044Sasami 66113044Sasami /* Set up corresponding lines correctly. */ 66213044Sasami last_diff3 = tmpblock; 66313044Sasami } 66413044Sasami return result; 66513044Sasami} 66613044Sasami 66713044Sasami/* Take two lists of blocks (from two separate diff threads) and put 66813044Sasami them together into one diff3 block. Return a pointer to this diff3 66913044Sasami block or 0 for failure. 67013044Sasami 67113044Sasami All arguments besides using are for the convenience of the routine; 67213044Sasami they could be derived from the using array. LAST_USING is a pair 67313044Sasami of pointers to the last blocks in the using structure. LOW_THREAD 67413044Sasami and HIGH_THREAD tell which threads contain the lowest and highest 67513044Sasami line numbers for File0. LAST_DIFF3 contains the last diff produced 67613044Sasami in the calling routine. This is used for lines mappings that 67713044Sasami would still be identical to the state that diff ended in. 67813044Sasami 67913044Sasami A distinction should be made in this routine between the two diffs 68013044Sasami that are part of a normal two diff block, and the three diffs that 68113044Sasami are part of a diff3_block. */ 68213044Sasami 68313044Sasamistatic struct diff3_block * 68413044Sasamiusing_to_diff3_block (struct diff_block *using[2], 68513044Sasami struct diff_block *last_using[2], 68613044Sasami int low_thread, int high_thread, 68713044Sasami struct diff3_block const *last_diff3) 68813044Sasami{ 68913044Sasami lin low[2], high[2]; 69013044Sasami struct diff3_block *result; 69113044Sasami struct diff_block *ptr; 69213044Sasami int d; 69313044Sasami lin i; 69413044Sasami 69513044Sasami /* Find the range in the common file. */ 69613044Sasami lin lowc = D_LOWLINE (using[low_thread], FC); 69713044Sasami lin highc = D_HIGHLINE (last_using[high_thread], FC); 69813044Sasami 69913044Sasami /* Find the ranges in the other files. 70013044Sasami If using[d] is null, that means that the file to which that diff 70113044Sasami refers is equivalent to the common file over this range. */ 70213044Sasami 70313044Sasami for (d = 0; d < 2; d++) 70413044Sasami if (using[d]) 70513044Sasami { 70613044Sasami low[d] = D_LOW_MAPLINE (using[d], FC, FO, lowc); 70713044Sasami high[d] = D_HIGH_MAPLINE (last_using[d], FC, FO, highc); 70813044Sasami } 70913044Sasami else 71013044Sasami { 71113044Sasami low[d] = D_HIGH_MAPLINE (last_diff3, FILEC, FILE0 + d, lowc); 71213044Sasami high[d] = D_HIGH_MAPLINE (last_diff3, FILEC, FILE0 + d, highc); 71313044Sasami } 71413044Sasami 71513044Sasami /* Create a block with the appropriate sizes */ 71613044Sasami result = create_diff3_block (low[0], high[0], low[1], high[1], lowc, highc); 71713044Sasami 71813044Sasami /* Copy information for the common file. 71913044Sasami Return with a zero if any of the compares failed. */ 72013044Sasami 72126541Scharnier for (d = 0; d < 2; d++) 72226541Scharnier for (ptr = using[d]; ptr; ptr = D_NEXT (ptr)) 72326541Scharnier { 72426541Scharnier lin result_offset = D_LOWLINE (ptr, FC) - lowc; 72526541Scharnier 72626541Scharnier if (!copy_stringlist (D_LINEARRAY (ptr, FC), 72713044Sasami D_LENARRAY (ptr, FC), 72813044Sasami D_LINEARRAY (result, FILEC) + result_offset, 72926541Scharnier D_LENARRAY (result, FILEC) + result_offset, 73013052Sasami D_NUMLINES (ptr, FC))) 73113052Sasami return 0; 73213052Sasami } 73313052Sasami 734 /* Copy information for file d. First deal with anything that might be 735 before the first diff. */ 736 737 for (d = 0; d < 2; d++) 738 { 739 struct diff_block *u = using[d]; 740 lin lo = low[d], hi = high[d]; 741 742 for (i = 0; 743 i + lo < (u ? D_LOWLINE (u, FO) : hi + 1); 744 i++) 745 { 746 D_RELNUM (result, FILE0 + d, i) = D_RELNUM (result, FILEC, i); 747 D_RELLEN (result, FILE0 + d, i) = D_RELLEN (result, FILEC, i); 748 } 749 750 for (ptr = u; ptr; ptr = D_NEXT (ptr)) 751 { 752 lin result_offset = D_LOWLINE (ptr, FO) - lo; 753 lin linec; 754 755 if (!copy_stringlist (D_LINEARRAY (ptr, FO), 756 D_LENARRAY (ptr, FO), 757 D_LINEARRAY (result, FILE0 + d) + result_offset, 758 D_LENARRAY (result, FILE0 + d) + result_offset, 759 D_NUMLINES (ptr, FO))) 760 return 0; 761 762 /* Catch the lines between here and the next diff */ 763 linec = D_HIGHLINE (ptr, FC) + 1 - lowc; 764 for (i = D_HIGHLINE (ptr, FO) + 1 - lo; 765 i < (D_NEXT (ptr) ? D_LOWLINE (D_NEXT (ptr), FO) : hi + 1) - lo; 766 i++) 767 { 768 D_RELNUM (result, FILE0 + d, i) = D_RELNUM (result, FILEC, linec); 769 D_RELLEN (result, FILE0 + d, i) = D_RELLEN (result, FILEC, linec); 770 linec++; 771 } 772 } 773 } 774 775 /* Set correspond */ 776 if (!using[0]) 777 D3_TYPE (result) = DIFF_2ND; 778 else if (!using[1]) 779 D3_TYPE (result) = DIFF_1ST; 780 else 781 { 782 lin nl0 = D_NUMLINES (result, FILE0); 783 lin nl1 = D_NUMLINES (result, FILE1); 784 785 if (nl0 != nl1 786 || !compare_line_list (D_LINEARRAY (result, FILE0), 787 D_LENARRAY (result, FILE0), 788 D_LINEARRAY (result, FILE1), 789 D_LENARRAY (result, FILE1), 790 nl0)) 791 D3_TYPE (result) = DIFF_ALL; 792 else 793 D3_TYPE (result) = DIFF_3RD; 794 } 795 796 return result; 797} 798 799/* Copy pointers from a list of strings to a different list of 800 strings. If a spot in the second list is already filled, make sure 801 that it is filled with the same string; if not, return false, the copy 802 incomplete. Upon successful completion of the copy, return true. */ 803 804static bool 805copy_stringlist (char * const fromptrs[], size_t const fromlengths[], 806 char *toptrs[], size_t tolengths[], 807 lin copynum) 808{ 809 register char * const *f = fromptrs; 810 register char **t = toptrs; 811 register size_t const *fl = fromlengths; 812 register size_t *tl = tolengths; 813 814 while (copynum--) 815 { 816 if (*t) 817 { 818 if (*fl != *tl || memcmp (*f, *t, *fl) != 0) 819 return false; 820 } 821 else 822 { 823 *t = *f; 824 *tl = *fl; 825 } 826 827 t++; f++; tl++; fl++; 828 } 829 830 return true; 831} 832 833/* Create a diff3_block, with ranges as specified in the arguments. 834 Allocate the arrays for the various pointers (and zero them) based 835 on the arguments passed. Return the block as a result. */ 836 837static struct diff3_block * 838create_diff3_block (lin low0, lin high0, 839 lin low1, lin high1, 840 lin low2, lin high2) 841{ 842 struct diff3_block *result = xmalloc (sizeof *result); 843 lin numlines; 844 845 D3_TYPE (result) = ERROR; 846 D_NEXT (result) = 0; 847 848 /* Assign ranges */ 849 D_LOWLINE (result, FILE0) = low0; 850 D_HIGHLINE (result, FILE0) = high0; 851 D_LOWLINE (result, FILE1) = low1; 852 D_HIGHLINE (result, FILE1) = high1; 853 D_LOWLINE (result, FILE2) = low2; 854 D_HIGHLINE (result, FILE2) = high2; 855 856 /* Allocate and zero space */ 857 numlines = D_NUMLINES (result, FILE0); 858 if (numlines) 859 { 860 D_LINEARRAY (result, FILE0) = xcalloc (numlines, sizeof (char *)); 861 D_LENARRAY (result, FILE0) = xcalloc (numlines, sizeof (size_t)); 862 } 863 else 864 { 865 D_LINEARRAY (result, FILE0) = 0; 866 D_LENARRAY (result, FILE0) = 0; 867 } 868 869 numlines = D_NUMLINES (result, FILE1); 870 if (numlines) 871 { 872 D_LINEARRAY (result, FILE1) = xcalloc (numlines, sizeof (char *)); 873 D_LENARRAY (result, FILE1) = xcalloc (numlines, sizeof (size_t)); 874 } 875 else 876 { 877 D_LINEARRAY (result, FILE1) = 0; 878 D_LENARRAY (result, FILE1) = 0; 879 } 880 881 numlines = D_NUMLINES (result, FILE2); 882 if (numlines) 883 { 884 D_LINEARRAY (result, FILE2) = xcalloc (numlines, sizeof (char *)); 885 D_LENARRAY (result, FILE2) = xcalloc (numlines, sizeof (size_t)); 886 } 887 else 888 { 889 D_LINEARRAY (result, FILE2) = 0; 890 D_LENARRAY (result, FILE2) = 0; 891 } 892 893 /* Return */ 894 return result; 895} 896 897/* Compare two lists of lines of text. 898 Return 1 if they are equivalent, 0 if not. */ 899 900static bool 901compare_line_list (char * const list1[], size_t const lengths1[], 902 char * const list2[], size_t const lengths2[], 903 lin nl) 904{ 905 char * const *l1 = list1; 906 char * const *l2 = list2; 907 size_t const *lgths1 = lengths1; 908 size_t const *lgths2 = lengths2; 909 910 while (nl--) 911 if (!*l1 || !*l2 || *lgths1 != *lgths2++ 912 || memcmp (*l1++, *l2++, *lgths1++) != 0) 913 return false; 914 return true; 915} 916 917/* Input and parse two way diffs. */ 918 919static struct diff_block * 920process_diff (char const *filea, 921 char const *fileb, 922 struct diff_block **last_block) 923{ 924 char *diff_contents; 925 char *diff_limit; 926 char *scan_diff; 927 enum diff_type dt; 928 lin i; 929 struct diff_block *block_list, **block_list_end, *bptr; 930 size_t too_many_lines = (PTRDIFF_MAX 931 / MIN (sizeof *bptr->lines[1], 932 sizeof *bptr->lengths[1])); 933 934 diff_limit = read_diff (filea, fileb, &diff_contents); 935 scan_diff = diff_contents; 936 block_list_end = &block_list; 937 bptr = 0; /* Pacify `gcc -W'. */ 938 939 while (scan_diff < diff_limit) 940 { 941 bptr = xmalloc (sizeof *bptr); 942 bptr->lines[0] = bptr->lines[1] = 0; 943 bptr->lengths[0] = bptr->lengths[1] = 0; 944 945 dt = process_diff_control (&scan_diff, bptr); 946 if (dt == ERROR || *scan_diff != '\n') 947 { 948 fprintf (stderr, _("%s: diff failed: "), program_name); 949 do 950 { 951 putc (*scan_diff, stderr); 952 } 953 while (*scan_diff++ != '\n'); 954 exit (EXIT_TROUBLE); 955 } 956 scan_diff++; 957 958 /* Force appropriate ranges to be null, if necessary */ 959 switch (dt) 960 { 961 case ADD: 962 bptr->ranges[0][0]++; 963 break; 964 case DELETE: 965 bptr->ranges[1][0]++; 966 break; 967 case CHANGE: 968 break; 969 default: 970 fatal ("internal error: invalid diff type in process_diff"); 971 break; 972 } 973 974 /* Allocate space for the pointers for the lines from filea, and 975 parcel them out among these pointers */ 976 if (dt != ADD) 977 { 978 lin numlines = D_NUMLINES (bptr, 0); 979 if (too_many_lines <= numlines) 980 xalloc_die (); 981 bptr->lines[0] = xmalloc (numlines * sizeof *bptr->lines[0]); 982 bptr->lengths[0] = xmalloc (numlines * sizeof *bptr->lengths[0]); 983 for (i = 0; i < numlines; i++) 984 scan_diff = scan_diff_line (scan_diff, 985 &(bptr->lines[0][i]), 986 &(bptr->lengths[0][i]), 987 diff_limit, 988 '<'); 989 } 990 991 /* Get past the separator for changes */ 992 if (dt == CHANGE) 993 { 994 if (strncmp (scan_diff, "---\n", 4)) 995 fatal ("invalid diff format; invalid change separator"); 996 scan_diff += 4; 997 } 998 999 /* Allocate space for the pointers for the lines from fileb, and 1000 parcel them out among these pointers */ 1001 if (dt != DELETE) 1002 { 1003 lin numlines = D_NUMLINES (bptr, 1); 1004 if (too_many_lines <= numlines) 1005 xalloc_die (); 1006 bptr->lines[1] = xmalloc (numlines * sizeof *bptr->lines[1]); 1007 bptr->lengths[1] = xmalloc (numlines * sizeof *bptr->lengths[1]); 1008 for (i = 0; i < numlines; i++) 1009 scan_diff = scan_diff_line (scan_diff, 1010 &(bptr->lines[1][i]), 1011 &(bptr->lengths[1][i]), 1012 diff_limit, 1013 '>'); 1014 } 1015 1016 /* Place this block on the blocklist. */ 1017 *block_list_end = bptr; 1018 block_list_end = &bptr->next; 1019 } 1020 1021 *block_list_end = 0; 1022 *last_block = bptr; 1023 return block_list; 1024} 1025 1026/* Skip tabs and spaces, and return the first character after them. */ 1027 1028static char * 1029skipwhite (char *s) 1030{ 1031 while (*s == ' ' || *s == '\t') 1032 s++; 1033 return s; 1034} 1035 1036/* Read a nonnegative line number from S, returning the address of the 1037 first character after the line number, and storing the number into 1038 *PNUM. Return 0 if S does not point to a valid line number. */ 1039 1040static char * 1041readnum (char *s, lin *pnum) 1042{ 1043 unsigned char c = *s; 1044 lin num = 0; 1045 1046 if (! ISDIGIT (c)) 1047 return 0; 1048 1049 do 1050 { 1051 num = c - '0' + num * 10; 1052 c = *++s; 1053 } 1054 while (ISDIGIT (c)); 1055 1056 *pnum = num; 1057 return s; 1058} 1059 1060/* Parse a normal format diff control string. Return the type of the 1061 diff (ERROR if the format is bad). All of the other important 1062 information is filled into to the structure pointed to by db, and 1063 the string pointer (whose location is passed to this routine) is 1064 updated to point beyond the end of the string parsed. Note that 1065 only the ranges in the diff_block will be set by this routine. 1066 1067 If some specific pair of numbers has been reduced to a single 1068 number, then both corresponding numbers in the diff block are set 1069 to that number. In general these numbers are interpreted as ranges 1070 inclusive, unless being used by the ADD or DELETE commands. It is 1071 assumed that these will be special cased in a superior routine. */ 1072 1073static enum diff_type 1074process_diff_control (char **string, struct diff_block *db) 1075{ 1076 char *s = *string; 1077 enum diff_type type; 1078 1079 /* Read first set of digits */ 1080 s = readnum (skipwhite (s), &db->ranges[0][RANGE_START]); 1081 if (! s) 1082 return ERROR; 1083 1084 /* Was that the only digit? */ 1085 s = skipwhite (s); 1086 if (*s == ',') 1087 { 1088 s = readnum (s + 1, &db->ranges[0][RANGE_END]); 1089 if (! s) 1090 return ERROR; 1091 } 1092 else 1093 db->ranges[0][RANGE_END] = db->ranges[0][RANGE_START]; 1094 1095 /* Get the letter */ 1096 s = skipwhite (s); 1097 switch (*s) 1098 { 1099 case 'a': 1100 type = ADD; 1101 break; 1102 case 'c': 1103 type = CHANGE; 1104 break; 1105 case 'd': 1106 type = DELETE; 1107 break; 1108 default: 1109 return ERROR; /* Bad format */ 1110 } 1111 s++; /* Past letter */ 1112 1113 /* Read second set of digits */ 1114 s = readnum (skipwhite (s), &db->ranges[1][RANGE_START]); 1115 if (! s) 1116 return ERROR; 1117 1118 /* Was that the only digit? */ 1119 s = skipwhite (s); 1120 if (*s == ',') 1121 { 1122 s = readnum (s + 1, &db->ranges[1][RANGE_END]); 1123 if (! s) 1124 return ERROR; 1125 s = skipwhite (s); /* To move to end */ 1126 } 1127 else 1128 db->ranges[1][RANGE_END] = db->ranges[1][RANGE_START]; 1129 1130 *string = s; 1131 return type; 1132} 1133 1134static char * 1135read_diff (char const *filea, 1136 char const *fileb, 1137 char **output_placement) 1138{ 1139 char *diff_result; 1140 size_t current_chunk_size, total; 1141 int fd, wstatus, status; 1142 int werrno = 0; 1143 struct stat pipestat; 1144 1145#if HAVE_WORKING_FORK || HAVE_WORKING_VFORK 1146 1147 char const *argv[9]; 1148 char const **ap; 1149 int fds[2]; 1150 pid_t pid; 1151 1152 ap = argv; 1153 *ap++ = diff_program; 1154 if (text) 1155 *ap++ = "-a"; 1156 if (strip_trailing_cr) 1157 *ap++ = "--strip-trailing-cr"; 1158 *ap++ = "--horizon-lines=100"; 1159 *ap++ = "--"; 1160 *ap++ = filea; 1161 *ap++ = fileb; 1162 *ap = 0; 1163 1164 if (pipe (fds) != 0) 1165 perror_with_exit ("pipe"); 1166 1167 pid = vfork (); 1168 if (pid == 0) 1169 { 1170 /* Child */ 1171 close (fds[0]); 1172 if (fds[1] != STDOUT_FILENO) 1173 { 1174 dup2 (fds[1], STDOUT_FILENO); 1175 close (fds[1]); 1176 } 1177 1178 /* The cast to (char **) is needed for portability to older 1179 hosts with a nonstandard prototype for execvp. */ 1180 execvp (diff_program, (char **) argv); 1181 1182 _exit (errno == ENOENT ? 127 : 126); 1183 } 1184 1185 if (pid == -1) 1186 perror_with_exit ("fork"); 1187 1188 close (fds[1]); /* Prevent erroneous lack of EOF */ 1189 fd = fds[0]; 1190 1191#else 1192 1193 FILE *fpipe; 1194 char const args[] = " --horizon-lines=100 -- "; 1195 char *command = xmalloc (quote_system_arg (0, diff_program) 1196 + sizeof "-a" 1197 + sizeof "--strip-trailing-cr" 1198 + sizeof args - 1 1199 + quote_system_arg (0, filea) + 1 1200 + quote_system_arg (0, fileb) + 1); 1201 char *p = command; 1202 p += quote_system_arg (p, diff_program); 1203 if (text) 1204 { 1205 strcpy (p, " -a"); 1206 p += 3; 1207 } 1208 if (strip_trailing_cr) 1209 { 1210 strcpy (p, " --strip-trailing-cr"); 1211 p += 20; 1212 } 1213 strcpy (p, args); 1214 p += sizeof args - 1; 1215 p += quote_system_arg (p, filea); 1216 *p++ = ' '; 1217 p += quote_system_arg (p, fileb); 1218 *p = 0; 1219 errno = 0; 1220 fpipe = popen (command, "r"); 1221 if (!fpipe) 1222 perror_with_exit (command); 1223 free (command); 1224 fd = fileno (fpipe); 1225 1226#endif 1227 1228 if (fstat (fd, &pipestat) != 0) 1229 perror_with_exit ("fstat"); 1230 current_chunk_size = MAX (1, STAT_BLOCKSIZE (pipestat)); 1231 diff_result = xmalloc (current_chunk_size); 1232 total = 0; 1233 1234 for (;;) 1235 { 1236 size_t bytes_to_read = current_chunk_size - total; 1237 size_t bytes = block_read (fd, diff_result + total, bytes_to_read); 1238 total += bytes; 1239 if (bytes != bytes_to_read) 1240 { 1241 if (bytes == SIZE_MAX) 1242 perror_with_exit (_("read failed")); 1243 break; 1244 } 1245 if (PTRDIFF_MAX / 2 <= current_chunk_size) 1246 xalloc_die (); 1247 current_chunk_size *= 2; 1248 diff_result = xrealloc (diff_result, current_chunk_size); 1249 } 1250 1251 if (total != 0 && diff_result[total-1] != '\n') 1252 fatal ("invalid diff format; incomplete last line"); 1253 1254 *output_placement = diff_result; 1255 1256#if ! (HAVE_WORKING_FORK || HAVE_WORKING_VFORK) 1257 1258 wstatus = pclose (fpipe); 1259 if (wstatus == -1) 1260 werrno = errno; 1261 1262#else 1263 1264 if (close (fd) != 0) 1265 perror_with_exit ("close"); 1266 if (waitpid (pid, &wstatus, 0) < 0) 1267 perror_with_exit ("waitpid"); 1268 1269#endif 1270 1271 status = ! werrno && WIFEXITED (wstatus) ? WEXITSTATUS (wstatus) : INT_MAX; 1272 1273 if (EXIT_TROUBLE <= status) 1274 error (EXIT_TROUBLE, werrno, 1275 _(status == 126 1276 ? "subsidiary program `%s' could not be invoked" 1277 : status == 127 1278 ? "subsidiary program `%s' not found" 1279 : status == INT_MAX 1280 ? "subsidiary program `%s' failed" 1281 : "subsidiary program `%s' failed (exit status %d)"), 1282 diff_program, status); 1283 1284 return diff_result + total; 1285} 1286 1287 1288/* Scan a regular diff line (consisting of > or <, followed by a 1289 space, followed by text (including nulls) up to a newline. 1290 1291 This next routine began life as a macro and many parameters in it 1292 are used as call-by-reference values. */ 1293static char * 1294scan_diff_line (char *scan_ptr, char **set_start, size_t *set_length, 1295 char *limit, char leadingchar) 1296{ 1297 char *line_ptr; 1298 1299 if (!(scan_ptr[0] == leadingchar 1300 && scan_ptr[1] == ' ')) 1301 fatal ("invalid diff format; incorrect leading line chars"); 1302 1303 *set_start = line_ptr = scan_ptr + 2; 1304 while (*line_ptr++ != '\n') 1305 continue; 1306 1307 /* Include newline if the original line ended in a newline, 1308 or if an edit script is being generated. 1309 Copy any missing newline message to stderr if an edit script is being 1310 generated, because edit scripts cannot handle missing newlines. 1311 Return the beginning of the next line. */ 1312 *set_length = line_ptr - *set_start; 1313 if (line_ptr < limit && *line_ptr == '\\') 1314 { 1315 if (edscript) 1316 fprintf (stderr, "%s:", program_name); 1317 else 1318 --*set_length; 1319 line_ptr++; 1320 do 1321 { 1322 if (edscript) 1323 putc (*line_ptr, stderr); 1324 } 1325 while (*line_ptr++ != '\n'); 1326 } 1327 1328 return line_ptr; 1329} 1330 1331/* Output a three way diff passed as a list of diff3_block's. The 1332 argument MAPPING is indexed by external file number (in the 1333 argument list) and contains the internal file number (from the diff 1334 passed). This is important because the user expects outputs in 1335 terms of the argument list number, and the diff passed may have 1336 been done slightly differently (if the last argument was "-", for 1337 example). REV_MAPPING is the inverse of MAPPING. */ 1338 1339static void 1340output_diff3 (FILE *outputfile, struct diff3_block *diff, 1341 int const mapping[3], int const rev_mapping[3]) 1342{ 1343 int i; 1344 int oddoneout; 1345 char *cp; 1346 struct diff3_block *ptr; 1347 lin line; 1348 size_t length; 1349 int dontprint; 1350 static int skew_increment[3] = { 2, 3, 1 }; /* 0==>2==>1==>3 */ 1351 char const *line_prefix = initial_tab ? "\t" : " "; 1352 1353 for (ptr = diff; ptr; ptr = D_NEXT (ptr)) 1354 { 1355 char x[2]; 1356 1357 switch (ptr->correspond) 1358 { 1359 case DIFF_ALL: 1360 x[0] = 0; 1361 dontprint = 3; /* Print them all */ 1362 oddoneout = 3; /* Nobody's odder than anyone else */ 1363 break; 1364 case DIFF_1ST: 1365 case DIFF_2ND: 1366 case DIFF_3RD: 1367 oddoneout = rev_mapping[ptr->correspond - DIFF_1ST]; 1368 1369 x[0] = oddoneout + '1'; 1370 x[1] = 0; 1371 dontprint = oddoneout == 0; 1372 break; 1373 default: 1374 fatal ("internal error: invalid diff type passed to output"); 1375 } 1376 fprintf (outputfile, "====%s\n", x); 1377 1378 /* Go 0, 2, 1 if the first and third outputs are equivalent. */ 1379 for (i = 0; i < 3; 1380 i = (oddoneout == 1 ? skew_increment[i] : i + 1)) 1381 { 1382 int realfile = mapping[i]; 1383 lin lowt = D_LOWLINE (ptr, realfile); 1384 lin hight = D_HIGHLINE (ptr, realfile); 1385 long int llowt = lowt; 1386 long int lhight = hight; 1387 1388 fprintf (outputfile, "%d:", i + 1); 1389 switch (lowt - hight) 1390 { 1391 case 1: 1392 fprintf (outputfile, "%lda\n", llowt - 1); 1393 break; 1394 case 0: 1395 fprintf (outputfile, "%ldc\n", llowt); 1396 break; 1397 default: 1398 fprintf (outputfile, "%ld,%ldc\n", llowt, lhight); 1399 break; 1400 } 1401 1402 if (i == dontprint) continue; 1403 1404 if (lowt <= hight) 1405 { 1406 line = 0; 1407 do 1408 { 1409 fprintf (outputfile, line_prefix); 1410 cp = D_RELNUM (ptr, realfile, line); 1411 length = D_RELLEN (ptr, realfile, line); 1412 fwrite (cp, sizeof (char), length, outputfile); 1413 } 1414 while (++line < hight - lowt + 1); 1415 if (cp[length - 1] != '\n') 1416 fprintf (outputfile, "\n\\ %s\n", 1417 _("No newline at end of file")); 1418 } 1419 } 1420 } 1421} 1422 1423 1424/* Output to OUTPUTFILE the lines of B taken from FILENUM. Double any 1425 initial '.'s; yield nonzero if any initial '.'s were doubled. */ 1426 1427static bool 1428dotlines (FILE *outputfile, struct diff3_block *b, int filenum) 1429{ 1430 lin i; 1431 bool leading_dot = false; 1432 1433 for (i = 0; 1434 i < D_NUMLINES (b, filenum); 1435 i++) 1436 { 1437 char *line = D_RELNUM (b, filenum, i); 1438 if (line[0] == '.') 1439 { 1440 leading_dot = true; 1441 fprintf (outputfile, "."); 1442 } 1443 fwrite (line, sizeof (char), 1444 D_RELLEN (b, filenum, i), outputfile); 1445 } 1446 1447 return leading_dot; 1448} 1449 1450/* Output to OUTPUTFILE a '.' line. If LEADING_DOT is true, also 1451 output a command that removes initial '.'s starting with line START 1452 and continuing for NUM lines. (START is long int, not lin, for 1453 convenience with printf %ld formats.) */ 1454 1455static void 1456undotlines (FILE *outputfile, bool leading_dot, long int start, lin num) 1457{ 1458 fprintf (outputfile, ".\n"); 1459 if (leading_dot) 1460 { 1461 if (num == 1) 1462 fprintf (outputfile, "%lds/^\\.//\n", start); 1463 else 1464 fprintf (outputfile, "%ld,%lds/^\\.//\n", start, start + num - 1); 1465 } 1466} 1467 1468/* Output a diff3 set of blocks as an ed script. This script applies 1469 the changes between file's 2 & 3 to file 1. Take the precise 1470 format of the ed script to be output from global variables set 1471 during options processing. Reverse the order of 1472 the set of diff3 blocks in DIFF; this gets 1473 around the problems involved with changing line numbers in an ed 1474 script. 1475 1476 As in `output_diff3', the variable MAPPING maps from file number 1477 according to the argument list to file number according to the diff 1478 passed. All files listed below are in terms of the argument list. 1479 REV_MAPPING is the inverse of MAPPING. 1480 1481 FILE0, FILE1 and FILE2 are the strings to print as the names of the 1482 three files. These may be the actual names, or may be the 1483 arguments specified with -L. 1484 1485 Return 1 if conflicts were found. */ 1486 1487static bool 1488output_diff3_edscript (FILE *outputfile, struct diff3_block *diff, 1489 int const mapping[3], int const rev_mapping[3], 1490 char const *file0, char const *file1, char const *file2) 1491{ 1492 bool leading_dot; 1493 bool conflicts_found = false; 1494 bool conflict; 1495 struct diff3_block *b; 1496 1497 for (b = reverse_diff3_blocklist (diff); b; b = b->next) 1498 { 1499 /* Must do mapping correctly. */ 1500 enum diff_type type 1501 = (b->correspond == DIFF_ALL 1502 ? DIFF_ALL 1503 : DIFF_1ST + rev_mapping[b->correspond - DIFF_1ST]); 1504 1505 long int low0, high0; 1506 1507 /* If we aren't supposed to do this output block, skip it. */ 1508 switch (type) 1509 { 1510 default: continue; 1511 case DIFF_2ND: if (!show_2nd) continue; conflict = true; break; 1512 case DIFF_3RD: if (overlap_only) continue; conflict = false; break; 1513 case DIFF_ALL: if (simple_only) continue; conflict = flagging; break; 1514 } 1515 1516 low0 = D_LOWLINE (b, mapping[FILE0]); 1517 high0 = D_HIGHLINE (b, mapping[FILE0]); 1518 1519 if (conflict) 1520 { 1521 conflicts_found = true; 1522 1523 1524 /* Mark end of conflict. */ 1525 1526 fprintf (outputfile, "%lda\n", high0); 1527 leading_dot = false; 1528 if (type == DIFF_ALL) 1529 { 1530 if (show_2nd) 1531 { 1532 /* Append lines from FILE1. */ 1533 fprintf (outputfile, "||||||| %s\n", file1); 1534 leading_dot = dotlines (outputfile, b, mapping[FILE1]); 1535 } 1536 /* Append lines from FILE2. */ 1537 fprintf (outputfile, "=======\n"); 1538 leading_dot |= dotlines (outputfile, b, mapping[FILE2]); 1539 } 1540 fprintf (outputfile, ">>>>>>> %s\n", file2); 1541 undotlines (outputfile, leading_dot, high0 + 2, 1542 (D_NUMLINES (b, mapping[FILE1]) 1543 + D_NUMLINES (b, mapping[FILE2]) + 1)); 1544 1545 1546 /* Mark start of conflict. */ 1547 1548 fprintf (outputfile, "%lda\n<<<<<<< %s\n", low0 - 1, 1549 type == DIFF_ALL ? file0 : file1); 1550 leading_dot = false; 1551 if (type == DIFF_2ND) 1552 { 1553 /* Prepend lines from FILE1. */ 1554 leading_dot = dotlines (outputfile, b, mapping[FILE1]); 1555 fprintf (outputfile, "=======\n"); 1556 } 1557 undotlines (outputfile, leading_dot, low0 + 1, 1558 D_NUMLINES (b, mapping[FILE1])); 1559 } 1560 else if (D_NUMLINES (b, mapping[FILE2]) == 0) 1561 /* Write out a delete */ 1562 { 1563 if (low0 == high0) 1564 fprintf (outputfile, "%ldd\n", low0); 1565 else 1566 fprintf (outputfile, "%ld,%ldd\n", low0, high0); 1567 } 1568 else 1569 /* Write out an add or change */ 1570 { 1571 switch (high0 - low0) 1572 { 1573 case -1: 1574 fprintf (outputfile, "%lda\n", high0); 1575 break; 1576 case 0: 1577 fprintf (outputfile, "%ldc\n", high0); 1578 break; 1579 default: 1580 fprintf (outputfile, "%ld,%ldc\n", low0, high0); 1581 break; 1582 } 1583 1584 undotlines (outputfile, dotlines (outputfile, b, mapping[FILE2]), 1585 low0, D_NUMLINES (b, mapping[FILE2])); 1586 } 1587 } 1588 if (finalwrite) fprintf (outputfile, "w\nq\n"); 1589 return conflicts_found; 1590} 1591 1592/* Read from INFILE and output to OUTPUTFILE a set of diff3_blocks 1593 DIFF as a merged file. This acts like 'ed file0 1594 <[output_diff3_edscript]', except that it works even for binary 1595 data or incomplete lines. 1596 1597 As before, MAPPING maps from arg list file number to diff file 1598 number, REV_MAPPING is its inverse, and FILE0, FILE1, and FILE2 are 1599 the names of the files. 1600 1601 Return 1 if conflicts were found. */ 1602 1603static bool 1604output_diff3_merge (FILE *infile, FILE *outputfile, struct diff3_block *diff, 1605 int const mapping[3], int const rev_mapping[3], 1606 char const *file0, char const *file1, char const *file2) 1607{ 1608 int c; 1609 lin i; 1610 bool conflicts_found = false; 1611 bool conflict; 1612 struct diff3_block *b; 1613 lin linesread = 0; 1614 1615 for (b = diff; b; b = b->next) 1616 { 1617 /* Must do mapping correctly. */ 1618 enum diff_type type 1619 = ((b->correspond == DIFF_ALL) 1620 ? DIFF_ALL 1621 : DIFF_1ST + rev_mapping[b->correspond - DIFF_1ST]); 1622 char const *format_2nd = "<<<<<<< %s\n"; 1623 1624 /* If we aren't supposed to do this output block, skip it. */ 1625 switch (type) 1626 { 1627 default: continue; 1628 case DIFF_2ND: if (!show_2nd) continue; conflict = true; break; 1629 case DIFF_3RD: if (overlap_only) continue; conflict = false; break; 1630 case DIFF_ALL: if (simple_only) continue; conflict = flagging; 1631 format_2nd = "||||||| %s\n"; 1632 break; 1633 } 1634 1635 /* Copy I lines from file 0. */ 1636 i = D_LOWLINE (b, FILE0) - linesread - 1; 1637 linesread += i; 1638 while (0 <= --i) 1639 do 1640 { 1641 c = getc (infile); 1642 if (c == EOF) 1643 { 1644 if (ferror (infile)) 1645 perror_with_exit (_("read failed")); 1646 else if (feof (infile)) 1647 fatal ("input file shrank"); 1648 } 1649 putc (c, outputfile); 1650 } 1651 while (c != '\n'); 1652 1653 if (conflict) 1654 { 1655 conflicts_found = true; 1656 1657 if (type == DIFF_ALL) 1658 { 1659 /* Put in lines from FILE0 with bracket. */ 1660 fprintf (outputfile, "<<<<<<< %s\n", file0); 1661 for (i = 0; 1662 i < D_NUMLINES (b, mapping[FILE0]); 1663 i++) 1664 fwrite (D_RELNUM (b, mapping[FILE0], i), sizeof (char), 1665 D_RELLEN (b, mapping[FILE0], i), outputfile); 1666 } 1667 1668 if (show_2nd) 1669 { 1670 /* Put in lines from FILE1 with bracket. */ 1671 fprintf (outputfile, format_2nd, file1); 1672 for (i = 0; 1673 i < D_NUMLINES (b, mapping[FILE1]); 1674 i++) 1675 fwrite (D_RELNUM (b, mapping[FILE1], i), sizeof (char), 1676 D_RELLEN (b, mapping[FILE1], i), outputfile); 1677 } 1678 1679 fprintf (outputfile, "=======\n"); 1680 } 1681 1682 /* Put in lines from FILE2. */ 1683 for (i = 0; 1684 i < D_NUMLINES (b, mapping[FILE2]); 1685 i++) 1686 fwrite (D_RELNUM (b, mapping[FILE2], i), sizeof (char), 1687 D_RELLEN (b, mapping[FILE2], i), outputfile); 1688 1689 if (conflict) 1690 fprintf (outputfile, ">>>>>>> %s\n", file2); 1691 1692 /* Skip I lines in file 0. */ 1693 i = D_NUMLINES (b, FILE0); 1694 linesread += i; 1695 while (0 <= --i) 1696 while ((c = getc (infile)) != '\n') 1697 if (c == EOF) 1698 { 1699 if (ferror (infile)) 1700 perror_with_exit (_("read failed")); 1701 else if (feof (infile)) 1702 { 1703 if (i || b->next) 1704 fatal ("input file shrank"); 1705 return conflicts_found; 1706 } 1707 } 1708 } 1709 /* Copy rest of common file. */ 1710 while ((c = getc (infile)) != EOF || !(ferror (infile) | feof (infile))) 1711 putc (c, outputfile); 1712 return conflicts_found; 1713} 1714 1715/* Reverse the order of the list of diff3 blocks. */ 1716 1717static struct diff3_block * 1718reverse_diff3_blocklist (struct diff3_block *diff) 1719{ 1720 register struct diff3_block *tmp, *next, *prev; 1721 1722 for (tmp = diff, prev = 0; tmp; tmp = next) 1723 { 1724 next = tmp->next; 1725 tmp->next = prev; 1726 prev = tmp; 1727 } 1728 1729 return prev; 1730} 1731 1732static void 1733fatal (char const *msgid) 1734{ 1735 error (EXIT_TROUBLE, 0, "%s", _(msgid)); 1736 abort (); 1737} 1738 1739static void 1740perror_with_exit (char const *string) 1741{ 1742 error (EXIT_TROUBLE, errno, "%s", string); 1743 abort (); 1744} 1745