Refactor messages.cc to use boost::circular_buffer

We might as well delegate the massive implementation
complexity and get rid of a ton of legacy code.

11 files changed, 172 insertions, 393 deletions

diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index 8991318d..7d64a66f 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -43,6 +43,7 @@ SET(SRCS_COMMON
   lua_bind.cc
   melee1.cc
   melee2.cc
+  message.cc
   messages.cc
   mimic.cc
   modules.cc
diff --git a/src/cmd4.cc b/src/cmd4.cc
index 724d5a1f..12d47324 100644
--- a/src/cmd4.cc
+++ b/src/cmd4.cc
@@ -255,10 +255,12 @@ void do_cmd_change_name(void)
  */
 void do_cmd_message_one(void)
 {
-	cptr msg = format("> %s", message_str(0));
+	auto message = message_at(0);
+
+	cptr msg = format("> %s", message.text_with_count().c_str());
 
 	/* Recall one message XXX XXX XXX */
-	display_message(0, 0, strlen(msg), message_color(0), msg);
+	display_message(0, 0, strlen(msg), message.color, msg);
 }
 
 
@@ -286,15 +288,8 @@ void do_cmd_messages(void)
 	u32b q;
 	int wid, hgt;
 
-	char shower[80];
-	char finder[80];
-
-	/* Wipe finder */
-	strcpy(finder, "");
-
-	/* Wipe shower */
-	strcpy(shower, "");
-
+	/* String to highlight */
+	std::string shower;
 
 	/* Total messages */
 	n = message_num();
@@ -323,30 +318,30 @@ void do_cmd_messages(void)
 		/* Dump up to 20 (or more in bigscreen) lines of messages */
 		for (j = 0; (j < (hgt - 4)) && (i + j < n); j++)
 		{
-			cptr msg = message_str(i + j);
-			byte color = message_color(i + j);
+			auto message = message_at(i + j);
+			auto text = message.text_with_count();
+			auto color = message.color;
 
 			/* Apply horizontal scroll */
-			msg = (strlen(msg) >= q) ? (msg + q) : "";
+			text = (text.size() >= q) ? text.substr(q) : "";
 
 			/* Dump the messages, bottom to top */
-			display_message(0, (hgt - 3) - j, strlen(msg), color, msg);
+			display_message(0, (hgt - 3) - j, text.size(), color, text.c_str());
 
 			/* Hilite "shower" */
 			if (shower[0])
 			{
-				cptr str = msg;
-
+				std::size_t pos = 0;
 				/* Display matches */
-				while ((str = strstr(str, shower)) != NULL)
+				while ((pos = text.find(shower, pos)) != std::string::npos)
 				{
-					int len = strlen(shower);
+					std::size_t len = shower.size();
 
 					/* Display the match */
-					Term_putstr(str - msg, (hgt - 3) - j, len, TERM_YELLOW, shower);
+					Term_putstr(pos, (hgt - 3) - j, len, TERM_YELLOW, shower.c_str());
 
 					/* Advance */
-					str += len;
+					pos += len;
 				}
 			}
 		}
@@ -394,7 +389,10 @@ void do_cmd_messages(void)
 			prt("Show: ", hgt - 1, 0);
 
 			/* Get a "shower" string, or continue */
-			if (!askfor_aux(shower, 80)) continue;
+			if (!askfor_aux(&shower, 80))
+			{
+				continue;
+			}
 
 			/* Okay */
 			continue;
@@ -409,18 +407,22 @@ void do_cmd_messages(void)
 			prt("Find: ", hgt - 1, 0);
 
 			/* Get a "finder" string, or continue */
-			if (!askfor_aux(finder, 80)) continue;
+			auto finder = shower;
+			if (!askfor_aux(&finder, 80))
+			{
+				continue;
+			}
 
 			/* Show it */
-			strcpy(shower, finder);
+			shower = finder;
 
 			/* Scan messages */
 			for (z = i + 1; z < n; z++)
 			{
-				cptr msg = message_str(z);
+				auto message = message_at(z);
 
 				/* Search for it */
-				if (strstr(msg, finder))
+				if (message.text_with_count().find(finder) != std::string::npos)
 				{
 					/* New location */
 					i = z;
diff --git a/src/init2.cc b/src/init2.cc
index 8fc4bb07..77866648 100644
--- a/src/init2.cc
+++ b/src/init2.cc
@@ -648,9 +648,6 @@ static errr init_misc(void)
 
 	/*** Prepare the various "bizarre" arrays ***/
 
-	/* Initialize messages subsystem */
-	message_init();
-
 	/* Initialise the values */
 	process_dungeon_file("misc.txt", &ystart, &xstart, 0, 0, TRUE, FALSE);
 
diff --git a/src/loadsave.cc b/src/loadsave.cc
index c8b3e533..ce7dfdf8 100644
--- a/src/loadsave.cc
+++ b/src/loadsave.cc
@@ -1943,43 +1943,38 @@ static bool_ do_inventory(ls_flag_t flag)
 }
 
 
+static void do_message(message &msg, ls_flag_t flag)
+{
+	do_std_string(msg.text, flag);
+	do_u32b(&msg.count, flag);
+	do_byte(&msg.color, flag);
+}
+
 
 /*
  * Read the saved messages
  */
 static void do_messages(ls_flag_t flag)
 {
-	int i;
-	char buf[128];
-	byte color;
-
-	s16b num;
-
-	/* Total */
-	if (flag == ls_flag_t::SAVE) num = message_num();
+	/* Save/load number of messages */
+	s16b num = message_num();
 	do_s16b(&num, flag);
 
 	/* Read the messages */
-	if (flag == ls_flag_t::LOAD)
+	for (int i = 0; i < num; i++)
 	{
-		for (i = 0; i < num; i++)
-		{
-			/* Read the message */
-			do_string(buf, 128, ls_flag_t::LOAD);
-			do_byte(&color, flag);
+		message message;
 
-			/* Save the message */
-			message_add(buf, color);
+		if (flag == ls_flag_t::SAVE)
+		{
+			message = message_at(i);
 		}
-	}
-	if (flag == ls_flag_t::SAVE)
-	{
-		byte holder;
-		for (i = num - 1; i >= 0; i--)
+
+		do_message(message, flag);
+
+		if (flag == ls_flag_t::LOAD)
 		{
-			do_string((char *)message_str((s16b)i), 0, ls_flag_t::SAVE);
-			holder = message_color((s16b)i);
-			do_byte(&holder, flag);
+			message_add(message);
 		}
 	}
 }
diff --git a/src/message.cc b/src/message.cc
new file mode 100644
index 00000000..a0f46f22
--- /dev/null
+++ b/src/message.cc
@@ -0,0 +1,15 @@
+#include "message.hpp"
+
+#include <fmt/format.h>
+
+std::string message::text_with_count() const
+{
+	if (count > 1)
+	{
+		return fmt::format("{} <{}x>", text, count);
+	}
+	else
+	{
+		return text;
+	}
+}
diff --git a/src/message.hpp b/src/message.hpp
new file mode 100644
index 00000000..7b47a9db
--- /dev/null
+++ b/src/message.hpp
@@ -0,0 +1,31 @@
+#pragma once
+
+#include "h-basic.h"
+
+#include <string>
+
+/**
+ * Message
+ */
+struct message {
+	/**
+	 * Message color.
+	 */
+	byte color = 0;
+
+	/**
+	 * Repetation count for this message.
+	 */
+	u32b count = 0;
+
+	/**
+	 * Message text.
+	 */
+	std::string text;
+
+	/**
+	 * Get message text with count
+	 */
+	std::string text_with_count() const;
+
+};
diff --git a/src/messages.cc b/src/messages.cc
index a4ce949d..c2f8d079 100644
--- a/src/messages.cc
+++ b/src/messages.cc
@@ -1,10 +1,8 @@
 #include "messages.hpp"
 
-#include "tome/make_array.hpp"
-
-#include "z-term.h"
-#include "z-form.h"
-#include "z-util.h"
+#include <boost/circular_buffer.hpp>
+#include <fmt/format.h>
+#include <string>
 
 /*
  * OPTION: Maximum number of messages to remember (see "io.c")
@@ -12,357 +10,57 @@
  */
 #define MESSAGE_MAX     2048
 
-/*
- * OPTION: Maximum space for the message text buffer (see "io.c")
- * Default: assume that each of the 2048 messages is repeated an
- * average of three times, and has an average length of 48
- */
-#define MESSAGE_BUF     32768
-
-
-
-
-/*
- * The next "free" index to use
- */
-static u16b message__next;
-
-/*
- * The index of the oldest message (none yet)
- */
-static u16b message__last;
-
-/*
- * The next "free" offset
+/**
+ * Circular buffer for the messages
  */
-static u16b message__head;
-
-/*
- * The offset to the oldest used char (none yet)
- */
-static u16b message__tail;
-
-/*
- * The array of offsets, by index [MESSAGE_MAX]
- */
-static u16b *message__ptr;
-
-/*
- * The array of colors, by index [MESSAGE_MAX]
- */
-static byte *message__color;
-
-/*
- * The array of message counts, by index [MESSAGE_MAX]
- */
-static u16b *message__count;
-
-/*
- * The array of chars, by offset [MESSAGE_BUF]
- */
-static char *message__buf;
-
-
-/*
-* Second try for the "message" handling routines.
-*
-* Each call to "message_add(s)" will add a new "most recent" message
-* to the "message recall list", using the contents of the string "s".
-*
-* The messages will be stored in such a way as to maximize "efficiency",
-* that is, we attempt to maximize the number of sequential messages that
-* can be retrieved, given a limited amount of storage space.
-*
-* We keep a buffer of chars to hold the "text" of the messages, not
-* necessarily in "order", and an array of offsets into that buffer,
-* representing the actual messages.  This is made more complicated
-* by the fact that both the array of indexes, and the buffer itself,
-* are both treated as "circular arrays" for efficiency purposes, but
-* the strings may not be "broken" across the ends of the array.
-*
-* The "message_add()" function is rather "complex", because it must be
-* extremely efficient, both in space and time, for use with the Borg.
-*/
-
-void message_init()
+static boost::circular_buffer<message> *buffer()
 {
-	/* Message variables */
-	message__ptr = make_array<u16b>(MESSAGE_MAX);
-	message__color = make_array<byte>(MESSAGE_MAX);
-	message__count = make_array<u16b>(MESSAGE_MAX);
-	message__buf = make_array<char>(MESSAGE_BUF);
-
-	/* Hack -- No messages yet */
-	message__tail = MESSAGE_BUF;
+	static auto *instance = new boost::circular_buffer<message>(MESSAGE_MAX);
+	return instance;
 }
 
-/*
-* How many messages are "available"?
-*/
 s16b message_num(void)
 {
-	int last, next, n;
-
-	/* Extract the indexes */
-	last = message__last;
-	next = message__next;
-
-	/* Handle "wrap" */
-	if (next < last) next += MESSAGE_MAX;
-
-	/* Extract the space */
-	n = (next - last);
-
-	/* Return the result */
-	return (n);
-}
-
-
-
-/*
-* Recall the "text" of a saved message
-*/
-cptr message_str(int age)
-{
-	static char buf[1024];
-	s16b x;
-	s16b o;
-	cptr s;
-
-	/* Forgotten messages have no text */
-	if ((age < 0) || (age >= message_num())) return ("");
-
-	/* Acquire the "logical" index */
-	x = (message__next + MESSAGE_MAX - (age + 1)) % MESSAGE_MAX;
-
-	/* Get the "offset" for the message */
-	o = message__ptr[x];
-
-	/* Access the message text */
-	s = &message__buf[o];
-
-	/* Hack -- Handle repeated messages */
-	if (message__count[x] > 1)
-	{
-		strnfmt(buf, 1024, "%s <%dx>", s, message__count[x]);
-		s = buf;
-	}
-
-	/* Return the message text */
-	return (s);
+	return buffer()->size();
 }
 
-/*
-* Recall the color of a saved message
-*/
-byte message_color(int age)
+message const &message_at(int age)
 {
-	s16b x;
-	byte color = TERM_WHITE;
+	assert(age >= 0);
+	assert(age < message_num());
 
-	/* Forgotten messages have no text */
-	if ((age < 0) || (age >= message_num())) return (TERM_WHITE);
+	// Age indexes backward through history and is zero-based, so...
+	std::size_t i = buffer()->size() - 1 - age;
 
-	/* Acquire the "logical" index */
-	x = (message__next + MESSAGE_MAX - (age + 1)) % MESSAGE_MAX;
-
-	/* Get the "offset" for the message */
-	color = message__color[x];
-
-	/* Return the message text */
-	return (color);
+	// Get the message
+	return buffer()->at(i);
 }
 
-
-/*
-* Add a new message, with great efficiency
-*/
 void message_add(cptr str, byte color)
 {
-	int i, k, x, n;
-	cptr s;
-
-
-	/*** Step 1 -- Analyze the message ***/
-
-	/* Hack -- Ignore "non-messages" */
-	if (!str) return;
+	assert(str != nullptr);
 
-	/* Message length */
-	n = strlen(str);
+	// Shorthand to avoid syntactic clutter
+	auto buf = buffer();
 
-	/* Important Hack -- Ignore "long" messages */
-	if (n >= MESSAGE_BUF / 4) return;
-
-
-	/*** Step 2 -- Handle repeated messages ***/
-
-	/* Acquire the "logical" last index */
-	x = (message__next + MESSAGE_MAX - 1) % MESSAGE_MAX;
-
-	/* Get the last message text */
-	s = &message__buf[message__ptr[x]];
-
-	/* Last message repeated? */
-	if (streq(str, s))
+	// If the message is the same as the last message,
+	// we just increment the counter instead of adding
+	// the message.
+	if ((!buf->empty()) && (buf->back().text == str))
 	{
-		/* Increase the message count */
-		message__count[x]++;
-
-		/* Success */
-		return;
-	}
-
-
-	/*** Step 3 -- Attempt to optimize ***/
-
-	/* Limit number of messages to check */
-	k = message_num() / 4;
-
-	/* Limit number of messages to check */
-	if (k > MESSAGE_MAX / 32) k = MESSAGE_MAX / 32;
-
-	/* Check the last few messages (if any to count) */
-	for (i = message__next; k; k--)
-	{
-		u16b q;
-
-		cptr old;
-
-		/* Back up and wrap if needed */
-		if (i-- == 0) i = MESSAGE_MAX - 1;
-
-		/* Stop before oldest message */
-		if (i == message__last) break;
-
-		/* Extract "distance" from "head" */
-		q = (message__head + MESSAGE_BUF - message__ptr[i]) % MESSAGE_BUF;
-
-		/* Do not optimize over large distance */
-		if (q > MESSAGE_BUF / 2) continue;
-
-		/* Access the old string */
-		old = &message__buf[message__ptr[i]];
-
-		/* Compare */
-		if (!streq(old, str)) continue;
-
-		/* Get the next message index, advance */
-		x = message__next++;
-
-		/* Handle wrap */
-		if (message__next == MESSAGE_MAX) message__next = 0;
-
-		/* Kill last message if needed */
-		if (message__next == message__last) message__last++;
-
-		/* Handle wrap */
-		if (message__last == MESSAGE_MAX) message__last = 0;
-
-		/* Assign the starting address */
-		message__ptr[x] = message__ptr[i];
-		message__color[x] = color;
-		message__count[x] = 1;
-
-		/* Success */
+		buf->back().count += 1;
 		return;
 	}
 
+	// Push onto the end of the buffer.
+	message message;
+	message.color = color;
+	message.count = 1;
+	message.text = str;
+	buf->push_back(message);
+}
 
-	/*** Step 4 -- Ensure space before end of buffer ***/
-
-	/* Kill messages and Wrap if needed */
-	if (message__head + n + 1 >= MESSAGE_BUF)
-	{
-		/* Kill all "dead" messages */
-		for (i = message__last; TRUE; i++)
-		{
-			/* Wrap if needed */
-			if (i == MESSAGE_MAX) i = 0;
-
-			/* Stop before the new message */
-			if (i == message__next) break;
-
-			/* Kill "dead" messages */
-			if (message__ptr[i] >= message__head)
-			{
-				/* Track oldest message */
-				message__last = i + 1;
-			}
-		}
-
-		/* Wrap "tail" if needed */
-		if (message__tail >= message__head) message__tail = 0;
-
-		/* Start over */
-		message__head = 0;
-	}
-
-
-	/*** Step 5 -- Ensure space before next message ***/
-
-	/* Kill messages if needed */
-	if (message__head + n + 1 > message__tail)
-	{
-		/* Grab new "tail" */
-		message__tail = message__head + n + 1;
-
-		/* Advance tail while possible past first "nul" */
-		while (message__buf[message__tail - 1]) message__tail++;
-
-		/* Kill all "dead" messages */
-		for (i = message__last; TRUE; i++)
-		{
-			/* Wrap if needed */
-			if (i == MESSAGE_MAX) i = 0;
-
-			/* Stop before the new message */
-			if (i == message__next) break;
-
-			/* Kill "dead" messages */
-			if ((message__ptr[i] >= message__head) &&
-			                (message__ptr[i] < message__tail))
-			{
-				/* Track oldest message */
-				message__last = i + 1;
-			}
-		}
-	}
-
-
-	/*** Step 6 -- Grab a new message index ***/
-
-	/* Get the next message index, advance */
-	x = message__next++;
-
-	/* Handle wrap */
-	if (message__next == MESSAGE_MAX) message__next = 0;
-
-	/* Kill last message if needed */
-	if (message__next == message__last) message__last++;
-
-	/* Handle wrap */
-	if (message__last == MESSAGE_MAX) message__last = 0;
-
-
-
-	/*** Step 7 -- Insert the message text ***/
-
-	/* Assign the starting address */
-	message__ptr[x] = message__head;
-	message__color[x] = color;
-	message__count[x] = 1;
-
-	/* Append the new part of the message */
-	for (i = 0; i < n; i++)
-	{
-		/* Copy the message */
-		message__buf[message__head + i] = str[i];
-	}
-
-	/* Terminate */
-	message__buf[message__head + i] = '\0';
-
-	/* Advance the "head" pointer */
-	message__head += n + 1;
+void message_add(message const &message)
+{
+	buffer()->push_back(message);
 }
diff --git a/src/messages.hpp b/src/messages.hpp
index 22943ab9..99edd0e2 100644
--- a/src/messages.hpp
+++ b/src/messages.hpp
@@ -1,9 +1,28 @@
 #pragma once
 
 #include "h-basic.h"
+#include "message.hpp"
 
-void message_init();
+/**
+ * Get the current number of messages.
+ */
 s16b message_num();
-cptr message_str(int age);
-byte message_color(int age);
+
+/**
+ * Get message of given age. Age must be
+ * in the half-open interval [0, message_num).
+ *
+ * The reference is only valid as long as
+ * no messages are added.
+ */
+message const &message_at(int age);
+
+/**
+ * Add a message.
+ */
 void message_add(cptr msg, byte color);
+
+/**
+ * Add a message.
+ */
+void message_add(message const &);
diff --git a/src/util.cc b/src/util.cc
index 3c358052..6dfbca65 100644
--- a/src/util.cc
+++ b/src/util.cc
@@ -2352,6 +2352,23 @@ static int complete_command(char *buf, int clen, int mlen)
 }
 
 
+extern bool askfor_aux(std::string *buf, std::size_t max_len)
+{
+	// Buffer
+	char cstr[1024];
+	// Sanity
+	assert(max_len < sizeof(cstr));
+	// Copy into temporary buffer
+	cstr[buf->size()] = '\0';
+	buf->copy(cstr, std::string::npos);
+	// Delegate
+	bool result  = askfor_aux(cstr, max_len);
+	// Copy back
+	(*buf) = cstr;
+	// Done
+	return result;
+}
+
 /*
 * Get some input at the cursor location.
 * Assume the buffer is initialized to a default string.
diff --git a/src/util.hpp b/src/util.hpp
index 2953ca11..eafe4f31 100644
--- a/src/util.hpp
+++ b/src/util.hpp
@@ -47,6 +47,7 @@ extern void text_out(cptr str);
 extern void text_out_c(byte a, cptr str);
 extern void clear_from(int row);
 extern int ask_menu(cptr ask, const std::vector<std::string> &items);
+extern bool askfor_aux(std::string *buf, std::size_t max_len);
 extern bool_ askfor_aux(char *buf, int len);
 extern bool_ askfor_aux_with_completion(char *buf, int len);
 extern bool_ get_string(cptr prompt, char *buf, int len);
diff --git a/src/xtra1.cc b/src/xtra1.cc
index e2ae994b..6005deee 100644
--- a/src/xtra1.cc
+++ b/src/xtra1.cc
@@ -1224,8 +1224,11 @@ void fix_message(void)
 		/* Dump messages */
 		for (i = 0; i < h; i++)
 		{
+			auto message = message_at(i);
+			auto text_with_count = message.text_with_count();
+
 			/* Dump the message on the appropriate line */
-			display_message(0, (h - 1) - i, strlen(message_str((s16b)i)), message_color((s16b)i), message_str((s16b)i));
+			display_message(0, (h - 1) - i, text_with_count.size(), message.color, text_with_count.c_str());
 
 			/* Cursor */
 			Term_locate(&x, &y);