Add undo code to mg.

 needs further hacking.

 ok `whole bunch of people on icb'@

7 files changed, 530 insertions, 14 deletions

diff --git a/usr.bin/mg/Makefile b/usr.bin/mg/Makefile
index fb750662bc3..f9d2ada1be0 100644
--- a/usr.bin/mg/Makefile
+++ b/usr.bin/mg/Makefile
@@ -1,4 +1,4 @@
-# $OpenBSD: Makefile,v 1.10 2002/02/14 03:07:33 vincent Exp $
+# $OpenBSD: Makefile,v 1.11 2002/02/20 22:30:54 vincent Exp $
 
 PROG=	mg
 
@@ -22,7 +22,7 @@ SRCS=	cinfo.c fileio.c spawn.c ttyio.c tty.c ttykbd.c \
 	basic.c dir.c dired.c file.c line.c match.c paragraph.c \
 	random.c region.c search.c version.c window.c word.c \
 	buffer.c display.c echo.c extend.c help.c kbd.c keymap.c \
-	macro.c main.c modes.c re_search.c funmap.c
+	macro.c main.c modes.c re_search.c funmap.c undo.c
 
 #
 # More or less standalone extensions.
diff --git a/usr.bin/mg/def.h b/usr.bin/mg/def.h
index 0ee13e9d86b..7c5a5c57984 100644
--- a/usr.bin/mg/def.h
+++ b/usr.bin/mg/def.h
@@ -1,4 +1,6 @@
-/*	$OpenBSD: def.h,v 1.29 2002/02/16 21:27:49 millert Exp $	*/
+/*	$OpenBSD: def.h,v 1.30 2002/02/20 22:30:54 vincent Exp $	*/
+
+#include <sys/queue.h>
 
 /*
  * This file is the general header file for all parts
@@ -252,6 +254,26 @@ typedef struct {
 } REGION;
 
 /*
+ * This structure holds information about recent actions for the Undo command.
+ */
+struct undo_rec {
+        LIST_ENTRY(undo_rec) next;
+        BUFFER          *buf;
+	enum {
+		INSERT = 1,
+		DELETE,
+		CHANGE,
+		BOUNDARY
+	} type;
+	REGION		 region;
+	int		 pos;
+	int		 size;
+        char            *content;
+};
+   
+LIST_HEAD(undo_list, undo_rec);
+
+/*
  * Prototypes.
  */
 
@@ -490,6 +512,8 @@ int	 lowerregion(int, int);
 int	 upperregion(int, int);
 int	 prefixregion(int, int);
 int	 setprefix(int, int);
+int	 region_get_data(REGION *, char *, int);
+int	 region_put_data(const char *, int);
 
 /* search.c X */
 int	 forwsearch(int, int);
@@ -545,6 +569,15 @@ int	 cntmatchlines(int, int);
 int	 cntnonmatchlines(int, int);
 #endif	/* REGEX */
 
+/* undo.c X */
+int	 undo_init(void);
+int	 undo_enable(int);
+int	 undo_add_boundary(void);
+int	 undo_add_insert(LINE *, int, int);
+int	 undo_add_delete(LINE *, int, int);
+int	 undo_add_change(LINE *, int, int);
+int	 undo(void);
+
 /*
  * Externals.
  */
@@ -565,6 +598,7 @@ extern int	 ttcol;
 extern int	 tttop;
 extern int	 ttbot;
 extern int	 tthue;
+extern int	 undoaction;
 extern int	 defb_nmodes;
 extern int	 defb_flag;
 extern const char cinfo[];
@@ -580,4 +614,3 @@ extern char	 prompt[];
 int	 tceeol;
 int	 tcinsl;
 int	 tcdell;
-
diff --git a/usr.bin/mg/funmap.c b/usr.bin/mg/funmap.c
index 2beb16ecc9c..1b3d7bb98d4 100644
--- a/usr.bin/mg/funmap.c
+++ b/usr.bin/mg/funmap.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: funmap.c,v 1.4 2002/02/08 21:21:11 deraadt Exp $	*/
+/*	$OpenBSD: funmap.c,v 1.5 2002/02/20 22:30:54 vincent Exp $	*/
 /*
  * Copyright (c) 2001 Artur Grabowski <art@openbsd.org>.  All rights reserved.
  *
@@ -217,6 +217,7 @@ static struct funmap functnames[] = {
 	{usebuffer, "switch-to-buffer",},
 	{poptobuffer, "switch-to-buffer-other-window",},
 	{twiddle, "transpose-chars",},
+	{ undo, "undo", },
 	{universal_argument, "universal-argument",},
 	{upperregion, "upcase-region",},
 	{upperword, "upcase-word",},
diff --git a/usr.bin/mg/line.c b/usr.bin/mg/line.c
index 3c6c398b669..d88f60bef0f 100644
--- a/usr.bin/mg/line.c
+++ b/usr.bin/mg/line.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: line.c,v 1.12 2002/02/16 21:27:49 millert Exp $	*/
+/*	$OpenBSD: line.c,v 1.13 2002/02/20 22:30:54 vincent Exp $	*/
 
 /*
  *		Text line handling.
@@ -169,7 +169,7 @@ linsert(n, c)
 
 	/* current line */
 	lp1 = curwp->w_dotp;
-
+	
 	/* special case for the end */
 	if (lp1 == curbp->b_linep) {
 		LINE *lp2, *lp3;
@@ -182,7 +182,6 @@ linsert(n, c)
 		/* allocate a new line */
 		if ((lp2 = lalloc(n)) == NULL)
 			return FALSE;
-
 		/* previous line */
 		lp3 = lp1->l_bp;
 		/* link in */
@@ -200,7 +199,8 @@ linsert(n, c)
 			if (wp->w_markp == lp1)
 				wp->w_markp = lp2;
 		}
-
+		if (!undoaction)
+			undo_add_insert(lp2, 0, n);
 		curwp->w_doto = n;
 		return TRUE;
 	}
@@ -230,7 +230,8 @@ linsert(n, c)
 				wp->w_marko += n;
 		}
 	}
-
+	if (!undoaction)
+		undo_add_insert(curwp->w_dotp, doto, n);
 	return TRUE;
 }
 
@@ -311,6 +312,10 @@ ldelete(n, kflag)
 	int	 doto;
 	char	*cp1, *cp2;
 
+	if (!undoaction) {
+		undo_add_delete(curwp->w_dotp, curwp->w_doto, n);
+	}
+	
 	/*
 	 * HACK - doesn't matter, and fixes back-over-nl bug for empty
 	 *	kill buffers.
@@ -466,7 +471,7 @@ lreplace(plen, st, f)
 	int	rtype;	/* capitalization		 */
 	int	c;	/* used for random characters	 */
 	int	doto;	/* offset into line		 */
-
+	
 	/*
 	 * Find the capitalization of the word that was found.  f says use
 	 * exact case of replacement string (same thing that happens with
@@ -485,6 +490,7 @@ lreplace(plen, st, f)
 			}
 		}
 	}
+	
 	/*
 	 * make the string lengths match (either pad the line
 	 * so that it will fit, or scrunch out the excess).
@@ -529,6 +535,7 @@ lreplace(plen, st, f)
 	return (TRUE);
 }
 
+
 /*
  * Delete all of the text saved in the kill buffer.  Called by commands when
  * a new kill context is created. The kill buffer array is released, just in
diff --git a/usr.bin/mg/main.c b/usr.bin/mg/main.c
index 0d7f7ba1cf0..48e09b2f537 100644
--- a/usr.bin/mg/main.c
+++ b/usr.bin/mg/main.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: main.c,v 1.15 2002/02/16 21:27:49 millert Exp $	*/
+/*	$OpenBSD: main.c,v 1.16 2002/02/20 22:30:54 vincent Exp $	*/
 
 /*
  *	Mainline.
@@ -41,7 +41,8 @@ main(argc, argv)
 	maps_init();		/* Keymaps and modes.		*/
 	funmap_init();		/* Functions.			*/
 	ttykeymapinit();	/* Symbols, bindings.		*/
-
+	undo_init();
+	
 	/*
 	 * This is where we initialize standalone extensions that should
 	 * be loaded dynamically sometime in the future.
diff --git a/usr.bin/mg/region.c b/usr.bin/mg/region.c
index 34a1b621223..9b3142a20d2 100644
--- a/usr.bin/mg/region.c
+++ b/usr.bin/mg/region.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: region.c,v 1.8 2002/02/16 21:27:49 millert Exp $	*/
+/*	$OpenBSD: region.c,v 1.9 2002/02/20 22:30:54 vincent Exp $	*/
 
 /*
  *		Region based commands.
@@ -95,6 +95,9 @@ lowerregion(f, n)
 
 	if ((s = getregion(&region)) != TRUE)
 		return s;
+
+	undo_add_change(region.r_linep, region.r_offset, region.r_size);
+	
 	lchange(WFHARD);
 	linep = region.r_linep;
 	loffs = region.r_offset;
@@ -129,6 +132,9 @@ upperregion(f, n)
 
 	if ((s = getregion(&region)) != TRUE)
 		return s;
+	
+	undo_add_change(region.r_linep, region.r_offset, region.r_size);
+		
 	lchange(WFHARD);
 	linep = region.r_linep;
 	loffs = region.r_offset;
@@ -305,3 +311,45 @@ setprefix(f, n)
 	return s;
 }
 #endif /* PREFIXREGION */
+
+
+int
+region_get_data(REGION *reg, char *buf, int len)
+{
+	int i, off;
+	LINE *lp;
+	
+	i = 0;
+	off = reg->r_offset;
+	lp = reg->r_linep;
+	while (i < len) {
+		if (off == llength(lp)) {
+			lp = lforw(lp);
+			if (lp == curwp->w_linep)
+				break;
+			off = 0;
+			buf[i] = '\n';
+		} else {
+			buf[i] = lgetc(lp, off);
+			off++;
+		}
+		i++;
+	}
+	return i;
+}
+
+int
+region_put_data(const char *buf, int len)
+{
+	int i;
+
+	for (i = 0; i < len; i++) {
+		if (buf[i] == '\n')
+			lnewline();
+		else
+			linsert(1, buf[i]);
+	}
+	return 0;
+}
+
+
diff --git a/usr.bin/mg/undo.c b/usr.bin/mg/undo.c
new file mode 100644
index 00000000000..649a9f49f54
--- /dev/null
+++ b/usr.bin/mg/undo.c
@@ -0,0 +1,426 @@
+/* $OpenBSD: undo.c,v 1.1 2002/02/20 22:30:54 vincent Exp $ */
+/*
+ * Copyright (c) 2002 Vincent Labrecque <vincent@openbsd.org>
+ *							 All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "def.h"
+#include "kbd.h"
+
+#include <sys/queue.h>
+
+#define MAX_LIST_RECORDS	32
+#define MAX_FREE_RECORDS	32
+
+/*
+ * Local variables
+ */
+static struct undo_list	undo_list;
+static int		undo_list_num;
+static struct undo_list undo_free;
+static int		undo_free_num;
+
+/*
+ * Global variables
+ */
+/*
+ * undo_disable_flag -
+ *
+ * Stop doing undo (useful when we know are
+ * going to deal with huge deletion/insertions
+ * that we don't plan to undo)
+ */
+int undo_disable_flag;
+int undoaction;			/* Are we called indirectly from undo()? */
+
+/*
+ * Local functions
+ */
+static int find_offset(LINE *, int);
+static int find_linep(int, LINE **, int *);
+static struct undo_rec *new_undo_record(void);
+static void free_undo_record(struct undo_rec *);
+static int drop_oldest_undo_record(void);
+
+static int
+find_offset(LINE *lp, int off)
+{
+	int count = 0;
+	LINE *p;
+
+	for (p = curwp->w_linep; p != lp; p = lforw(p)) {
+		if (count != 0) {
+			if (p == curbp->b_linep) {
+				ewprintf("Error: Undo stuff called with a"
+				    "nonexistent line\n");
+				return FALSE;
+			}
+		}
+		count += llength(p) + 1;
+	}
+	count += off;
+
+	return count;
+}
+
+static int
+find_linep(int pos, LINE **olp, int *offset)
+{
+	LINE *p;
+
+	p = curwp->w_linep;
+	while (pos > 0 && pos > llength(p)) {
+		pos -= llength(p) + 1;
+		if ((p = lforw(p)) == curbp->b_linep) {
+			*olp = NULL;
+			*offset = 0;
+			return FALSE;
+		}
+	}
+	*olp = p;
+	*offset = pos;
+
+	return TRUE;
+}
+
+static struct undo_rec *
+new_undo_record(void)
+{
+	struct undo_rec *rec;
+
+	while (undo_list_num >= MAX_LIST_RECORDS) {
+		drop_oldest_undo_record();
+		undo_list_num--;
+	}
+	undo_list_num++;
+	rec = LIST_FIRST(&undo_free);
+	if (rec != NULL)
+		LIST_REMOVE(rec, next);	/* Remove it from the free-list */
+	else {
+		if ((rec = malloc(sizeof *rec)) == NULL)
+			panic("Out of memory in undo code (record)");
+	}
+	memset(rec, 0, sizeof(struct undo_rec));
+	
+	return rec;
+}
+
+static void
+free_undo_record(struct undo_rec *rec)
+{
+	if (rec->content != NULL) {
+		free(rec->content);
+		rec->content = NULL;
+	}
+	if (undo_free_num >= MAX_FREE_RECORDS) {
+		free(rec);
+		return;
+	}
+	undo_free_num++;
+	
+	LIST_INSERT_HEAD(&undo_free, rec, next);
+}
+
+/*
+ * Drop the oldest undo record in our list. Return 1 if we could remove it,
+ * 0 if the undo list was empty
+ */
+static int
+drop_oldest_undo_record(void)
+{
+	struct undo_rec *rec;
+
+	rec = LIST_END(&undo_list);
+	if (rec != NULL) {
+		undo_free_num--;
+		LIST_REMOVE(rec, next);	/* Remove it from the undo_list before
+					 * we insert it in the free list */
+		free_undo_record(rec);
+		return 1;
+	}
+	return 0;
+}
+	
+int
+undo_init(void)
+{
+	LIST_INIT(&undo_free);
+	LIST_INIT(&undo_list);
+	
+	return TRUE;
+}
+
+int
+undo_enable(int on)
+{
+	undo_disable_flag = on ? 0 : 1;
+	
+	/*
+	 * XXX-Vince:
+	 *
+	 * Here, I wonder if we should assume that the user has made a
+	 * long term choice.  If so, we could free all internal undo
+	 * data and save memory.
+	 */
+	
+	return on;
+}
+
+int
+undo_add_boundary(void)
+{
+	struct undo_rec *rec;
+
+	if (undo_disable_flag)
+		return TRUE;
+
+	rec = new_undo_record();
+	rec->buf = curbp;
+	rec->type = BOUNDARY;
+
+	LIST_INSERT_HEAD(&undo_list, rec, next);
+	
+	return TRUE;
+}
+
+int
+undo_add_insert(LINE *lp, int offset, int size)
+{
+	REGION reg;
+	struct undo_rec *rec;
+	
+	if (undo_disable_flag)
+		return TRUE;
+
+	reg.r_linep = lp;
+	reg.r_offset = offset;
+	reg.r_size = size;
+	
+	/*
+	 * We try to reuse the last undo record to `compress' things.
+	 */	
+	rec = LIST_FIRST(&undo_list);
+	if ((rec != NULL) &&
+	    (rec->type == INSERT) &&
+	    (rec->buf == curbp) &&
+	    (rec->region.r_linep == lp)) {
+		int dist;
+
+		dist = rec->region.r_offset - reg.r_offset;
+		
+		if (rec->region.r_size >= dist) {
+			rec->region.r_size += reg.r_size;
+			return TRUE;
+		}
+	}
+	/*
+	 * We couldn't reuse the last undo record, so prepare a new one
+	 */
+	rec = new_undo_record();
+	rec->pos = find_offset(lp, offset);
+	rec->buf = curbp;
+	rec->type = INSERT;
+	memmove(&rec->region, &reg, sizeof(REGION));
+	rec->content = NULL;
+	LIST_INSERT_HEAD(&undo_list, rec, next);
+
+	return TRUE;
+}
+
+/*
+ * This of course must be done _before_ the actual deletion is done
+ */
+int
+undo_add_delete(LINE *lp, int offset, int size)
+{
+	REGION reg;
+	struct undo_rec *rec;
+	int dist, pos;
+
+	if (undo_disable_flag)
+		return TRUE;
+
+	reg.r_linep = lp;
+	reg.r_offset = offset;
+	reg.r_size = size;
+
+	pos = find_offset(lp, offset);
+
+	/*
+	 * Again, try to reuse last undo record, if we can
+	 */
+	rec = LIST_FIRST(&undo_list);
+	if ((rec != NULL) &&
+	    (rec->type == DELETE) &&
+	    (rec->buf == curbp) &&
+	    (rec->region.r_linep == reg.r_linep)) {
+		char *newbuf;
+		int newlen;
+
+		dist = rec->region.r_offset - reg.r_offset;
+		if (rec->region.r_size >= dist) {
+			newlen = rec->region.r_size + reg.r_size;
+
+			do {
+				newbuf = malloc(newlen * sizeof(char));
+			} while (newbuf == NULL && drop_oldest_undo_record());
+			
+			if (newbuf == NULL)
+				panic("out of memory in undo delete code");
+
+			/*
+			 * [new data][old data]
+			 */
+			region_get_data(&reg, newbuf, size);
+			memmove(newbuf + reg.r_size, rec->content,
+			    rec->region.r_size);
+
+			rec->pos = pos;
+			rec->region.r_offset = reg.r_offset;
+			rec->region.r_size = newlen;
+			if (rec->content != NULL)
+				free(rec->content);
+			rec->content = newbuf;
+
+			return TRUE;
+		}
+	}
+
+	/*
+	 * So we couldn't reuse the last undo record? Just allocate a new
+	 * one.
+	 */
+	rec = new_undo_record();
+	rec->pos = pos;
+
+	rec->buf = curbp;
+	rec->type = DELETE;
+	memmove(&rec->region, &reg, sizeof(REGION));
+	do {
+		rec->content = malloc(reg.r_size + 1);
+	} while ((rec->content == NULL) && drop_oldest_undo_record());
+	
+	if (rec->content == NULL)
+		panic("Out of memory");
+	
+	region_get_data(&reg, rec->content, reg.r_size);
+
+	LIST_INSERT_HEAD(&undo_list, rec, next);
+
+	return TRUE;
+}
+
+/*
+ * This of course must be called before the change takes place
+ */
+int
+undo_add_change(LINE *lp, int offset, int size)
+{
+	REGION reg;
+	struct undo_rec *rec;
+
+		
+	if (undo_disable_flag)
+		return TRUE;
+	
+	reg.r_linep = lp;
+	reg.r_offset = offset;
+	reg.r_size = size;
+	
+	rec = new_undo_record();
+	rec->pos = find_offset(lp, offset);
+	rec->buf = curbp;
+	rec->type = CHANGE;
+	memmove(&rec->region, &reg, sizeof reg);
+
+	do {
+		rec->content = malloc(size + 1);
+	} while ((rec->content == NULL) && drop_oldest_undo_record());
+	
+	if (rec->content == NULL)
+		panic("Out of memory in undo change code");
+
+	region_get_data(&reg, rec->content, size);
+
+	LIST_INSERT_HEAD(&undo_list, rec, next);
+	
+	return TRUE;
+}
+
+int
+undo(void)
+{
+	struct undo_rec *rec;
+	LINE *ln;
+	int off;
+
+ again:
+	rec = LIST_FIRST(&undo_list);
+	if (rec == NULL) {
+		ewprintf("Nothing to undo!");
+		return FALSE;
+	}
+	if (rec->buf != curbp)
+		popbuf(rec->buf);
+
+	LIST_REMOVE(rec, next);
+	if (rec->type == BOUNDARY)
+		goto again;
+
+	/*
+	 * Let called functions know they are below us (for example, ldelete
+	 * don't want to record an undo record when called by us)
+	 */
+	undoaction++;
+
+	find_linep(rec->pos, &ln, &off);
+	if (ln == NULL)
+		return FALSE;
+	
+	/*
+	 * Move to where this record has to apply
+	 */
+	curwp->w_dotp = ln;
+	curwp->w_doto = off;
+
+	switch (rec->type) {
+	case INSERT:
+		ldelete(rec->region.r_size, KFORW);
+		break;
+	case DELETE:
+		region_put_data(rec->content, rec->region.r_size);
+		break;
+	case CHANGE:
+		forwchar(0, rec->region.r_size);
+		lreplace(rec->region.r_size, rec->content, 1);
+		break;
+	default:
+		break;
+	}
+
+	free_undo_record(rec);
+
+	undoaction--;
+	
+	return TRUE;
+}