1/*-
2 * Copyright (c) 2003-2006, Maxime Henrion <mux@FreeBSD.org>
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 *    notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 *    notice, this list of conditions and the following disclaimer in the
12 *    documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24 * SUCH DAMAGE.
25 *
26 * $FreeBSD$
27 */
28
29#include <sys/limits.h>
30
31#include <assert.h>
32#include <err.h>
33#include <errno.h>
34#include <stdio.h>
35#include <stdlib.h>
36#include <string.h>
37
38#include "diff.h"
39#include "keyword.h"
40#include "misc.h"
41#include "stream.h"
42#include "queue.h"
43
44typedef long lineno_t;
45
46#define	EC_ADD	0
47#define	EC_DEL	1
48#define	MAXKEY	LONG_MAX
49
50/* Editing command and state. */
51struct editcmd {
52	int cmd;
53	long key;
54	int havetext;
55	int offset;
56	lineno_t where;
57	lineno_t count;
58	lineno_t lasta;
59	lineno_t lastd;
60	lineno_t editline;
61	/* For convenience. */
62	struct keyword *keyword;
63	struct diffinfo *di;
64	struct stream *orig;
65	struct stream *dest;
66	LIST_ENTRY(editcmd) next;
67};
68
69struct diffstart {
70	LIST_HEAD(, editcmd) dhead;
71};
72
73static int	diff_geteditcmd(struct editcmd *, char *);
74static int	diff_copyln(struct editcmd *, lineno_t);
75static int	diff_ignoreln(struct editcmd *, lineno_t);
76static void	diff_write(struct editcmd *, void *, size_t);
77static int	diff_insert_edit(struct diffstart *, struct editcmd *);
78static void	diff_free(struct diffstart *);
79
80int
81diff_apply(struct stream *rd, struct stream *orig, struct stream *dest,
82    struct keyword *keyword, struct diffinfo *di, int comode)
83{
84	struct editcmd ec;
85	lineno_t i;
86	size_t size;
87	char *line;
88	int empty, error, noeol;
89
90	memset(&ec, 0, sizeof(ec));
91	empty = 0;
92	noeol = 0;
93	ec.di = di;
94	ec.keyword = keyword;
95	ec.orig = orig;
96	ec.dest = dest;
97	line = stream_getln(rd, NULL);
98	while (line != NULL && strcmp(line, ".") != 0 &&
99	    strcmp(line, ".+") != 0) {
100		/*
101		 * The server sends an empty line and then terminates
102		 * with .+ for forced (and thus empty) commits.
103		 */
104		if (*line == '\0') {
105			if (empty)
106				return (-1);
107			empty = 1;
108			line = stream_getln(rd, NULL);
109			continue;
110		}
111		error = diff_geteditcmd(&ec, line);
112		if (error)
113			return (-1);
114
115		if (ec.cmd == EC_ADD) {
116			error = diff_copyln(&ec, ec.where);
117			if (error)
118				return (-1);
119			for (i = 0; i < ec.count; i++) {
120				line = stream_getln(rd, &size);
121				if (line == NULL)
122					return (-1);
123				if (comode && line[0] == '.') {
124					line++;
125					size--;
126				}
127				diff_write(&ec, line, size);
128			}
129		} else {
130			assert(ec.cmd == EC_DEL);
131			error = diff_copyln(&ec, ec.where - 1);
132			if (error)
133				return (-1);
134			for (i = 0; i < ec.count; i++) {
135				line = stream_getln(orig, NULL);
136				if (line == NULL)
137					return (-1);
138				ec.editline++;
139			}
140		}
141		line = stream_getln(rd, NULL);
142	}
143	if (comode && line == NULL)
144		return (-1);
145	/* If we got ".+", there's no ending newline. */
146	if (comode && strcmp(line, ".+") == 0 && !empty)
147		noeol = 1;
148	ec.where = 0;
149	while ((line = stream_getln(orig, &size)) != NULL)
150		diff_write(&ec, line, size);
151	stream_flush(dest);
152	if (noeol) {
153		error = stream_truncate_rel(dest, -1);
154		if (error) {
155			warn("stream_truncate_rel");
156			return (-1);
157		}
158	}
159	return (0);
160}
161
162/*
163 * Reverse a diff using the same algorithm as in cvsup.
164 */
165static int
166diff_write_reverse(struct stream *dest, struct diffstart *ds)
167{
168	struct editcmd *ec, *nextec;
169	long editline, endline, firstoutputlinedeleted;
170	long num_added, num_deleted, startline;
171	int num;
172
173	nextec = LIST_FIRST(&ds->dhead);
174	editline = 0;
175	num = 0;
176	while (nextec != NULL) {
177		ec = nextec;
178		nextec = LIST_NEXT(nextec, next);
179		if (nextec == NULL)
180			break;
181		num++;
182		num_deleted = 0;
183		if (ec->havetext)
184			num_deleted = ec->count;
185		num_added = num_deleted + nextec->offset - ec->offset;
186		if (num_deleted > 0) {
187			firstoutputlinedeleted = ec->key - num_deleted + 1;
188			stream_printf(dest, "d%ld %ld\n", firstoutputlinedeleted,
189			    num_deleted);
190			if (num_added <= 0)
191				continue;
192		}
193		if (num_added > 0) {
194			stream_printf(dest, "a%ld %ld\n", ec->key, num_added);
195			startline = ec->key - num_deleted + 1 + ec->offset;
196			endline = startline + num_added - 1;
197
198			/* Copy lines from original file. First ignore some. */
199			ec->editline = editline;
200			diff_ignoreln(ec,  startline - 1);
201			diff_copyln(ec, endline);
202			editline = ec->editline;
203		}
204	}
205	return (0);
206}
207
208/*
209 * Insert a diff into the list sorted on key. Should perhaps use quicker
210 * algorithms than insertion sort, but do this for now.
211 */
212static int
213diff_insert_edit(struct diffstart *ds, struct editcmd *ec)
214{
215	struct editcmd *curec;
216
217	if (ec == NULL)
218		return (0);
219
220	if (LIST_EMPTY(&ds->dhead)) {
221		LIST_INSERT_HEAD(&ds->dhead, ec, next);
222		return (0);
223	}
224
225	/* Insertion sort based on key. */
226	LIST_FOREACH(curec, &ds->dhead, next) {
227		if (ec->key < curec->key) {
228			LIST_INSERT_BEFORE(curec, ec, next);
229			return (0);
230		}
231		if (LIST_NEXT(curec, next) == NULL)
232			break;
233	}
234	/* Just insert it after. */
235	LIST_INSERT_AFTER(curec, ec, next);
236	return (0);
237}
238
239static void
240diff_free(struct diffstart *ds)
241{
242	struct editcmd *ec;
243
244	while(!LIST_EMPTY(&ds->dhead)) {
245		ec = LIST_FIRST(&ds->dhead);
246		LIST_REMOVE(ec, next);
247		free(ec);
248	}
249}
250
251/*
252 * Write the reverse diff from the diff in rd, and original file into
253 * destination. This algorithm is the same as used in cvsup.
254 */
255int
256diff_reverse(struct stream *rd, struct stream *orig, struct stream *dest,
257    struct keyword *keyword, struct diffinfo *di)
258{
259	struct diffstart ds;
260	struct editcmd ec, *addec, *delec;
261	lineno_t i;
262	char *line;
263	int error, offset;
264
265	memset(&ec, 0, sizeof(ec));
266	ec.orig = orig;
267	ec.dest = dest;
268	ec.keyword = keyword;
269	ec.di = di;
270	addec = NULL;
271	delec = NULL;
272	ec.havetext = 0;
273	offset = 0;
274	LIST_INIT(&ds.dhead);
275
276	/* Start with next since we need it. */
277	line = stream_getln(rd, NULL);
278	/* First we build up the list of diffs from input. */
279	while (line != NULL) {
280		error = diff_geteditcmd(&ec, line);
281		if (error)
282			break;
283		if (ec.cmd == EC_ADD) {
284			addec = xmalloc(sizeof(struct editcmd));
285			*addec = ec;
286			addec->havetext = 1;
287			/* Ignore the lines we was supposed to add. */
288			for (i = 0; i < ec.count; i++) {
289				line = stream_getln(rd, NULL);
290				if (line == NULL)
291					return (-1);
292			}
293
294			/* Get the next diff command if we have one. */
295			addec->key = addec->where + addec->count - offset;
296			if (delec != NULL &&
297			    delec->key == addec->key - addec->count) {
298				delec->key = addec->key;
299				delec->havetext = addec->havetext;
300				delec->count = addec->count;
301				diff_insert_edit(&ds, delec);
302				free(addec);
303				delec = NULL;
304				addec = NULL;
305			} else {
306				if (delec != NULL) {
307					diff_insert_edit(&ds, delec);
308				}
309				delec = NULL;
310				addec->offset = offset;
311				diff_insert_edit(&ds, addec);
312				addec = NULL;
313			}
314			offset -= ec.count;
315		} else if (ec.cmd == EC_DEL) {
316			if (delec != NULL) {
317				/* Update offset to our next. */
318				diff_insert_edit(&ds, delec);
319				delec = NULL;
320			}
321			delec = xmalloc(sizeof(struct editcmd));
322			*delec = ec;
323			delec->key = delec->where - 1 - offset;
324			delec->offset = offset;
325			delec->count = 0;
326			delec->havetext = 0;
327			/* Important to use the count we had before reset.*/
328			offset += ec.count;
329		}
330		line = stream_getln(rd, NULL);
331	}
332
333	while (line != NULL)
334		line = stream_getln(rd, NULL);
335	if (delec != NULL) {
336		diff_insert_edit(&ds, delec);
337		delec = NULL;
338	}
339
340	addec = xmalloc(sizeof(struct editcmd));
341	/* Should be filesize, but we set it to max value. */
342	addec->key = MAXKEY;
343	addec->offset = offset;
344	addec->havetext = 0;
345	addec->count = 0;
346	diff_insert_edit(&ds, addec);
347	addec = NULL;
348	diff_write_reverse(dest, &ds);
349	diff_free(&ds);
350	stream_flush(dest);
351	return (0);
352}
353
354/* Get an editing command from the diff. */
355static int
356diff_geteditcmd(struct editcmd *ec, char *line)
357{
358	char *end;
359
360	if (line[0] == 'a')
361		ec->cmd = EC_ADD;
362	else if (line[0] == 'd')
363		ec->cmd = EC_DEL;
364	else
365		return (-1);
366	errno = 0;
367	ec->where = strtol(line + 1, &end, 10);
368	if (errno || ec->where < 0 || *end != ' ')
369		return (-1);
370	line = end + 1;
371	errno = 0;
372	ec->count = strtol(line, &end, 10);
373	if (errno || ec->count <= 0 || *end != '\0')
374		return (-1);
375	if (ec->cmd == EC_ADD) {
376		if (ec->where < ec->lasta)
377			return (-1);
378		ec->lasta = ec->where + 1;
379	} else {
380		if (ec->where < ec->lasta || ec->where < ec->lastd)
381			return (-1);
382		ec->lasta = ec->where;
383		ec->lastd = ec->where + ec->count;
384	}
385	return (0);
386}
387
388/* Copy lines from the original version of the file up to line "to". */
389static int
390diff_copyln(struct editcmd *ec, lineno_t to)
391{
392	size_t size;
393	char *line;
394
395	while (ec->editline < to) {
396		line = stream_getln(ec->orig, &size);
397		if (line == NULL)
398			return (-1);
399		ec->editline++;
400		diff_write(ec, line, size);
401	}
402	return (0);
403}
404
405/* Ignore lines from the original version of the file up to line "to". */
406static int
407diff_ignoreln(struct editcmd *ec, lineno_t to)
408{
409	size_t size;
410	char *line;
411
412	while (ec->editline < to) {
413		line = stream_getln(ec->orig, &size);
414		if (line == NULL)
415			return (-1);
416		ec->editline++;
417	}
418	return (0);
419}
420
421/* Write a new line to the file, expanding RCS keywords appropriately. */
422static void
423diff_write(struct editcmd *ec, void *buf, size_t size)
424{
425	size_t newsize;
426	char *line, *newline;
427	int ret;
428
429	line = buf;
430	ret = keyword_expand(ec->keyword, ec->di, line, size,
431	    &newline, &newsize);
432	if (ret) {
433		stream_write(ec->dest, newline, newsize);
434		free(newline);
435	} else {
436		stream_write(ec->dest, buf, size);
437	}
438}
439