Re: [bug report] git-am applying maildir patches in reverse

[Jeff King <peff@peff.net>]

On Fri, Mar 01, 2013 at 03:24:42PM -0800, Junio C Hamano wrote:

> Jeff King <peff@peff.net> writes:
> 
> > On Fri, Mar 01, 2013 at 05:52:31PM -0500, Jeff King wrote:
> > ...
> >> The maildir spec explicitly says that readers should not make
> >> assumptions about the content of the filenames. Mutt happens to write
> >> them as:
> >> 
> >>   ${epoch_seconds}.${pid}_${seq}.${host}
> >> 
> >> so in practice, sorting them kind of works. Except that ...
> >> << it does not work >> ...
> > That ordering is not necessarily useful.
> > ...
> > So it is somewhat against the maildir spec, but I think in practice it
> > would help.
> 
> I do not think it would help, unless these epoch_seconds are the
> sender timestamps.  And the number of digits in epoch-seconds for
> recent messages would be the same, so ordering textually would be
> sufficient if ordering by timestamp were.

The epoch_seconds are the time of writing into the maildir. They will
typically all be the same, unless your system is very slow, or you are
writing a really long patch series. The PID likewise should be the same
for a given series. It's the sequence number that is the interesting bit
to sort numerically (for mutt, anyway; ditto for dovecot).

The patch below seems to fix the issue for me with mutt. It's possible
that it regresses another case (which has numbers, but really wants them
sorted as byte strings), but I find that unlikely. If you're
zero-padding your numbers this will still work, and if you're not, then
you likely have no meaningful sort order at all.

-- >8 --
Subject: [PATCH] mailsplit: sort maildir filenames more cleverly

A maildir does not technically record the order in which
items were placed into it. That means that when applying a
patch series from a maildir, we may get the patches in the
wrong order. We try to work around this by sorting the
filenames. Unfortunately, this may or may not work depending
on the naming scheme used by the writer of the maildir.

For instance, mutt will write:

  ${epoch_seconds}.${pid}_${seq}.${host}

where we have:

  - epoch_seconds: timestamp at which entry was written
  - pid: PID of writing process
  - seq: a sequence number to ensure uniqueness of filenames
  - host: hostname

None of the numbers are zero-padded. Therefore, when we sort
the names as byte strings, entries that cross a digit
boundary (e.g., 10) will sort out of order.  In the case of
timestamps, it almost never matters (because we do not cross
a digit boundary in the epoch time very often these days).
But for the sequence number, a 10-patch series would be
ordered as 1, 10, 2, 3, etc.

To fix this, we can use a custom sort comparison function
which traverses each string, comparing chunks of digits
numerically, and otherwise doing a byte-for-byte comparison.
That would sort:

  123.456_1.bar
  123.456_2.bar
  ...
  123.456_10.bar

according to the sequence number. Since maildir does not
define a filename format, this is really just a heuristic.
But it happens to work for mutt, and there is a reasonable
chance that it will work for other writers, too (at least as
well as a straight sort).

Signed-off-by: Jeff King <peff@peff.net>
---
 builtin/mailsplit.c | 22 ++++++++++++++++++++++
 1 file changed, 22 insertions(+)

diff --git a/builtin/mailsplit.c b/builtin/mailsplit.c
index 2d43278..772c668 100644
--- a/builtin/mailsplit.c
+++ b/builtin/mailsplit.c
@@ -130,6 +130,26 @@ static int populate_maildir_list(struct string_list *list, const char *path)
 	return 0;
 }
 
+static int maildir_filename_cmp(const char *a, const char *b)
+{
+	while (1) {
+		if (isdigit(*a) && isdigit(*b)) {
+			long int na, nb;
+			na = strtol(a, (char **)&a, 10);
+			nb = strtol(b, (char **)&b, 10);
+			if (na != nb)
+				return na - nb;
+			/* strtol advanced our pointers */
+		}
+		else {
+			if (*a != *b)
+				return *a - *b;
+			a++;
+			b++;
+		}
+	}
+}
+
 static int split_maildir(const char *maildir, const char *dir,
 	int nr_prec, int skip)
 {
@@ -139,6 +159,8 @@ static int split_maildir(const char *maildir, const char *dir,
 	int i;
 	struct string_list list = STRING_LIST_INIT_DUP;
 
+	list.cmp = maildir_filename_cmp;
+
 	if (populate_maildir_list(&list, maildir) < 0)
 		goto out;
 
-- 
1.8.1.39.gbb3bf60