From ce62a76e4570b6368384b3995c1ba106389df454 Mon Sep 17 00:00:00 2001
From: Adam Spragg <adam@spra.gg>
Date: Wed, 18 May 2022 10:42:10 +0100
Subject: Sort entries in Format 1 files by path, ASCIIbetically.

This ensures that the files are stable, and not subject to the order in
which the OS returns directory entries. This should prevent unnecessary
changes, and therefore unnecessary merge conflicts.
---
 FILEFORMAT_1    | 16 ++++++++++++
 src/metaentry.c | 80 ++++++++++++++++++++++++++++++++++++++++-----------------
 2 files changed, 73 insertions(+), 23 deletions(-)

diff --git a/FILEFORMAT_1 b/FILEFORMAT_1
index b16d85a..189cc84 100644
--- a/FILEFORMAT_1
+++ b/FILEFORMAT_1
@@ -86,3 +86,19 @@ such as RTL/LTR marks (U+200E/U+200F) to prevent the possibility of "Trojan
 Source" type attacks.
 
 (See <https://lwn.net/Articles/874951/> for more info on "Trojan Source")
+
+
+### Sorting
+
+To generate stable metatdata files that do not depend on the order that files
+are returned by `readdir()`, which would producing spurious diffs, sort entries
+by path ASCIIbetically, as with `strcmp(3)`. But we don't require metadata files
+to be sorted when reading them.
+
+If we read two entries for the same path, the results are currently unspecified.
+
+Users should probably avoid sorting Format 1 files with standard tools like
+`sort(1)`, as the HEADER line must always be first, and also URL-encoded
+characters will throw off the sort order. Also, tools like `sort` will typically
+sort according to the current locale, e.g. using `strcoll(3)` rather than
+`strcmp()`.
diff --git a/src/metaentry.c b/src/metaentry.c
index ed0e23d..7f1012f 100644
--- a/src/metaentry.c
+++ b/src/metaentry.c
@@ -432,50 +432,84 @@ mentries_tofile_v0(const struct metahash *mhash, FILE * to)
 	}
 }
 
+/* Compare two mentries by path */
+static int
+mentry_cmp_path(const struct metaentry *a, const struct metaentry *b)
+{
+	return strcmp(a->path, b->path);
+}
+
+/* Compare two mentries by path, as is sutiable for qsort(3) */
+static int
+mentry_cmp_path_q(const void *a, const void *b)
+{
+	return mentry_cmp_path(*((const struct metaentry **) a),
+			*((const struct metaentry **) b));
+}
+
 /* Stores metaentries to a Format 1 file */
 static void
 mentries_tofile_v1(const struct metahash *mhash, FILE * to)
 {
 	const struct metaentry *mentry;
-	int key;
+	const struct metaentry **entarr;
+	int key, entries = 0;
 	struct tm tm;
 	char tmbuf[20];
 	unsigned i;
 
-	fputc('\n', to);
+	for (key = 0; key < HASH_INDEXES; key++) {
+		for (mentry = mhash->bucket[key]; mentry; mentry = mentry->next) {
+			++entries;
+		}
+	}
 
+	entarr = xmalloc(entries * sizeof(struct metaentry *));
+	i = 0;
 	for (key = 0; key < HASH_INDEXES; key++) {
 		for (mentry = mhash->bucket[key]; mentry; mentry = mentry->next) {
-			write_string_url(mentry->path, to);
+			entarr[i++] = mentry;
+		}
+	}
 
-			fputc('\t', to);
-			write_string_url(mentry->owner, to);
+	qsort(entarr, entries, sizeof(struct metaentry *), mentry_cmp_path_q);
 
-			fputc('\t', to);
-			write_string_url(mentry->group, to);
+	fputc('\n', to);
 
-			fputc('\t', to);
-			fprintf(to, "%.6o", mentry->mode);
+	for (key = 0; key < entries; key++) {
+		mentry = entarr[key];
 
-			fputc('\t', to);
-			gmtime_r(&mentry->mtime, &tm);
-			strftime(tmbuf, sizeof(tmbuf), "%Y-%m-%dT%H:%M:%S", &tm);
-			fputs(tmbuf, to);
+		write_string_url(mentry->path, to);
 
-			fputc('.', to);
-			fprintf(to, "%.9ldZ", mentry->mtimensec);
+		fputc('\t', to);
+		write_string_url(mentry->owner, to);
 
-			for (i = 0; i < mentry->xattrs; i++) {
-				fputc('\t', to);
-				write_string_url(mentry->xattr_names[i], to);
-				fputc('\t', to);
-				write_binary_url(mentry->xattr_values[i],
-						mentry->xattr_lvalues[i], to);
-			}
+		fputc('\t', to);
+		write_string_url(mentry->group, to);
 
-			fputc('\n', to);
+		fputc('\t', to);
+		fprintf(to, "%.6o", mentry->mode);
+
+		fputc('\t', to);
+		gmtime_r(&mentry->mtime, &tm);
+		strftime(tmbuf, sizeof(tmbuf), "%Y-%m-%dT%H:%M:%S", &tm);
+		fputs(tmbuf, to);
+
+		fputc('.', to);
+		fprintf(to, "%.9ldZ", mentry->mtimensec);
+
+		for (i = 0; i < mentry->xattrs; i++) {
+			fputc('\t', to);
+			write_string_url(mentry->xattr_names[i], to);
+			fputc('\t', to);
+			write_binary_url(mentry->xattr_values[i],
+					mentry->xattr_lvalues[i], to);
 		}
+
+		fputc('\n', to);
 	}
+
+	free(entarr);
 }
 
 /* Stores metaentries to a file */
-- 
cgit v1.2.1