- Import csup work from p4.

1 files changed, 241 insertions, 2 deletions

diff --git a/contrib/csup/diff.c b/contrib/csup/diff.c
index ea53c36..f4d73fa 100644
--- a/contrib/csup/diff.c
+++ b/contrib/csup/diff.c
@@ -26,25 +26,33 @@
  * $FreeBSD$
  */
 
+#include <sys/limits.h>
+
 #include <assert.h>
 #include <err.h>
 #include <errno.h>
 #include <stdlib.h>
 #include <string.h>
+#include <stdio.h>
 
 #include "diff.h"
 #include "keyword.h"
 #include "misc.h"
 #include "stream.h"
+#include "queue.h"
 
 typedef long lineno_t;
 
 #define	EC_ADD	0
 #define	EC_DEL	1
+#define MAXKEY LONG_MAX
 
 /* Editing command and state. */
 struct editcmd {
 	int cmd;
+	long key;
+	int havetext;
+	int offset;
 	lineno_t where;
 	lineno_t count;
 	lineno_t lasta;
@@ -55,15 +63,23 @@ struct editcmd {
 	struct diffinfo *di;
 	struct stream *orig;
 	struct stream *dest;
+	LIST_ENTRY(editcmd) next;
+};
+
+struct diffstart {
+	LIST_HEAD(, editcmd) dhead;
 };
 
 static int	diff_geteditcmd(struct editcmd *, char *);
 static int	diff_copyln(struct editcmd *, lineno_t);
+static int	diff_ignoreln(struct editcmd *, lineno_t);
 static void	diff_write(struct editcmd *, void *, size_t);
+static int	diff_insert_edit(struct diffstart *, struct editcmd *);
+static int	diff_free(struct diffstart *);
 
 int
 diff_apply(struct stream *rd, struct stream *orig, struct stream *dest,
-    struct keyword *keyword, struct diffinfo *di)
+    struct keyword *keyword, struct diffinfo *di, int comode)
 {
 	struct editcmd ec;
 	lineno_t i;
@@ -104,7 +120,7 @@ diff_apply(struct stream *rd, struct stream *orig, struct stream *dest,
 				line = stream_getln(rd, &size);
 				if (line == NULL)
 					return (-1);
-				if (line[0] == '.') {
+				if (comode && line[0] == '.') {
 					line++;
 					size--;
 				}
@@ -143,6 +159,213 @@ diff_apply(struct stream *rd, struct stream *orig, struct stream *dest,
 	return (0);
 }
 
+static int
+diff_write_reverse(struct stream *dest, struct diffstart *ds)
+{
+	long firstoutputlinedeleted, endline, startline, editline, num_deleted,
+	    num_added;
+	int num;
+	struct editcmd *ec, *nextec;
+
+	nextec = LIST_FIRST(&ds->dhead);
+	editline = 0;
+	num = 0;
+	while (nextec != NULL) {
+		ec = nextec;
+		nextec = LIST_NEXT(nextec, next);
+		if (nextec == NULL)
+			break;
+		num++;
+		num_deleted = 0;
+		if (ec->havetext)
+			num_deleted = ec->count;
+		num_added = num_deleted + nextec->offset - ec->offset;
+		if (num_deleted > 0) {
+			firstoutputlinedeleted = ec->key - num_deleted + 1;
+			stream_printf(dest, "d%ld %ld\n", firstoutputlinedeleted,
+			    num_deleted);
+			if (num_added <= 0)
+				continue;
+		}
+		if (num_added > 0) {
+			stream_printf(dest, "a%ld %ld\n", ec->key, num_added);
+			startline = ec->key - num_deleted + 1 + ec->offset;
+			endline = startline + num_added - 1;
+
+			/* Copy lines from original file. First ignore some. */
+			ec->editline = editline;
+			diff_ignoreln(ec,  startline - 1);
+			diff_copyln(ec, endline);
+			editline = ec->editline;
+		}
+	}
+	return (0);
+}
+
+/* 
+ * Insert a diff into the list sorted on key. Should perhaps use quicker
+ * algorithms than insertion sort, but do this for now.
+ */
+static int
+diff_insert_edit(struct diffstart *ds, struct editcmd *ec)
+{
+	struct editcmd *curec;
+
+	if (ec == NULL)
+		return (0);
+
+	if (LIST_EMPTY(&ds->dhead)) {
+		LIST_INSERT_HEAD(&ds->dhead, ec, next);
+		return (0);
+	}
+
+	/* Insertion sort based on key. */
+	/* XXX: check if this gets too slow. */
+	LIST_FOREACH(curec, &ds->dhead, next) {
+		if (ec->key < curec->key) {
+			LIST_INSERT_BEFORE(curec, ec, next);
+			return (0);
+		}
+		if (LIST_NEXT(curec, next) == NULL)
+			break;
+	}
+	/* Just insert it after. */
+	LIST_INSERT_AFTER(curec, ec, next);
+	return (0);
+}
+
+static int
+diff_free(struct diffstart *ds)
+{
+	struct editcmd *ec;
+	int freecount = 0;
+
+	while(!LIST_EMPTY(&ds->dhead)) {
+		ec = LIST_FIRST(&ds->dhead);
+		LIST_REMOVE(ec, next);
+		free(ec);
+		freecount++;
+	}
+	return freecount;
+}
+
+/*
+ * Write the reverse diff from the diff in rd, and original file into
+ * destination. This algorithm is the same as used in cvsup.
+ */
+int
+diff_reverse(struct stream *rd, struct stream *orig, struct stream *dest,
+    struct keyword *keyword, struct diffinfo *di)
+{
+	struct diffstart ds;
+	struct editcmd ec, *addec, *delec;
+	lineno_t i;
+	char *line;
+	int error, offset;
+	int malloccount = 0, freecount = 0;
+
+	memset(&ec, 0, sizeof(ec));
+	ec.orig = orig;
+	ec.dest = dest;
+	ec.keyword = keyword;
+	ec.di = di;
+	addec = NULL;
+	delec = NULL;
+	ec.havetext = 0;
+	offset = 0;
+	LIST_INIT(&ds.dhead);
+
+	/* Start with next since we need it. */
+	line = stream_getln(rd, NULL);
+	/* First we build up the list of diffs from input. */
+	while (line != NULL) {
+		error = diff_geteditcmd(&ec, line);
+		/*fprintf(stderr, "Diff line '%s'\n", line);*/
+		if (error)
+			break;
+		if (ec.cmd == EC_ADD) {
+			addec = xmalloc(sizeof(struct editcmd));
+			malloccount++;
+			*addec = ec;
+			addec->havetext = 1;
+			/* Ignore the lines we was supposed to add. */
+			for (i = 0; i < ec.count; i++) {
+				line = stream_getln(rd, NULL);
+				/*fprintf(stderr, "Diff line '%s'\n", line);*/
+				if (line == NULL)
+					return (-1);
+			}
+
+			/* Get the next diff command if we have one. */
+			addec->key = addec->where + addec->count - offset;
+			if (delec != NULL && delec->key == addec->key - addec->count) {
+				delec->key = addec->key;
+				delec->havetext = addec->havetext;
+				delec->count = addec->count;
+
+				diff_insert_edit(&ds, delec);
+				free(addec);
+				freecount++;
+				delec = NULL;
+				addec = NULL;
+			} else {
+				if (delec != NULL) {
+					diff_insert_edit(&ds, delec);
+				}
+				delec = NULL;
+				addec->offset = offset;
+				diff_insert_edit(&ds, addec);
+				addec = NULL;
+			}
+			offset -= ec.count;
+		} else if (ec.cmd == EC_DEL) {
+			if (delec != NULL) {
+				/* Update offset to our next. */
+				diff_insert_edit(&ds, delec);
+				delec = NULL;
+			}
+			delec = xmalloc(sizeof(struct editcmd));
+			malloccount++;
+			*delec = ec;
+			delec->key = delec->where - 1 - offset;
+			delec->offset = offset;
+			delec->count = 0;
+			delec->havetext = 0;
+			/* Important to use the count we had before reset.*/
+			offset += ec.count;
+		}
+		line = stream_getln(rd, NULL);
+	}
+
+	while (line != NULL) {
+		/*fprintf(stderr, "Diff line '%s'\n", line);*/
+		line = stream_getln(rd, NULL);
+	}
+	/*fprintf(stderr, "Done with diff\n");*/
+	if (delec != NULL) {
+		diff_insert_edit(&ds, delec);
+		delec = NULL;
+	}
+
+	addec = xmalloc(sizeof(struct editcmd));
+	malloccount++;
+	/* Should be filesize, but we set it to max value. */
+	addec->key = MAXKEY;
+	addec->offset = offset;
+	addec->havetext = 0;
+	addec->count = 0;
+	diff_insert_edit(&ds, addec);
+	addec = NULL;
+
+	/*fprintf(stderr, "Done with last diff\n");*/
+	diff_write_reverse(dest, &ds);
+	freecount += diff_free(&ds);
+	/*fprintf(stderr, "Diff did a total of %d mallocs\n", malloccount);
+	fprintf(stderr, "Diff did a total of %d frees\n", freecount);*/
+	stream_flush(dest);
+	return (0);
+}
+
 /* Get an editing command from the diff. */
 static int
 diff_geteditcmd(struct editcmd *ec, char *line)
@@ -194,6 +417,22 @@ diff_copyln(struct editcmd *ec, lineno_t to)
 	return (0);
 }
 
+/* Ignore lines from the original version of the file up to line "to". */
+static int
+diff_ignoreln(struct editcmd *ec, lineno_t to)
+{
+	char *line;
+	size_t size;
+
+	while (ec->editline < to) {
+		line = stream_getln(ec->orig, &size);
+		if (line == NULL)
+			return (-1);
+		ec->editline++;
+	}
+	return (0);
+}
+
 /* Write a new line to the file, expanding RCS keywords appropriately. */
 static void
 diff_write(struct editcmd *ec, void *buf, size_t size)