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