after fixing the repo corruption, turn on maximum hardening flags as a bonus level...
[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 /* 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 \f
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
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
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
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
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 \f
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 *
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 *
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
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 *
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
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 \f
1069 /*
1070  * Routines to input and parse two way diffs.
1071  */
1072
1073 extern char **environ;
1074
1075 static struct diff_block *
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
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 *
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 *
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
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 = 0;
1443   char *cp;
1444   struct diff3_block *ptr;
1445   int line;
1446   size_t length;
1447   int dontprint = 0;
1448   static int skew_increment[3] = { 2, 3, 1 }; /* 0==>2==>1==>3 */
1449
1450   for (ptr = diff; ptr; ptr = D_NEXT (ptr))
1451     {
1452       char x[2];
1453
1454       switch (ptr->correspond)
1455         {
1456         case DIFF_ALL:
1457           x[0] = '\0';
1458           dontprint = 3;        /* Print them all */
1459           oddoneout = 3;        /* Nobody's odder than anyone else */
1460           break;
1461         case DIFF_1ST:
1462         case DIFF_2ND:
1463         case DIFF_3RD:
1464           oddoneout = rev_mapping[(int) ptr->correspond - (int) DIFF_1ST];
1465
1466           x[0] = oddoneout + '1';
1467           x[1] = '\0';
1468           dontprint = oddoneout==0;
1469           break;
1470         default:
1471           diff3_fatal ("internal error: invalid diff type passed to output");
1472         }
1473       printf_output ("====%s\n", x);
1474
1475       /* Go 0, 2, 1 if the first and third outputs are equivalent.  */
1476       for (i = 0; i < 3;
1477            i = (oddoneout == 1 ? skew_increment[i] : i + 1))
1478         {
1479           int realfile = mapping[i];
1480           int
1481             lowt = D_LOWLINE (ptr, realfile),
1482             hight = D_HIGHLINE (ptr, realfile);
1483
1484           printf_output ("%d:", i + 1);
1485           switch (lowt - hight)
1486             {
1487             case 1:
1488               printf_output ("%da\n", lowt - 1);
1489               break;
1490             case 0:
1491               printf_output ("%dc\n", lowt);
1492               break;
1493             default:
1494               printf_output ("%d,%dc\n", lowt, hight);
1495               break;
1496             }
1497
1498           if (i == dontprint) continue;
1499
1500           if (lowt <= hight)
1501             {
1502               line = 0;
1503               do
1504                 {
1505                   printf_output (tab_align_flag ? "\t" : "  ");
1506                   cp = D_RELNUM (ptr, realfile, line);
1507                   length = D_RELLEN (ptr, realfile, line);
1508                   write_output (cp, length);
1509                 }
1510               while (++line < hight - lowt + 1);
1511               if (cp[length - 1] != '\n')
1512                 printf_output ("\n\\ No newline at end of file\n");
1513             }
1514         }
1515     }
1516 }
1517
1518
1519 /*
1520  * Output the lines of B taken from FILENUM.
1521  * Double any initial '.'s; yield nonzero if any initial '.'s were doubled.
1522  */
1523 static int
1524 dotlines (b, filenum)
1525      struct diff3_block *b;
1526      int filenum;
1527 {
1528   int i;
1529   int leading_dot = 0;
1530
1531   for (i = 0;
1532        i < D_NUMLINES (b, filenum);
1533        i++)
1534     {
1535       char *line = D_RELNUM (b, filenum, i);
1536       if (line[0] == '.')
1537         {
1538           leading_dot = 1;
1539           write_output (".", 1);
1540         }
1541       write_output (line, D_RELLEN (b, filenum, i));
1542     }
1543
1544   return leading_dot;
1545 }
1546
1547 /*
1548  * Output to OUTPUTFILE a '.' line.  If LEADING_DOT is nonzero,
1549  * also output a command that removes initial '.'s
1550  * starting with line START and continuing for NUM lines.
1551  */
1552 static void
1553 undotlines (leading_dot, start, num)
1554      int leading_dot, start, num;
1555 {
1556   write_output (".\n", 2);
1557   if (leading_dot) {
1558     if (num == 1)
1559       printf_output ("%ds/^\\.//\n", start);
1560     else
1561       printf_output ("%d,%ds/^\\.//\n", start, start + num - 1);
1562   }
1563 }
1564
1565 /*
1566  * This routine outputs a diff3 set of blocks as an ed script.  This
1567  * script applies the changes between file's 2 & 3 to file 1.  It
1568  * takes the precise format of the ed script to be output from global
1569  * variables set during options processing.  Note that it does
1570  * destructive things to the set of diff3 blocks it is passed; it
1571  * reverses their order (this gets around the problems involved with
1572  * changing line numbers in an ed script).
1573  *
1574  * Note that this routine has the same problem of mapping as the last
1575  * one did; the variable MAPPING maps from file number according to
1576  * the argument list to file number according to the diff passed.  All
1577  * files listed below are in terms of the argument list.
1578  * REV_MAPPING is the inverse of MAPPING.
1579  *
1580  * The arguments FILE0, FILE1 and FILE2 are the strings to print
1581  * as the names of the three files.  These may be the actual names,
1582  * or may be the arguments specified with -L.
1583  *
1584  * Returns 1 if conflicts were found.
1585  */
1586
1587 static int
1588 output_diff3_edscript (diff, mapping, rev_mapping, file0, file1, file2)
1589      struct diff3_block *diff;
1590      int const mapping[3], rev_mapping[3];
1591      char const *file0, *file1, *file2;
1592 {
1593   int leading_dot;
1594   int conflicts_found = 0, conflict;
1595   struct diff3_block *b;
1596
1597   for (b = reverse_diff3_blocklist (diff); b; b = b->next)
1598     {
1599       /* Must do mapping correctly.  */
1600       enum diff_type type
1601         = ((b->correspond == DIFF_ALL) ?
1602            DIFF_ALL :
1603            ((enum diff_type)
1604             (((int) DIFF_1ST)
1605              + rev_mapping[(int) b->correspond - (int) DIFF_1ST])));
1606
1607       /* If we aren't supposed to do this output block, skip it.  */
1608       switch (type)
1609         {
1610         default: continue;
1611         case DIFF_2ND: if (!show_2nd) continue; conflict = 1; break;
1612         case DIFF_3RD: if (overlap_only) continue; conflict = 0; break;
1613         case DIFF_ALL: if (simple_only) continue; conflict = flagging; break;
1614         }
1615
1616       if (conflict)
1617         {
1618           conflicts_found = 1;
1619
1620
1621           /* Mark end of conflict.  */
1622
1623           printf_output ("%da\n", D_HIGHLINE (b, mapping[FILE0]));
1624           leading_dot = 0;
1625           if (type == DIFF_ALL)
1626             {
1627               if (show_2nd)
1628                 {
1629                   /* Append lines from FILE1.  */
1630                   printf_output ("||||||| %s\n", file1);
1631                   leading_dot = dotlines (b, mapping[FILE1]);
1632                 }
1633               /* Append lines from FILE2.  */
1634               printf_output ("=======\n");
1635               leading_dot |= dotlines (b, mapping[FILE2]);
1636             }
1637           printf_output (">>>>>>> %s\n", file2);
1638           undotlines (leading_dot,
1639                       D_HIGHLINE (b, mapping[FILE0]) + 2,
1640                       (D_NUMLINES (b, mapping[FILE1])
1641                        + D_NUMLINES (b, mapping[FILE2]) + 1));
1642
1643
1644           /* Mark start of conflict.  */
1645
1646           printf_output ("%da\n<<<<<<< %s\n",
1647                          D_LOWLINE (b, mapping[FILE0]) - 1,
1648                          type == DIFF_ALL ? file0 : file1);
1649           leading_dot = 0;
1650           if (type == DIFF_2ND)
1651             {
1652               /* Prepend lines from FILE1.  */
1653               leading_dot = dotlines (b, mapping[FILE1]);
1654               printf_output ("=======\n");
1655             }
1656           undotlines (leading_dot,
1657                       D_LOWLINE (b, mapping[FILE0]) + 1,
1658                       D_NUMLINES (b, mapping[FILE1]));
1659         }
1660       else if (D_NUMLINES (b, mapping[FILE2]) == 0)
1661         /* Write out a delete */
1662         {
1663           if (D_NUMLINES (b, mapping[FILE0]) == 1)
1664             printf_output ("%dd\n", D_LOWLINE (b, mapping[FILE0]));
1665           else
1666             printf_output ("%d,%dd\n",
1667                            D_LOWLINE (b, mapping[FILE0]),
1668                            D_HIGHLINE (b, mapping[FILE0]));
1669         }
1670       else
1671         /* Write out an add or change */
1672         {
1673           switch (D_NUMLINES (b, mapping[FILE0]))
1674             {
1675             case 0:
1676               printf_output ("%da\n", D_HIGHLINE (b, mapping[FILE0]));
1677               break;
1678             case 1:
1679               printf_output ("%dc\n", D_HIGHLINE (b, mapping[FILE0]));
1680               break;
1681             default:
1682               printf_output ("%d,%dc\n",
1683                              D_LOWLINE (b, mapping[FILE0]),
1684                              D_HIGHLINE (b, mapping[FILE0]));
1685               break;
1686             }
1687
1688           undotlines (dotlines (b, mapping[FILE2]),
1689                       D_LOWLINE (b, mapping[FILE0]),
1690                       D_NUMLINES (b, mapping[FILE2]));
1691         }
1692     }
1693   if (finalwrite) printf_output ("w\nq\n");
1694   return conflicts_found;
1695 }
1696
1697 /*
1698  * Read from INFILE and output to the standard output file a set of
1699  * diff3_ blocks DIFF as a merged file.  This acts like 'ed file0
1700  * <[output_diff3_edscript]', except that it works even for binary
1701  * data or incomplete lines.
1702  *
1703  * As before, MAPPING maps from arg list file number to diff file number,
1704  * REV_MAPPING is its inverse,
1705  * and FILE0, FILE1, and FILE2 are the names of the files.
1706  *
1707  * Returns 1 if conflicts were found.
1708  */
1709
1710 static int
1711 output_diff3_merge (infile, diff, mapping, rev_mapping,
1712                     file0, file1, file2)
1713      FILE *infile;
1714      struct diff3_block *diff;
1715      int const mapping[3], rev_mapping[3];
1716      char const *file0, *file1, *file2;
1717 {
1718   int c, i;
1719   char cc;
1720   int conflicts_found = 0, conflict;
1721   struct diff3_block *b;
1722   int linesread = 0;
1723
1724   for (b = diff; b; b = b->next)
1725     {
1726       /* Must do mapping correctly.  */
1727       enum diff_type type
1728         = ((b->correspond == DIFF_ALL) ?
1729            DIFF_ALL :
1730            ((enum diff_type)
1731             (((int) DIFF_1ST)
1732              + rev_mapping[(int) b->correspond - (int) DIFF_1ST])));
1733       char const *format_2nd = "<<<<<<< %s\n";
1734
1735       /* If we aren't supposed to do this output block, skip it.  */
1736       switch (type)
1737         {
1738         default: continue;
1739         case DIFF_2ND: if (!show_2nd) continue; conflict = 1; break;
1740         case DIFF_3RD: if (overlap_only) continue; conflict = 0; break;
1741         case DIFF_ALL: if (simple_only) continue; conflict = flagging;
1742           format_2nd = "||||||| %s\n";
1743           break;
1744         }
1745
1746       /* Copy I lines from file 0.  */
1747       i = D_LOWLINE (b, FILE0) - linesread - 1;
1748       linesread += i;
1749       while (0 <= --i)
1750         do
1751           {
1752             c = getc (infile);
1753             if (c == EOF) {
1754               if (ferror (infile))
1755                 diff3_perror_with_exit ("input file");
1756               else if (feof (infile))
1757                 diff3_fatal ("input file shrank");
1758             }
1759             cc = c;
1760             write_output (&cc, 1);
1761           }
1762         while (c != '\n');
1763
1764       if (conflict)
1765         {
1766           conflicts_found = 1;
1767
1768           if (type == DIFF_ALL)
1769             {
1770               /* Put in lines from FILE0 with bracket.  */
1771               printf_output ("<<<<<<< %s\n", file0);
1772               for (i = 0;
1773                    i < D_NUMLINES (b, mapping[FILE0]);
1774                    i++)
1775                 write_output (D_RELNUM (b, mapping[FILE0], i),
1776                               D_RELLEN (b, mapping[FILE0], i));
1777             }
1778
1779           if (show_2nd)
1780             {
1781               /* Put in lines from FILE1 with bracket.  */
1782               printf_output (format_2nd, file1);
1783               for (i = 0;
1784                    i < D_NUMLINES (b, mapping[FILE1]);
1785                    i++)
1786                 write_output (D_RELNUM (b, mapping[FILE1], i),
1787                               D_RELLEN (b, mapping[FILE1], i));
1788             }
1789
1790           printf_output ("=======\n");
1791         }
1792
1793       /* Put in lines from FILE2.  */
1794       for (i = 0;
1795            i < D_NUMLINES (b, mapping[FILE2]);
1796            i++)
1797         write_output (D_RELNUM (b, mapping[FILE2], i),
1798                       D_RELLEN (b, mapping[FILE2], i));
1799
1800       if (conflict)
1801         printf_output (">>>>>>> %s\n", file2);
1802
1803       /* Skip I lines in file 0.  */
1804       i = D_NUMLINES (b, FILE0);
1805       linesread += i;
1806       while (0 <= --i)
1807         while ((c = getc (infile)) != '\n')
1808           if (c == EOF) {
1809             if (ferror (infile))
1810               diff3_perror_with_exit ("input file");
1811             else if (feof (infile))
1812               {
1813                 if (i || b->next)
1814                   diff3_fatal ("input file shrank");
1815                 return conflicts_found;
1816               }
1817           }
1818     }
1819   /* Copy rest of common file.  */
1820   while ((c = getc (infile)) != EOF || !(ferror (infile) | feof (infile)))
1821     {
1822       cc = c;
1823       write_output (&cc, 1);
1824     }
1825   return conflicts_found;
1826 }
1827
1828 /*
1829  * Reverse the order of the list of diff3 blocks.
1830  */
1831 static struct diff3_block *
1832 reverse_diff3_blocklist (diff)
1833      struct diff3_block *diff;
1834 {
1835   register struct diff3_block *tmp, *next, *prev;
1836
1837   for (tmp = diff, prev = 0;  tmp;  tmp = next)
1838     {
1839       next = tmp->next;
1840       tmp->next = prev;
1841       prev = tmp;
1842     }
1843
1844   return prev;
1845 }
1846 \f
1847 static size_t
1848 myread (fd, ptr, size)
1849      int fd;
1850      char *ptr;
1851      size_t size;
1852 {
1853   ssize_t result = read (fd, ptr, size);
1854   if (result == -1)
1855     diff3_perror_with_exit ("read failed");
1856   return (size_t)result;
1857 }
1858 \f
1859 static void
1860 diff3_fatal (string)
1861      char const *string;
1862 {
1863   diff_error ("%s", string, 0);
1864   DIFF3_ABORT (2);
1865 }
1866
1867 static void
1868 diff3_perror_with_exit (string)
1869      char const *string;
1870 {
1871   perror_with_name (string);
1872   DIFF3_ABORT (2);
1873 }
1874
1875 static void
1876 initialize_main (argcp, argvp)
1877     int *argcp;
1878     char ***argvp;
1879 {
1880   always_text = 0;
1881   edscript = 0;
1882   flagging = 0;
1883   tab_align_flag = 0;
1884   simple_only = 0;
1885   overlap_only = 0;
1886   show_2nd = 0;
1887   finalwrite = 0;
1888   merge = 0;
1889   diff_program_name = (*argvp)[0];
1890   outfile = NULL;
1891 }
1892
1893 static void
1894 free_diff_blocks(p)
1895     struct diff_block *p;
1896 {
1897   register struct diff_block *next;
1898
1899   while (p)
1900     {
1901       next = p->next;
1902       if (p->lines[0]) free(p->lines[0]);
1903       if (p->lines[1]) free(p->lines[1]);
1904       if (p->lengths[0]) free(p->lengths[0]);
1905       if (p->lengths[1]) free(p->lengths[1]);
1906       free(p);
1907       p = next;
1908     }
1909 }
1910
1911 static void
1912 free_diff3_blocks(p)
1913     struct diff3_block *p;
1914 {
1915   register struct diff3_block *next;
1916
1917   while (p)
1918     {
1919       next = p->next;
1920       if (p->lines[0]) free(p->lines[0]);
1921       if (p->lines[1]) free(p->lines[1]);
1922       if (p->lines[2]) free(p->lines[2]);
1923       if (p->lengths[0]) free(p->lengths[0]);
1924       if (p->lengths[1]) free(p->lengths[1]);
1925       if (p->lengths[2]) free(p->lengths[2]);
1926       free(p);
1927       p = next;
1928     }
1929 }