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