implemented to undo stack memory limiting

 * acts as a safe-guard against uninterrupted infinite loops
   or other operations that are costly to undo in interactive mode.
   If we're out of memory, it is usually too late to react properly.
   This implementation tries to avoid OOMs due to SciTECO behaviour.
   We cannot fully exclude the chance of an OOM error.
 * The undo stack size is only approximated using the
   UndoToken::get_size() method.
   Other ways to measure the exact amount of allocated heap
   (including size fields in every heap object or using sbrk(0) and
   similar) are either costly in terms of memory or platform-specific.
   This implementation does not need any additional memory per heap
   object or undo token but exploits the fact that undo tokens
   are virtual already. The size of an undo token is determined
   at compile time.
 * Default memory limit of 500mb should be OK for most people.
 * The current limit can be queried with "2EJ" and set with <x>,2EJ.
   This also works interactively (a bit tricky!)
 * Limiting can be disabled. In this case, undo token processing
   is a bit faster.
 * closes #3

10 files changed, 238 insertions, 33 deletions

diff --git a/src/expressions.h b/src/expressions.h
index ee9ca6f..e4b8908 100644
--- a/src/expressions.h
+++ b/src/expressions.h
@@ -27,7 +27,7 @@ namespace SciTECO {
 
 template <typename Type>
 class ValueStack {
-	class UndoTokenPush : public UndoToken {
+	class UndoTokenPush : public UndoTokenWithSize<UndoTokenPush> {
 		ValueStack<Type> *stack;
 
 		Type	value;
@@ -45,7 +45,7 @@ class ValueStack {
 		}
 	};
 
-	class UndoTokenPop : public UndoToken {
+	class UndoTokenPop : public UndoTokenWithSize<UndoTokenPop> {
 		ValueStack<Type> *stack;
 
 		int index;
diff --git a/src/goto.h b/src/goto.h
index 1988e23..76b3147 100644
--- a/src/goto.h
+++ b/src/goto.h
@@ -18,6 +18,8 @@
 #ifndef __GOTO_H
 #define __GOTO_H
 
+#include <string.h>
+
 #include <glib.h>
 #include <glib/gprintf.h>
 
@@ -51,6 +53,12 @@ class GotoTable : public RBTree {
 			table->dump();
 #endif
 		}
+
+		gsize
+		get_size(void) const
+		{
+			return sizeof(*this) + strlen(name) + 1;
+		}
 	};
 
 	class Label : public RBTree::RBEntry {
diff --git a/src/interface.h b/src/interface.h
index cf9aef6..8f37668 100644
--- a/src/interface.h
+++ b/src/interface.h
@@ -64,7 +64,7 @@ class View {
 		return *(ViewImpl *)this;
 	}
 
-	class UndoTokenMessage : public UndoToken {
+	class UndoTokenMessage : public UndoTokenWithSize<UndoTokenMessage> {
 		ViewImpl &view;
 
 		unsigned int iMessage;
@@ -74,8 +74,7 @@ class View {
 	public:
 		UndoTokenMessage(ViewImpl &_view, unsigned int _iMessage,
 				 uptr_t _wParam = 0, sptr_t _lParam = 0)
-				: UndoToken(), view(_view),
-		                  iMessage(_iMessage),
+				: view(_view), iMessage(_iMessage),
 				  wParam(_wParam), lParam(_lParam) {}
 
 		void
@@ -85,7 +84,8 @@ class View {
 		}
 	};
 
-	class UndoTokenSetRepresentations : public UndoToken {
+	class UndoTokenSetRepresentations : public
+	      UndoTokenWithSize<UndoTokenSetRepresentations> {
 		ViewImpl &view;
 
 	public:
@@ -158,7 +158,7 @@ class Interface {
 		return *(InterfaceImpl *)this;
 	}
 
-	class UndoTokenShowView : public UndoToken {
+	class UndoTokenShowView : public UndoTokenWithSize<UndoTokenShowView> {
 		ViewImpl *view;
 
 	public:
@@ -169,7 +169,7 @@ class Interface {
 	};
 
 	template <class Type>
-	class UndoTokenInfoUpdate : public UndoToken {
+	class UndoTokenInfoUpdate : public UndoTokenWithSize< UndoTokenInfoUpdate<Type> > {
 		Type *obj;
 
 	public:
diff --git a/src/ioview.cpp b/src/ioview.cpp
index 12f7312..2d368ed 100644
--- a/src/ioview.cpp
+++ b/src/ioview.cpp
@@ -192,6 +192,17 @@ public:
 				      savepoint);
 		}
 	}
+
+	gsize
+	get_size(void) const
+	{
+		gsize ret = sizeof(*this) + strlen(filename) + 1;
+
+		if (savepoint)
+			ret += strlen(savepoint) + 1;
+
+		return ret;
+	}
 };
 
 static void
diff --git a/src/ioview.h b/src/ioview.h
index 90b82b4..6a87b7b 100644
--- a/src/ioview.h
+++ b/src/ioview.h
@@ -18,6 +18,8 @@
 #ifndef __IOVIEW_H
 #define __IOVIEW_H
 
+#include <string.h>
+
 #include <glib.h>
 #include <glib/gstdio.h>
 
@@ -60,6 +62,12 @@ class IOView : public ViewCurrent {
 		{
 			g_unlink(filename);
 		}
+
+		gsize
+		get_size(void) const
+		{
+			return sizeof(*this) + strlen(filename) + 1;
+		}
 	};
 
 public:
diff --git a/src/parser.cpp b/src/parser.cpp
index 384c42d..97876b0 100644
--- a/src/parser.cpp
+++ b/src/parser.cpp
@@ -1896,31 +1896,69 @@ StateECommand::custom(gchar chr)
 	 * If \fIkey\fP is omitted, the prefix sign is implied
 	 * (1 or -1).
 	 * With two arguments, it sets property \fIkey\fP to
-	 * \fIvalue\fP and returns nothing. Currently, there
-	 * are no properties that can be set.
+	 * \fIvalue\fP and returns nothing. Properties may be
+	 * read-only.
 	 *
 	 * The following property keys are defined:
 	 * .IP 0 4
 	 * The current user interface: 1 for Curses, 2 for GTK
+	 * (\fBread-only\fP)
 	 * .IP 1
 	 * The current numbfer of buffers: Also the numeric id
 	 * of the last buffer in the ring. This is implied if
 	 * no argument is given, so \(lqEJ\(rq returns the number
 	 * of buffers in the ring.
+	 * (\fBread-only\fP)
+	 * .IP 2
+	 * The current undo stack memory limit in bytes.
+	 * This limit helps to prevent dangerous out-of-memory
+	 * conditions (e.g. resulting from infinite loops) by
+	 * approximating the memory used by \*(ST's undo stack and is only
+	 * effective in interactive mode.
+	 * Commands which would exceed that limit fail instead.
+	 * When getting, a zero value indicates that memory limiting is
+	 * disabled.
+	 * Setting a value less than or equal to 0 as in
+	 * \(lq0,2EJ\(rq disables the limit.
+	 * \fBWarning:\fP Disabling memory limiting may provoke
+	 * uncontrollable out-of-memory errors in long running
+	 * or infinite loops.
+	 * Setting a new limit may fail if the current undo stack
+	 * is too large for the new limit \(em if this happens
+	 * you may have to clear your command-line first.
+	 * Undo stack memory limiting is enabled by default.
 	 */
 	case 'J': {
 		BEGIN_EXEC(&States::start);
 
+		enum {
+			EJ_USER_INTERFACE = 0,
+			EJ_BUFFERS,
+			EJ_UNDO_MEMORY_LIMIT
+		};
 		tecoInt property;
 
 		expressions.eval();
 		property = expressions.pop_num_calc();
-		if (expressions.args() > 0)
-			throw Error("Cannot set property %" TECO_INTEGER_FORMAT
-			            " for <EJ>", property);
+		if (expressions.args() > 0) {
+			/* set property */
+			tecoInt value = expressions.pop_num_calc();
+
+			switch (property) {
+			case EJ_UNDO_MEMORY_LIMIT:
+				undo.set_memory_limit(MAX(0, value));
+				break;
+
+			default:
+				throw Error("Cannot set property %" TECO_INTEGER_FORMAT
+				            " for <EJ>", property);
+			}
+
+			break;
+		}
 
 		switch (property) {
-		case 0: /* user interface */
+		case EJ_USER_INTERFACE:
 #ifdef INTERFACE_CURSES
 			expressions.push(1);
 #elif defined(INTERFACE_GTK)
@@ -1930,10 +1968,14 @@ StateECommand::custom(gchar chr)
 #endif
 			break;
 
-		case 1: /* number of buffers */
+		case EJ_BUFFERS:
 			expressions.push(ring.get_id(ring.last()));
 			break;
 
+		case EJ_UNDO_MEMORY_LIMIT:
+			expressions.push(undo.memory_limit);
+			break;
+
 		default:
 			throw Error("Invalid property %" TECO_INTEGER_FORMAT
 			            " for <EJ>", property);
diff --git a/src/qregisters.h b/src/qregisters.h
index 62a9521..8414439 100644
--- a/src/qregisters.h
+++ b/src/qregisters.h
@@ -168,7 +168,7 @@ public:
 };
 
 class QRegisterTable : private RBTree {
-	class UndoTokenRemove : public UndoToken {
+	class UndoTokenRemove : public UndoTokenWithSize<UndoTokenRemove> {
 		QRegisterTable *table;
 		QRegister *reg;
 
@@ -266,14 +266,21 @@ class QRegisterStack {
 		}
 
 		void run(void);
+
+		gsize
+		get_size(void) const
+		{
+			return entry ? sizeof(*this) + sizeof(*entry)
+			             : sizeof(*this);
+		}
 	};
 
-	class UndoTokenPop : public UndoToken {
+	class UndoTokenPop : public UndoTokenWithSize<UndoTokenPop> {
 		QRegisterStack *stack;
 
 	public:
 		UndoTokenPop(QRegisterStack *_stack)
-			    : UndoToken(), stack(_stack) {}
+			    : stack(_stack) {}
 
 		void run(void);
 	};
diff --git a/src/ring.h b/src/ring.h
index 5fe4082..0aa12f0 100644
--- a/src/ring.h
+++ b/src/ring.h
@@ -40,12 +40,12 @@ namespace SciTECO {
 class Buffer : private IOView {
 	TAILQ_ENTRY(Buffer) buffers;
 
-	class UndoTokenClose : public UndoToken {
+	class UndoTokenClose : public UndoTokenWithSize<UndoTokenClose> {
 		Buffer *buffer;
 
 	public:
 		UndoTokenClose(Buffer *_buffer)
-			      : UndoToken(), buffer(_buffer) {}
+			      : buffer(_buffer) {}
 
 		void run(void);
 	};
@@ -148,6 +148,13 @@ extern class Ring {
 		}
 
 		void run(void);
+
+		gsize
+		get_size(void) const
+		{
+			return buffer ? sizeof(*this) + sizeof(*buffer)
+			              : sizeof(*this);
+		}
 	};
 
 	TAILQ_HEAD(Head, Buffer) head;
diff --git a/src/undo.cpp b/src/undo.cpp
index 25303f5..c1e842a 100644
--- a/src/undo.cpp
+++ b/src/undo.cpp
@@ -30,6 +30,7 @@
 #include "sciteco.h"
 #include "cmdline.h"
 #include "interface.h"
+#include "error.h"
 #include "undo.h"
 
 namespace SciTECO {
@@ -38,18 +39,61 @@ namespace SciTECO {
 
 UndoStack undo;
 
+static inline gdouble
+size_to_mb(gsize s)
+{
+	return ((gdouble)s)/(1024*1024);
+}
+
+void
+UndoStack::set_memory_limit(gsize new_limit)
+{
+	if (new_limit) {
+		if (!memory_limit) {
+			/* memory_usage outdated - recalculate */
+			UndoToken *token;
+
+			memory_usage = 0;
+			SLIST_FOREACH(token, &head, tokens)
+				memory_usage += token->get_size();
+		}
+
+		if (memory_usage > new_limit)
+			throw Error("Cannot set undo memory limit (%gmb): "
+			            "Current stack too large (%gmb).",
+			            size_to_mb(new_limit),
+			            size_to_mb(memory_usage));
+	}
+
+	push_var(memory_limit) = new_limit;
+}
+
 void
 UndoStack::push(UndoToken *token)
 {
-	if (enabled) {
-#ifdef DEBUG
-		g_printf("UNDO PUSH %p\n", token);
-#endif
-		token->pos = cmdline_pos;
-		SLIST_INSERT_HEAD(&head, token, tokens);
-	} else {
+	if (!enabled) {
 		delete token;
+		return;
+	}
+
+	if (memory_limit) {
+		gsize token_size = token->get_size();
+
+		if (memory_usage + token_size > memory_limit) {
+			delete token;
+			throw Error("Undo stack memory limit (%gmb) exceeded. "
+			            "See <EJ> command.",
+			            size_to_mb(memory_limit));
+		}
+
+		memory_usage += token_size;
 	}
+
+#ifdef DEBUG
+	g_printf("UNDO PUSH %p\n", token);
+#endif
+	token->pos = cmdline_pos;
+	SLIST_INSERT_HEAD(&head, token, tokens);
 }
 
 void
@@ -62,6 +106,8 @@ UndoStack::pop(gint pos)
 		fflush(stdout);
 #endif
 
+		if (memory_limit)
+			memory_usage -= top->get_size();
 		top->run();
 
 		SLIST_REMOVE_HEAD(&head, tokens);
@@ -78,6 +124,8 @@ UndoStack::clear(void)
 		SLIST_REMOVE_HEAD(&head, tokens);
 		delete cur;
 	}
+
+	memory_usage = 0;
 }
 
 UndoStack::~UndoStack()
diff --git a/src/undo.h b/src/undo.h
index 17c8685..bd0ad74 100644
--- a/src/undo.h
+++ b/src/undo.h
@@ -18,6 +18,8 @@
 #ifndef __UNDO_H
 #define __UNDO_H
 
+#include <string.h>
+
 #include <bsd/sys/queue.h>
 
 #include <glib.h>
@@ -29,25 +31,65 @@
 
 namespace SciTECO {
 
+/**
+ * Default undo stack memory limit (500mb).
+ */
+#define UNDO_MEMORY_LIMIT_DEFAULT (500*1024*1024)
+
 class UndoToken {
 public:
 	SLIST_ENTRY(UndoToken) tokens;
 
+	/**
+	 * Command-line character position corresponding
+	 * to this token.
+	 *
+	 * @todo This wastes memory in macro calls and loops
+	 *       because all undo tokens will have the same
+	 *       value. It may be better to redesign the undo
+	 *       stack data structure - as a list/array pointing
+	 *       to undo stacks per character.
+	 */
 	gint pos;
 
 	virtual ~UndoToken() {}
 
-	virtual void run() = 0;
+	virtual void run(void) = 0;
+
+	/**
+	 * Return approximated size of this object.
+	 * If possible it should take all heap objects
+	 * into account that are memory-managed by the undo
+	 * token.
+	 * For a simple implementation, you may derive
+	 * from UndoTokenWithSize.
+	 */
+	virtual gsize get_size(void) const = 0;
+};
+
+/**
+ * UndoToken base class employing the CRTP idiom.
+ * Deriving this class adds a size approximation based
+ * on the shallow size of the template parameter.
+ */
+template <class UndoTokenImpl>
+class UndoTokenWithSize : public UndoToken {
+public:
+	gsize
+	get_size(void) const
+	{
+		return sizeof(UndoTokenImpl);
+	}
 };
 
 template <typename Type>
-class UndoTokenVariable : public UndoToken {
+class UndoTokenVariable : public UndoTokenWithSize< UndoTokenVariable<Type> > {
 	Type *ptr;
 	Type value;
 
 public:
 	UndoTokenVariable(Type &variable, Type _value)
-			 : UndoToken(), ptr(&variable), value(_value) {}
+			 : ptr(&variable), value(_value) {}
 
 	void
 	run(void)
@@ -66,7 +108,7 @@ class UndoTokenString : public UndoToken {
 
 public:
 	UndoTokenString(gchar *&variable, gchar *_str)
-		       : UndoToken(), ptr(&variable)
+		       : ptr(&variable)
 	{
 		str = _str ? g_strdup(_str) : NULL;
 	}
@@ -83,6 +125,13 @@ public:
 		*ptr = str;
 		str = NULL;
 	}
+
+	gsize
+	get_size(void) const
+	{
+		return str ? sizeof(*this) + strlen(str) + 1
+		           : sizeof(*this);
+	}
 };
 
 template <class Type>
@@ -92,7 +141,7 @@ class UndoTokenObject : public UndoToken {
 
 public:
 	UndoTokenObject(Type *&variable, Type *_obj)
-		       : UndoToken(), ptr(&variable), obj(_obj) {}
+		       : ptr(&variable), obj(_obj) {}
 
 	~UndoTokenObject()
 	{
@@ -108,20 +157,45 @@ public:
 		*ptr = obj;
 		obj = NULL;
 	}
+
+	gsize
+	get_size(void) const
+	{
+		return obj ? sizeof(*this) + sizeof(*obj)
+		           : sizeof(*this);
+	}
 };
 
 extern class UndoStack {
 	SLIST_HEAD(Head, UndoToken) head;
 
+	/**
+	 * Current approx. memory usage of all
+	 * undo tokens in the stack.
+	 * It is only up to date if memory limiting
+	 * is enabled.
+	 */
+	gsize memory_usage;
+
 public:
 	bool enabled;
 
-	UndoStack(bool _enabled = false) : enabled(_enabled)
+	/**
+	 * Undo stack memory limit in bytes.
+	 * 0 means no limiting.
+	 */
+	gsize memory_limit;
+
+	UndoStack(bool _enabled = false)
+	         : memory_usage(0), enabled(_enabled),
+	           memory_limit(UNDO_MEMORY_LIMIT_DEFAULT)
 	{
 		SLIST_INIT(&head);
 	}
 	~UndoStack();
 
+	void set_memory_limit(gsize new_limit = 0);
+
 	void push(UndoToken *token);
 
 	template <typename Type>