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