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