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