op public repos

Blob

Date:: Tue Nov 1 07:41:39 2022 UTC
Message:: use mkstemps(3) instead of mkstemp(3) for opening named temporary files Allows 'got commit' to use a ".diff" suffix for temporary diff files. ok op@
Actions:: History | Blame | Raw File
1 /*	$OpenBSD: diff3.c,v 1.41 2016/10/18 21:06:52 millert Exp $	*/
2 
3 /*
4  * Copyright (C) Caldera International Inc.  2001-2002.
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  * 1. Redistributions of source code and documentation must retain the above
11  *    copyright notice, this list of conditions and the following disclaimer.
12  * 2. Redistributions in binary form must reproduce the above copyright
13  *    notice, this list of conditions and the following disclaimer in the
14  *    documentation and/or other materials provided with the distribution.
15  * 3. All advertising materials mentioning features or use of this software
16  *    must display the following acknowledgement:
17  *	This product includes software developed or owned by Caldera
18  *	International, Inc.
19  * 4. Neither the name of Caldera International, Inc. nor the names of other
20  *    contributors may be used to endorse or promote products derived from
21  *    this software without specific prior written permission.
22  *
23  * USE OF THE SOFTWARE PROVIDED FOR UNDER THIS LICENSE BY CALDERA
24  * INTERNATIONAL, INC. AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR
25  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
26  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
27  * IN NO EVENT SHALL CALDERA INTERNATIONAL, INC. BE LIABLE FOR ANY DIRECT,
28  * INDIRECT INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
29  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
30  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
32  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
33  * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
34  * POSSIBILITY OF SUCH DAMAGE.
35  */
36 /*-
37  * Copyright (c) 1991, 1993
38  *	The Regents of the University of California.  All rights reserved.
39  *
40  * Redistribution and use in source and binary forms, with or without
41  * modification, are permitted provided that the following conditions
42  * are met:
43  * 1. Redistributions of source code must retain the above copyright
44  *    notice, this list of conditions and the following disclaimer.
45  * 2. Redistributions in binary form must reproduce the above copyright
46  *    notice, this list of conditions and the following disclaimer in the
47  *    documentation and/or other materials provided with the distribution.
48  * 3. Neither the name of the University nor the names of its contributors
49  *    may be used to endorse or promote products derived from this software
50  *    without specific prior written permission.
51  *
52  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
53  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
54  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
55  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
56  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
57  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
58  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
59  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
60  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
61  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
62  * SUCH DAMAGE.
63  *
64  *	@(#)diff3.c	8.1 (Berkeley) 6/6/93
65  */
66 
67 #include <sys/stat.h>
68 #include <sys/queue.h>
69 
70 #include <ctype.h>
71 #include <limits.h>
72 #include <sha1.h>
73 #include <stdio.h>
74 #include <stdarg.h>
75 #include <stdlib.h>
76 #include <string.h>
77 #include <time.h>
78 #include <unistd.h>
79 
80 #include "got_error.h"
81 #include "got_opentemp.h"
82 #include "got_object.h"
83 #include "got_diff.h"
84 
85 #include "buf.h"
86 #include "rcsutil.h"
87 #include "got_lib_diff.h"
88 
89 #ifndef nitems
90 #define nitems(_a) (sizeof(_a) / sizeof((_a)[0]))
91 #endif
92 
93 /* diff3 - 3-way differential file comparison */
94 
95 /* diff3 [-ex3EX] d13 d23 f1 f2 f3 [m1 m3]
96  *
97  * d13 = diff report on f1 vs f3
98  * d23 = diff report on f2 vs f3
99  * f1, f2, f3 the 3 files
100  * if changes in f1 overlap with changes in f3, m1 and m3 are used
101  * to mark the overlaps; otherwise, the file names f1 and f3 are used
102  * (only for options E and X).
103  */
104 
105 /*
106  * "from" is first in range of changed lines; "to" is last+1
107  * from=to=line after point of insertion for added lines.
108  */
109 struct line_range {
110 	int from;
111 	int to;
112 };
113 
114 struct off_range {
115 	off_t from;
116 	off_t to;
117 };
118 
119 struct diff {
120 	struct line_range old;
121 	struct line_range new;
122 	struct off_range oldo;
123 	struct off_range newo;
124 };
125 
126 struct diff3_state {
127 	size_t szchanges;
128 
129 	struct diff *d13;
130 	struct diff *d23;
131 
132 	/*
133 	 * "de" is used to gather editing scripts.  These are later spewed out
134 	 * in reverse order.  Its first element must be all zero, the "new"
135 	 * component of "de" contains line positions, and "oldo" and "newo"
136 	 * components contain byte positions.
137 	 * Array overlap indicates which sections in "de" correspond to lines
138 	 * that are different in all three files.
139 	 */
140 	struct diff *de;
141 	char *overlap;
142 	int overlapcnt;
143 	FILE *fp[3];
144 	int cline[3];		/* # of the last-read line in each file (0-2) */
145 
146 	/*
147 	 * the latest known correspondence between line numbers of the 3 files
148 	 * is stored in last[1-3];
149 	 */
150 	int last[4];
151 	char f1mark[PATH_MAX];
152 	char f2mark[PATH_MAX];
153 	char f3mark[PATH_MAX];
154 
155 	char *buf;
156 
157 	BUF *diffbuf;
158 };
159 
160 
161 static const struct got_error *duplicate(int *, int, struct line_range *,
162     struct line_range *, struct diff3_state *);
163 static const struct got_error *edit(struct diff *, int, int *,
164     struct diff3_state *);
165 static const struct got_error *getchange(char **, FILE *, struct diff3_state *);
166 static const struct got_error *get_line(char **, FILE *, size_t *,
167     struct diff3_state *);
168 static int number(char **);
169 static const struct got_error *readin(size_t *, char *, struct diff **,
170     struct diff3_state *);
171 static int ed_patch_lines(struct rcs_lines *, struct rcs_lines *);
172 static const struct got_error *skip(size_t *, int, int, struct diff3_state *);
173 static const struct got_error *edscript(int, struct diff3_state *);
174 static const struct got_error *merge(size_t, size_t, struct diff3_state *);
175 static const struct got_error *prange(struct line_range *,
176     struct diff3_state *);
177 static const struct got_error *repos(int, struct diff3_state *);
178 static const struct got_error *increase(struct diff3_state *);
179 static const struct got_error *diff3_internal(char *, char *, char *,
180     char *, char *, const char *, const char *, struct diff3_state *,
181     const char *, const char *, const char *);
182 
183 static const struct got_error *
184 diff_output(BUF *diffbuf, const char *fmt, ...)
185 {
186 	const struct got_error *err = NULL;
187 	va_list vap;
188 	int i;
189 	char *str;
190 	size_t newsize;
191 
192 	va_start(vap, fmt);
193 	i = vasprintf(&str, fmt, vap);
194 	va_end(vap);
195 	if (i == -1)
196 		return got_error_from_errno("vasprintf");
197 	err = buf_append(&newsize, diffbuf, str, strlen(str));
198 	free(str);
199 	return err;
200 }
201 
202 static const struct got_error*
203 diffreg(BUF **d, const char *path1, const char *path2,
204     enum got_diff_algorithm diff_algo)
205 {
206 	const struct got_error *err = NULL;
207 	FILE *f1 = NULL, *f2 = NULL, *outfile = NULL;
208 	char *outpath = NULL;
209 	struct got_diffreg_result *diffreg_result = NULL;
210 
211 	*d = NULL;
212 
213 	f1 = fopen(path1, "re");
214 	if (f1 == NULL) {
215 		err = got_error_from_errno2("fopen", path1);
216 		goto done;
217 	}
218 	f2 = fopen(path2, "re");
219 	if (f1 == NULL) {
220 		err = got_error_from_errno2("fopen", path2);
221 		goto done;
222 	}
223 
224 	err = got_opentemp_named(&outpath, &outfile,
225 	    GOT_TMPDIR_STR "/got-diffreg", "");
226 	if (err)
227 		goto done;
228 
229 	err = got_diffreg(&diffreg_result, f1, f2, diff_algo, 0, 0);
230 	if (err)
231 		goto done;
232 
233 	if (diffreg_result) {
234 		struct diff_result *diff_result = diffreg_result->result;
235 		int atomizer_flags = (diff_result->left->atomizer_flags |
236 		    diff_result->right->atomizer_flags);
237 		if ((atomizer_flags & DIFF_ATOMIZER_FOUND_BINARY_DATA)) {
238 			err = got_error(GOT_ERR_FILE_BINARY);
239 			goto done;
240 		}
241 	}
242 
243 	err = got_diffreg_output(NULL, NULL, diffreg_result, 1, 1, "", "",
244 	    GOT_DIFF_OUTPUT_PLAIN, 0, outfile);
245 	if (err)
246 		goto done;
247 
248 	if (fflush(outfile) != 0) {
249 		err = got_error_from_errno2("fflush", outpath);
250 		goto done;
251 	}
252 	if (fseek(outfile, 0L, SEEK_SET) == -1) {
253 		err = got_ferror(outfile, GOT_ERR_IO);
254 		goto done;
255 	}
256 
257 	err = buf_load(d, outfile);
258 done:
259 	if (outpath) {
260 		if (unlink(outpath) == -1 && err == NULL)
261 			err = got_error_from_errno2("unlink", outpath);
262 		free(outpath);
263 	}
264 	if (outfile && fclose(outfile) == EOF && err == NULL)
265 		err = got_error_from_errno("fclose");
266 	if (f1 && fclose(f1) == EOF && err == NULL)
267 		err = got_error_from_errno("fclose");
268 	if (f2 && fclose(f2) == EOF && err == NULL)
269 		err = got_error_from_errno("fclose");
270 	return err;
271 }
272 
273 /*
274  * For merge(1).
275  */
276 const struct got_error *
277 got_merge_diff3(int *overlapcnt, int outfd, FILE *f1, FILE *f2,
278     FILE *f3, const char *label1, const char *label2, const char *label3,
279     enum got_diff_algorithm diff_algo)
280 {
281 	const struct got_error *err = NULL;
282 	char *dp13, *dp23, *path1, *path2, *path3;
283 	BUF *b1, *b2, *b3, *d1, *d2, *diffb;
284 	u_char *data, *patch;
285 	size_t dlen, plen, i;
286 	struct diff3_state *d3s;
287 
288 	*overlapcnt = 0;
289 
290 	d3s = calloc(1, sizeof(*d3s));
291 	if (d3s == NULL)
292 		return got_error_from_errno("calloc");
293 
294 	b1 = b2 = b3 = d1 = d2 = diffb = NULL;
295 	dp13 = dp23 = path1 = path2 = path3 = NULL;
296 	data = patch = NULL;
297 
298 	err = buf_load(&b1, f1);
299 	if (err)
300 		goto out;
301 	err = buf_load(&b2, f2);
302 	if (err)
303 		goto out;
304 	err = buf_load(&b3, f3);
305 	if (err)
306 		goto out;
307 
308 	err = buf_alloc(&diffb, 128);
309 	if (err)
310 		goto out;
311 
312 	if (asprintf(&path1, GOT_TMPDIR_STR "/got-diff1.XXXXXXXX") == -1) {
313 		err = got_error_from_errno("asprintf");
314 		goto out;
315 	}
316 	if (asprintf(&path2, GOT_TMPDIR_STR "/got-diff2.XXXXXXXX") == -1) {
317 		err = got_error_from_errno("asprintf");
318 		goto out;
319 	}
320 	if (asprintf(&path3, GOT_TMPDIR_STR "/got-diff3.XXXXXXXX") == -1) {
321 		err = got_error_from_errno("asprintf");
322 		goto out;
323 	}
324 
325 	err = buf_write_stmp(b1, path1);
326 	if (err)
327 		goto out;
328 	err = buf_write_stmp(b2, path2);
329 	if (err)
330 		goto out;
331 	err = buf_write_stmp(b3, path3);
332 	if (err)
333 		goto out;
334 
335 	buf_free(b2);
336 	b2 = NULL;
337 
338 	err = diffreg(&d1, path1, path3, diff_algo);
339 	if (err) {
340 		buf_free(diffb);
341 		diffb = NULL;
342 		goto out;
343 
344 	}
345 	err = diffreg(&d2, path2, path3, diff_algo);
346 	if (err) {
347 		buf_free(diffb);
348 		diffb = NULL;
349 		goto out;
350 	}
351 
352 	if (asprintf(&dp13, GOT_TMPDIR_STR "/got-d13.XXXXXXXXXX") == -1) {
353 		err = got_error_from_errno("asprintf");
354 		goto out;
355 	}
356 	err = buf_write_stmp(d1, dp13);
357 	if (err)
358 		goto out;
359 
360 	buf_free(d1);
361 	d1 = NULL;
362 
363 	if (asprintf(&dp23, GOT_TMPDIR_STR "/got-d23.XXXXXXXXXX") == -1) {
364 		err = got_error_from_errno("asprintf");
365 		goto out;
366 	}
367 	err = buf_write_stmp(d2, dp23);
368 	if (err)
369 		goto out;
370 
371 	buf_free(d2);
372 	d2 = NULL;
373 
374 	d3s->diffbuf = diffb;
375 	err = diff3_internal(dp13, dp23, path1, path2, path3,
376 	    label1, label3, d3s, label1, label2, label3);
377 	if (err) {
378 		buf_free(diffb);
379 		diffb = NULL;
380 		goto out;
381 	}
382 
383 	plen = buf_len(diffb);
384 	patch = buf_release(diffb);
385 	dlen = buf_len(b1);
386 	data = buf_release(b1);
387 
388 	diffb = rcs_patchfile(data, dlen, patch, plen, ed_patch_lines);
389 out:
390 	buf_free(b2);
391 	buf_free(b3);
392 	buf_free(d1);
393 	buf_free(d2);
394 
395 	if (unlink(path1) == -1 && err == NULL)
396 		err = got_error_from_errno2("unlink", path1);
397 	if (unlink(path2) == -1 && err == NULL)
398 		err = got_error_from_errno2("unlink", path2);
399 	if (unlink(path3) == -1 && err == NULL)
400 		err = got_error_from_errno2("unlink", path3);
401 	if (unlink(dp13) == -1 && err == NULL)
402 		err = got_error_from_errno2("unlink", dp13);
403 	if (unlink(dp23) == -1 && err == NULL)
404 		err = got_error_from_errno2("unlink", dp23);
405 
406 	free(path1);
407 	free(path2);
408 	free(path3);
409 	free(dp13);
410 	free(dp23);
411 	free(data);
412 	free(patch);
413 
414 	for (i = 0; i < nitems(d3s->fp); i++) {
415 		if (d3s->fp[i] && fclose(d3s->fp[i]) == EOF && err == NULL)
416 			err = got_error_from_errno("fclose");
417 	}
418 	if (err == NULL && diffb) {
419 		if (buf_write_fd(diffb, outfd) < 0)
420 			err = got_error_from_errno("buf_write_fd");
421 		*overlapcnt = d3s->overlapcnt;
422 	}
423 	free(d3s);
424 	buf_free(diffb);
425 	return err;
426 }
427 
428 static const struct got_error *
429 diff3_internal(char *dp13, char *dp23, char *path1, char *path2, char *path3,
430     const char *fmark, const char *rmark, struct diff3_state *d3s,
431     const char *label1, const char *label2, const char *label3)
432 {
433 	const struct got_error *err = NULL;
434 	ssize_t m, n;
435 	int i;
436 
437 	i = snprintf(d3s->f1mark, sizeof(d3s->f1mark),
438 	    "%s%s%s", GOT_DIFF_CONFLICT_MARKER_BEGIN,
439 	    label1 ? " " : "", label1 ? label1 : "");
440 	if (i < 0 || i >= (int)sizeof(d3s->f1mark))
441 		return got_error(GOT_ERR_NO_SPACE);
442 
443 	i = snprintf(d3s->f2mark, sizeof(d3s->f2mark),
444 	    "%s%s%s", GOT_DIFF_CONFLICT_MARKER_ORIG,
445 	    label2 ? " " : "", label2 ? label2 : "");
446 	if (i < 0 || i >= (int)sizeof(d3s->f2mark))
447 		return got_error(GOT_ERR_NO_SPACE);
448 
449 	i = snprintf(d3s->f3mark, sizeof(d3s->f3mark),
450 	    "%s%s%s", GOT_DIFF_CONFLICT_MARKER_END,
451 	    label3 ? " " : "", label3 ? label3 : "");
452 	if (i < 0 || i >= (int)sizeof(d3s->f3mark))
453 		return got_error(GOT_ERR_NO_SPACE);
454 
455 	err = increase(d3s);
456 	if (err)
457 		return err;
458 
459 	err = readin(&m, dp13, &d3s->d13, d3s);
460 	if (err)
461 		return err;
462 	err = readin(&n, dp23, &d3s->d23, d3s);
463 	if (err)
464 		return err;
465 
466 	if ((d3s->fp[0] = fopen(path1, "re")) == NULL)
467 		return got_error_from_errno2("fopen", path1);
468 	if ((d3s->fp[1] = fopen(path2, "re")) == NULL)
469 		return got_error_from_errno2("fopen", path2);
470 	if ((d3s->fp[2] = fopen(path3, "re")) == NULL)
471 		return got_error_from_errno2("fopen", path3);
472 
473 	return merge(m, n, d3s);
474 }
475 
476 static int
477 ed_patch_lines(struct rcs_lines *dlines, struct rcs_lines *plines)
478 {
479 	char op, *ep;
480 	struct rcs_line *sort, *lp, *dlp, *ndlp, *insert_after;
481 	int start, end, i, lineno;
482 	u_char tmp;
483 
484 	dlp = TAILQ_FIRST(&(dlines->l_lines));
485 	lp = TAILQ_FIRST(&(plines->l_lines));
486 
487 	end = 0;
488 	for (lp = TAILQ_NEXT(lp, l_list); lp != NULL;
489 	    lp = TAILQ_NEXT(lp, l_list)) {
490 		/* Skip blank lines */
491 		if (lp->l_len < 2)
492 			continue;
493 
494 		/* NUL-terminate line buffer for strtol() safety. */
495 		tmp = lp->l_line[lp->l_len - 1];
496 		lp->l_line[lp->l_len - 1] = '\0';
497 
498 		/* len - 1 is NUL terminator so we use len - 2 for 'op' */
499 		op = lp->l_line[lp->l_len - 2];
500 		start = (int)strtol(lp->l_line, &ep, 10);
501 
502 		/* Restore the last byte of the buffer */
503 		lp->l_line[lp->l_len - 1] = tmp;
504 
505 		if (op == 'a') {
506 			if (start > dlines->l_nblines ||
507 			    start < 0 || *ep != 'a')
508 				return -1;
509 		} else if (op == 'c') {
510 			if (start > dlines->l_nblines ||
511 			    start < 0 || (*ep != ',' && *ep != 'c'))
512 				return -1;
513 
514 			if (*ep == ',') {
515 				ep++;
516 				end = (int)strtol(ep, &ep, 10);
517 				if (end < 0 || *ep != 'c')
518 					return -1;
519 			} else {
520 				end = start;
521 			}
522 		}
523 
524 
525 		for (;;) {
526 			if (dlp == NULL)
527 				break;
528 			if (dlp->l_lineno == start)
529 				break;
530 			if (dlp->l_lineno > start) {
531 				dlp = TAILQ_PREV(dlp, tqh, l_list);
532 			} else if (dlp->l_lineno < start) {
533 				ndlp = TAILQ_NEXT(dlp, l_list);
534 				if (ndlp->l_lineno > start)
535 					break;
536 				dlp = ndlp;
537 			}
538 		}
539 
540 		if (dlp == NULL)
541 			return -1;
542 
543 
544 		if (op == 'c') {
545 			insert_after = TAILQ_PREV(dlp, tqh, l_list);
546 			for (i = 0; i <= (end - start); i++) {
547 				ndlp = TAILQ_NEXT(dlp, l_list);
548 				TAILQ_REMOVE(&(dlines->l_lines), dlp, l_list);
549 				dlp = ndlp;
550 			}
551 			dlp = insert_after;
552 		}
553 
554 		if (op == 'a' || op == 'c') {
555 			for (;;) {
556 				ndlp = lp;
557 				lp = TAILQ_NEXT(lp, l_list);
558 				if (lp == NULL)
559 					return -1;
560 
561 				if (lp->l_len == 2 &&
562 				    lp->l_line[0] == '.' &&
563 				    lp->l_line[1] == '\n')
564 					break;
565 
566 				if (lp->l_line[0] == ':') {
567 					lp->l_line++;
568 					lp->l_len--;
569 				}
570 				TAILQ_REMOVE(&(plines->l_lines), lp, l_list);
571 				TAILQ_INSERT_AFTER(&(dlines->l_lines), dlp,
572 				    lp, l_list);
573 				dlp = lp;
574 
575 				lp->l_lineno = start;
576 				lp = ndlp;
577 			}
578 		}
579 
580 		/*
581 		 * always resort lines as the markers might be put at the
582 		 * same line as we first started editing.
583 		 */
584 		lineno = 0;
585 		TAILQ_FOREACH(sort, &(dlines->l_lines), l_list)
586 			sort->l_lineno = lineno++;
587 		dlines->l_nblines = lineno - 1;
588 	}
589 
590 	return (0);
591 }
592 
593 /*
594  * Pick up the line numbers of all changes from one change file.
595  * (This puts the numbers in a vector, which is not strictly necessary,
596  * since the vector is processed in one sequential pass.
597  * The vector could be optimized out of existence)
598  */
599 static const struct got_error *
600 readin(size_t *n, char *name, struct diff **dd, struct diff3_state *d3s)
601 {
602 	const struct got_error *err = NULL;
603 	FILE *f;
604 	int a, b, c, d;
605 	char kind, *p;
606 	size_t i = 0;
607 
608 	*n = 0;
609 
610 	f = fopen(name, "re");
611 	if (f == NULL)
612 		return got_error_from_errno2("fopen", name);
613 	err = getchange(&p, f, d3s);
614 	if (err)
615 		goto done;
616 	for (i = 0; p; i++) {
617 		if (i >= d3s->szchanges - 1) {
618 			err = increase(d3s);
619 			if (err)
620 				goto done;
621 		}
622 		a = b = number(&p);
623 		if (*p == ',') {
624 			p++;
625 			b = number(&p);
626 		}
627 		kind = *p++;
628 		c = d = number(&p);
629 		if (*p == ',') {
630 			p++;
631 			d = number(&p);
632 		}
633 		if (kind == 'a')
634 			a++;
635 		if (kind == 'd')
636 			c++;
637 		b++;
638 		d++;
639 		(*dd)[i].old.from = a;
640 		(*dd)[i].old.to = b;
641 		(*dd)[i].new.from = c;
642 		(*dd)[i].new.to = d;
643 
644 		err = getchange(&p, f, d3s);
645 		if (err)
646 			goto done;
647 	}
648 
649 	if (i) {
650 		(*dd)[i].old.from = (*dd)[i - 1].old.to;
651 		(*dd)[i].new.from = (*dd)[i - 1].new.to;
652 	}
653 done:
654 	if (fclose(f) == EOF && err == NULL)
655 		err = got_error_from_errno("fclose");
656 	if (err == NULL)
657 		*n = i;
658 	return err;
659 }
660 
661 static int
662 number(char **lc)
663 {
664 	int nn;
665 
666 	nn = 0;
667 	while (isdigit((unsigned char)(**lc)))
668 		nn = nn*10 + *(*lc)++ - '0';
669 
670 	return (nn);
671 }
672 
673 static const struct got_error *
674 getchange(char **line, FILE *b, struct diff3_state *d3s)
675 {
676 	const struct got_error *err = NULL;
677 
678 	*line = NULL;
679 	do {
680 		if (*line && isdigit((unsigned char)(*line)[0]))
681 			return NULL;
682 		err = get_line(line, b, NULL, d3s);
683 		if (err)
684 			return err;
685 	} while (*line);
686 
687 	return NULL;
688 }
689 
690 static const struct got_error *
691 get_line(char **ret, FILE *b, size_t *n, struct diff3_state *d3s)
692 {
693 	const struct got_error *err = NULL;
694 	char *cp = NULL;
695 	size_t size;
696 	ssize_t len;
697 	char *new;
698 
699 	*ret = NULL;
700 	if (n != NULL)
701 		*n = 0;
702 
703 	len = getline(&cp, &size, b);
704 	if (len == -1) {
705 		if (ferror(b))
706 			err = got_error_from_errno("getline");
707 		goto done;
708 	}
709 
710 	if (cp[len - 1] != '\n') {
711 		len++;
712 		if (len + 1 > size) {
713 			new = realloc(cp, len + 1);
714 			if (new == NULL) {
715 				err = got_error_from_errno("realloc");
716 				goto done;
717 			}
718 			cp = new;
719 		}
720 		cp[len - 1] = '\n';
721 		cp[len] = '\0';
722 	}
723 
724 	free(d3s->buf);
725 	*ret = d3s->buf = cp;
726 	cp = NULL;
727 	if (n != NULL)
728 		*n = len;
729 done:
730 	free(cp);
731 	return err;
732 }
733 
734 static const struct got_error *
735 merge(size_t m1, size_t m2, struct diff3_state *d3s)
736 {
737 	const struct got_error *err = NULL;
738 	struct diff *d1, *d2;
739 	int dpl, j, t1, t2;
740 
741 	d1 = d3s->d13;
742 	d2 = d3s->d23;
743 	j = 0;
744 	for (;;) {
745 		t1 = (d1 < d3s->d13 + m1);
746 		t2 = (d2 < d3s->d23 + m2);
747 		if (!t1 && !t2)
748 			break;
749 
750 		/* first file is different from others */
751 		if (!t2 || (t1 && d1->new.to < d2->new.from)) {
752 			/* stuff peculiar to 1st file */
753 			d1++;
754 			continue;
755 		}
756 
757 		/* second file is different from others */
758 		if (!t1 || (t2 && d2->new.to < d1->new.from)) {
759 			d2++;
760 			continue;
761 		}
762 
763 		/*
764 		 * Merge overlapping changes in first file
765 		 * this happens after extension (see below).
766 		 */
767 		if (d1 + 1 < d3s->d13 + m1 && d1->new.to >= d1[1].new.from) {
768 			d1[1].old.from = d1->old.from;
769 			d1[1].new.from = d1->new.from;
770 			d1++;
771 			continue;
772 		}
773 
774 		/* merge overlapping changes in second */
775 		if (d2 + 1 < d3s->d23 + m2 && d2->new.to >= d2[1].new.from) {
776 			d2[1].old.from = d2->old.from;
777 			d2[1].new.from = d2->new.from;
778 			d2++;
779 			continue;
780 		}
781 		/* stuff peculiar to third file or different in all */
782 		if (d1->new.from == d2->new.from && d1->new.to == d2->new.to) {
783 			err = duplicate(&dpl, j, &d1->old, &d2->old, d3s);
784 			if (err)
785 				return err;
786 
787 			/*
788 			 * dpl = 0 means all files differ
789 			 * dpl = 1 means files 1 and 2 identical
790 			 */
791 			err = edit(d1, dpl, &j, d3s);
792 			if (err)
793 				return err;
794 			d1++;
795 			d2++;
796 			continue;
797 		}
798 
799 		/*
800 		 * Overlapping changes from file 1 and 2; extend changes
801 		 * appropriately to make them coincide.
802 		 */
803 		if (d1->new.from < d2->new.from) {
804 			d2->old.from -= d2->new.from - d1->new.from;
805 			d2->new.from = d1->new.from;
806 		} else if (d2->new.from < d1->new.from) {
807 			d1->old.from -= d1->new.from - d2->new.from;
808 			d1->new.from = d2->new.from;
809 		}
810 		if (d1->new.to > d2->new.to) {
811 			d2->old.to += d1->new.to - d2->new.to;
812 			d2->new.to = d1->new.to;
813 		} else if (d2->new.to > d1->new.to) {
814 			d1->old.to += d2->new.to - d1->new.to;
815 			d1->new.to = d2->new.to;
816 		}
817 	}
818 
819 	return (edscript(j, d3s));
820 }
821 
822 /*
823  * print the range of line numbers, rold.from thru rold.to, as n1,n2 or n1
824  */
825 static const struct got_error *
826 prange(struct line_range *rold, struct diff3_state *d3s)
827 {
828 	const struct got_error *err = NULL;
829 
830 	if (rold->to <= rold->from) {
831 		err = diff_output(d3s->diffbuf, "%da\n", rold->from - 1);
832 		if (err)
833 			return err;
834 	} else {
835 		err = diff_output(d3s->diffbuf, "%d", rold->from);
836 		if (err)
837 			return err;
838 		if (rold->to > rold->from + 1) {
839 			err = diff_output(d3s->diffbuf, ",%d", rold->to - 1);
840 			if (err)
841 				return err;
842 		}
843 		err = diff_output(d3s->diffbuf, "c\n");
844 		if (err)
845 			return err;
846 	}
847 
848 	return NULL;
849 }
850 
851 /*
852  * Skip to just before line number from in file "i".
853  * Return the number of bytes skipped in *nskipped.
854  */
855 static const struct got_error *
856 skip(size_t *nskipped, int i, int from, struct diff3_state *d3s)
857 {
858 	const struct got_error *err = NULL;
859 	size_t len, n;
860 	char *line;
861 
862 	*nskipped = 0;
863 	for (n = 0; d3s->cline[i] < from - 1; n += len) {
864 		err = get_line(&line, d3s->fp[i], &len, d3s);
865 		if (err)
866 			return err;
867 		d3s->cline[i]++;
868 	}
869 	*nskipped = n;
870 	return NULL;
871 }
872 
873 /*
874  * Set *dpl to 1 or 0 according as the old range (in file 1) contains exactly
875  * the same data as the new range (in file 2).
876  *
877  * If this change could overlap, remember start/end offsets in file 2 so we
878  * can write out the original lines of text if a merge conflict occurs.
879  */
880 static const struct got_error *
881 duplicate(int *dpl, int j, struct line_range *r1, struct line_range *r2,
882     struct diff3_state *d3s)
883 {
884 	const struct got_error *err = NULL;
885 	int c,d;
886 	int nchar;
887 	int nline;
888 	size_t nskipped;
889 	off_t off;
890 
891 	*dpl = 0;
892 
893 	if (r1->to - r1->from != r2->to - r2->from)
894 		return NULL;
895 
896 	err = skip(&nskipped, 0, r1->from, d3s);
897 	if (err)
898 		return err;
899 	err = skip(&nskipped, 1, r2->from, d3s);
900 	if (err)
901 		return err;
902 
903 	off = ftello(d3s->fp[1]);
904 	if (off == -1)
905 		return got_error_from_errno("ftello");
906 	d3s->de[j + 1].oldo.from = off; /* original lines start here */
907 
908 	nchar = 0;
909 	for (nline = 0; nline < r1->to - r1->from; nline++) {
910 		do {
911 			c = getc(d3s->fp[0]);
912 			d = getc(d3s->fp[1]);
913 			if (c == EOF && d == EOF)
914 				break;
915 			else if (c == EOF)
916 				return got_ferror(d3s->fp[0], GOT_ERR_EOF);
917 			else if (d == EOF)
918 				return got_ferror(d3s->fp[1], GOT_ERR_EOF);
919 			nchar++;
920 			if (c != d) {
921 				long orig_line_len = nchar;
922 				while (d != '\n') {
923 					d = getc(d3s->fp[1]);
924 					if (d == EOF)
925 						break;
926 					orig_line_len++;
927 				}
928 				if (orig_line_len > nchar &&
929 				    fseek(d3s->fp[1], -(orig_line_len - nchar),
930 				    SEEK_CUR) == -1)
931 					return got_ferror(d3s->fp[1],
932 						GOT_ERR_IO);
933 				/* original lines end here */
934 				d3s->de[j + 1].oldo.to = off + orig_line_len;
935 				err = repos(nchar, d3s);
936 				if (err)
937 					return err;
938 				return NULL;
939 			}
940 		} while (c != '\n');
941 	}
942 
943 	/* original lines end here */
944 	d3s->de[j + 1].oldo.to = off + nchar;
945 
946 	err = repos(nchar, d3s);
947 	if (err)
948 		return err;
949 	*dpl = 1;
950 	return NULL;
951 }
952 
953 static const struct got_error *
954 repos(int nchar, struct diff3_state *d3s)
955 {
956 	int i;
957 
958 	for (i = 0; i < 2; i++) {
959 		if (fseek(d3s->fp[i], (long)-nchar, SEEK_CUR) == -1)
960 			return got_ferror(d3s->fp[i], GOT_ERR_IO);
961 	}
962 
963 	return NULL;
964 }
965 
966 /*
967  * collect an editing script for later regurgitation
968  */
969 static const struct got_error *
970 edit(struct diff *diff, int fdup, int *j, struct diff3_state *d3s)
971 {
972 	const struct got_error *err = NULL;
973 	size_t nskipped;
974 
975 	if (((fdup + 1) & 3) == 0)
976 		return NULL;
977 	(*j)++;
978 	d3s->overlap[*j] = !fdup;
979 	if (!fdup)
980 		d3s->overlapcnt++;
981 	d3s->de[*j].old.from = diff->old.from;
982 	d3s->de[*j].old.to = diff->old.to;
983 
984 	err = skip(&nskipped, 2, diff->new.from, d3s);
985 	if (err)
986 		return err;
987 	d3s->de[*j].newo.from = d3s->de[*j - 1].newo.to + nskipped;
988 
989 	err = skip(&nskipped, 2, diff->new.to, d3s);
990 	if (err)
991 		return err;
992 	d3s->de[*j].newo.to = d3s->de[*j].newo.from + nskipped;
993 	return NULL;
994 }
995 
996 /* regurgitate */
997 static const struct got_error *
998 edscript(int n, struct diff3_state *d3s)
999 {
1000 	const struct got_error *err = NULL;
1001 	off_t len;
1002 	char *line = NULL;
1003 	size_t linesize = 0;
1004 	ssize_t linelen = 0, k;
1005 
1006 	for (; n > 0; n--) {
1007 		if (!d3s->overlap[n]) {
1008 			err = prange(&d3s->de[n].old, d3s);
1009 			if (err)
1010 				return err;
1011 		} else if (d3s->de[n].oldo.from < d3s->de[n].oldo.to) {
1012 			/* Output a block of 3-way diff base file content. */
1013 			err = diff_output(d3s->diffbuf, "%da\n:%s\n",
1014 			    d3s->de[n].old.to - 1, d3s->f2mark);
1015 			if (err)
1016 				return err;
1017 			if (fseeko(d3s->fp[1], d3s->de[n].oldo.from, SEEK_SET)
1018 			    == -1)
1019 				return got_error_from_errno("fseeko");
1020 			len = (d3s->de[n].oldo.to - d3s->de[n].oldo.from);
1021 			for (k = 0; k < (ssize_t)len; k += linelen) {
1022 				linelen = getline(&line, &linesize, d3s->fp[1]);
1023 				if (linelen == -1) {
1024 					if (feof(d3s->fp[1]))
1025 						break;
1026 					err = got_ferror(d3s->fp[1],
1027 					    GOT_ERR_IO);
1028 					goto done;
1029 				}
1030 				err = diff_output(d3s->diffbuf, ":%s", line);
1031 				if (err)
1032 					goto done;
1033 			}
1034 			err = diff_output(d3s->diffbuf, "%s%s\n",
1035 			    linelen > 0 && line[linelen] == '\n' ? ":" : "",
1036 			    GOT_DIFF_CONFLICT_MARKER_SEP);
1037 			if (err)
1038 				goto done;
1039 		} else {
1040 			err = diff_output(d3s->diffbuf, "%da\n:%s\n",
1041 			    d3s->de[n].old.to -1, GOT_DIFF_CONFLICT_MARKER_SEP);
1042 			if (err)
1043 				goto done;
1044 		}
1045 		if (fseeko(d3s->fp[2], d3s->de[n].newo.from, SEEK_SET)
1046 		    == -1) {
1047 			err = got_error_from_errno("fseek");
1048 			goto done;
1049 		}
1050 		len = (d3s->de[n].newo.to - d3s->de[n].newo.from);
1051 		for (k = 0; k < (ssize_t)len; k += linelen) {
1052 			linelen = getline(&line, &linesize, d3s->fp[2]);
1053 			if (linelen == -1) {
1054 				if (feof(d3s->fp[2]))
1055 					break;
1056 				err = got_ferror(d3s->fp[2], GOT_ERR_IO);
1057 				goto done;
1058 			}
1059 			err = diff_output(d3s->diffbuf, ":%s", line);
1060 			if (err)
1061 				goto done;
1062 		}
1063 
1064 		if (!d3s->overlap[n]) {
1065 			err = diff_output(d3s->diffbuf, ".\n");
1066 			if (err)
1067 				goto done;
1068 		} else {
1069 			err = diff_output(d3s->diffbuf, "%s%s\n.\n",
1070 			    linelen > 0 && line[linelen] == '\n' ? ":" : "",
1071 			    d3s->f3mark);
1072 			if (err)
1073 				goto done;
1074 			err = diff_output(d3s->diffbuf, "%da\n:%s\n.\n",
1075 			    d3s->de[n].old.from - 1, d3s->f1mark);
1076 			if (err)
1077 				goto done;
1078 		}
1079 	}
1080 done:
1081 	free(line);
1082 	return err;
1083 }
1084 
1085 static const struct got_error *
1086 increase(struct diff3_state *d3s)
1087 {
1088 	size_t newsz, incr;
1089 	struct diff *d;
1090 	char *s;
1091 
1092 	/* are the memset(3) calls needed? */
1093 	newsz = d3s->szchanges == 0 ? 64 : 2 * d3s->szchanges;
1094 	incr = newsz - d3s->szchanges;
1095 
1096 	d = reallocarray(d3s->d13, newsz, sizeof(*d3s->d13));
1097 	if (d == NULL)
1098 		return got_error_from_errno("reallocarray");
1099 	d3s->d13 = d;
1100 	memset(d3s->d13 + d3s->szchanges, 0, incr * sizeof(*d3s->d13));
1101 
1102 	d = reallocarray(d3s->d23, newsz, sizeof(*d3s->d23));
1103 	if (d == NULL)
1104 		return got_error_from_errno("reallocarray");
1105 	d3s->d23 = d;
1106 	memset(d3s->d23 + d3s->szchanges, 0, incr * sizeof(*d3s->d23));
1107 
1108 	d = reallocarray(d3s->de, newsz, sizeof(*d3s->de));
1109 	if (d == NULL)
1110 		return got_error_from_errno("reallocarray");
1111 	d3s->de = d;
1112 	memset(d3s->de + d3s->szchanges, 0, incr * sizeof(*d3s->de));
1113 
1114 	s = reallocarray(d3s->overlap, newsz, sizeof(*d3s->overlap));
1115 	if (s == NULL)
1116 		return got_error_from_errno("reallocarray");
1117 	d3s->overlap = s;
1118 	memset(d3s->overlap + d3s->szchanges, 0, incr * sizeof(*d3s->overlap));
1119 	d3s->szchanges = newsz;
1120 
1121 	return NULL;
1122 }