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