Maintain multi key references in sorted order

This is a step towards being able to reproduce the same database given
the same manual page tree.

* bootstrap.conf (gnulib_modules): Add stpcpy.
* libdb/db_lookup.c (name_ext_equals): Remove static; add pure
attribute.
(name_ext_compare): New function.
(list_extensions): Add entries in sorted order.
* libdb/db_storage.h (name_ext_equals, name_ext_compare): Add
prototypes.
* libdb/db_store.c (make_extensions_reference): New function.
(dbstore): When building or updating multi key references, maintain them
in sorted order.
* NEWS.md: Document this.

5 files changed, 65 insertions, 8 deletions

diff --git a/NEWS.md b/NEWS.md
index d4c51440..332da3cf 100644
--- a/NEWS.md
+++ b/NEWS.md
@@ -13,6 +13,7 @@ Improvements:
 
  * Add more recognized case variants for localized versions of the `NAME`
    section.
+ * Maintain multi keys in sorted order, improving database reproducibility.
 
 man-db 2.10.2 (17 March 2022)
 =============================
diff --git a/bootstrap.conf b/bootstrap.conf
index 16c043ba..dc8e4792 100644
--- a/bootstrap.conf
+++ b/bootstrap.conf
@@ -69,6 +69,7 @@ gnulib_modules="
   sigprocmask
   stat-time
   stdbool
+  stpcpy
   strcase
   strcasestr
   strerror
diff --git a/libdb/db_lookup.c b/libdb/db_lookup.c
index db062597..66541d83 100644
--- a/libdb/db_lookup.c
+++ b/libdb/db_lookup.c
@@ -230,12 +230,21 @@ void split_content (MYDBM_FILE dbf, char *cont_ptr, struct mandata *pinfo)
 	pinfo->addr = cont_ptr;
 }
 
-static bool name_ext_equals (const void *elt1, const void *elt2)
+bool ATTRIBUTE_PURE name_ext_equals (const void *elt1, const void *elt2)
 {
 	const struct name_ext *ref1 = elt1, *ref2 = elt2;
 	return STREQ (ref1->name, ref2->name) && STREQ (ref1->ext, ref2->ext);
 }
 
+int ATTRIBUTE_PURE name_ext_compare (const void *elt1, const void *elt2)
+{
+	const struct name_ext *ref1 = elt1, *ref2 = elt2;
+	int name_cmp = strcmp (ref1->name, ref2->name);
+	if (name_cmp)
+		return name_cmp;
+	return strcmp (ref1->ext, ref2->ext);
+}
+
 /* Extract all of the names/extensions associated with this key. Each case
  * variant of a name will be returned separately.
  *
@@ -260,7 +269,7 @@ gl_list_t list_extensions (char *data)
 		/* Don't copy these; they will point into the given string. */
 		name_ext->name = name;
 		name_ext->ext = ext;
-		gl_list_add_last (list, name_ext);
+		gl_sortedlist_add (list, name_ext_compare, name_ext);
 	}
 
 	debug ("found %zu names/extensions\n", gl_list_size (list));
diff --git a/libdb/db_storage.h b/libdb/db_storage.h
index be01cc37..87afe802 100644
--- a/libdb/db_storage.h
+++ b/libdb/db_storage.h
@@ -103,6 +103,8 @@ extern datum make_multi_key (const char *page, const char *ext);
 #define infoalloc() XZALLOC (struct mandata)
 
 extern char *name_to_key (const char *name);
+bool name_ext_equals (const void *elt1, const void *elt2);
+int name_ext_compare (const void *elt1, const void *elt2);
 /* Returns a list of struct name_ext. */
 extern gl_list_t list_extensions (char *data);
 extern void gripe_replace_key (MYDBM_FILE dbf, const char *data);
diff --git a/libdb/db_store.c b/libdb/db_store.c
index 213ae63e..505207fd 100644
--- a/libdb/db_store.c
+++ b/libdb/db_store.c
@@ -33,6 +33,8 @@
 
 #include "attribute.h"
 #include "error.h"
+#include "gl_array_list.h"
+#include "gl_xlist.h"
 #include "timespec.h"
 #include "xalloc.h"
 #include "xvasprintf.h"
@@ -40,6 +42,7 @@
 #include "manconfig.h"
 
 #include "debug.h"
+#include "glcontainers.h"
 
 #include "mydbm.h"
 #include "db_storage.h"
@@ -164,6 +167,27 @@ static datum make_content (struct mandata *in)
 	return cont;
 }
 
+/* The complement of list_extensions. */
+static char *make_extensions_reference (gl_list_t refs)
+{
+	struct name_ext *ref;
+	size_t len = 0;
+	char *data, *cur;
+
+	GL_LIST_FOREACH (refs, ref)
+		len += strlen (ref->name) + strlen (ref->ext) + 2;
+
+	cur = data = xmalloc (len + 1);
+	GL_LIST_FOREACH (refs, ref) {
+		*cur++ = '\t';
+		cur = stpcpy (cur, ref->name);
+		*cur++ = '\t';
+		cur = stpcpy (cur, ref->ext);
+	}
+
+	return data;
+}
+
 /*
  Any one of three situations can occur when storing some data.
 
@@ -197,6 +221,8 @@ static datum make_content (struct mandata *in)
 int dbstore (MYDBM_FILE dbf, struct mandata *in, const char *base)
 {
 	datum oldkey, oldcont;
+	gl_list_t refs;
+	struct name_ext *ref;
 	char *value;
 
 	memset (&oldkey, 0, sizeof oldkey);
@@ -268,9 +294,15 @@ int dbstore (MYDBM_FILE dbf, struct mandata *in, const char *base)
 		MYDBM_FREE_DPTR (newkey);
 		MYDBM_FREE_DPTR (newcont);
 
-		value = xasprintf (
-			"%s\t%s\t%s", MYDBM_DPTR (oldcont), base, in->ext);
-		assert (value);
+		refs = list_extensions (MYDBM_DPTR (oldcont) + 1);
+		ref = XMALLOC (struct name_ext);
+		/* Not copied. */
+		ref->name = base;
+		ref->ext = in->ext;
+		gl_sortedlist_add (refs, name_ext_compare, ref);
+		value = make_extensions_reference (refs);
+		gl_list_free (refs);
+
 		MYDBM_SET (newcont, value);
 		MYDBM_FREE_DPTR (oldcont);
 
@@ -359,9 +391,21 @@ int dbstore (MYDBM_FILE dbf, struct mandata *in, const char *base)
 
 		/* Now build a simple reference to the above two items */
 
-		value = xasprintf (
-			"\t%s\t%s\t%s\t%s", old_name, old.ext, base, in->ext);
-		assert (value);
+		refs = gl_list_create_empty (GL_ARRAY_LIST, name_ext_equals,
+					     NULL, plain_free, true);
+		ref = XMALLOC (struct name_ext);
+		/* Not copied. */
+		ref->name = old_name;
+		ref->ext = old.ext;
+		gl_sortedlist_add (refs, name_ext_compare, ref);
+		ref = XMALLOC (struct name_ext);
+		/* Not copied. */
+		ref->name = base;
+		ref->ext = in->ext;
+		gl_sortedlist_add (refs, name_ext_compare, ref);
+		value = make_extensions_reference (refs);
+		gl_list_free (refs);
+
 		MYDBM_SET (newcont, value);
 
 		if (MYDBM_REPLACE (dbf, oldkey, newcont))