Support customized reordering in version sort

[Duy Nguyen <pclouds@gmail.com>]

On Fri, Feb 20, 2015 at 12:26:29AM -0800, Junio C Hamano wrote:
> On Thu, Feb 19, 2015 at 11:13 PM, Jeff King <peff@peff.net> wrote:
> 
> >> There is debian bug 777690 [1] that's basically about making tag's
> >> version sort aware about -rc, -pre suffixes. I imagine it would touch
> >> versioncmp.c and builtin/tag.c (to retrieve the suffixes from config
> >> file).
> >>
> >> [1] https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=777690
> >
> > I think that's a reasonable thing to work on, but it's too big for a
> > microproject and too small for a GSoC.
> 
> That is certainly too big as a Micro, but I do not think it is too small
> for GSoC, if it is to be done right (meaning, not just implementing an
> arbitrary version comparison hardwired, but design how to make it
> extensible).

I did write "maybe more of mini-size than micro" then looked at the
micro list again and somehow decided to delete that. Anyway while I
still have my attention on it, might as well do it.

My idea is to make it easy for the user to change the sort algorithm.
And it's probably intuitive to just substitute a string with
something. So if "1-rc1" is put incorrectly before "1.1" and you
realize that "1.999" ought to be the last one before "2". You could
tell git to internally replace "1-rc1" with "1.999".

This patch does that. The user feeds substitution rules via
versionsort.substitute config keys, e.g.

    git config versionsort.substitute "-rc .999"

Performance is not a concern because I don't think people would throw
100k tags to it. There are two issues I'm aware of but not addressed:

 - the order of substitution matters, but right now it's up in the air
 - case-sensitiveness may surprise users

-- 8< --
diff --git a/versioncmp.c b/versioncmp.c
index 7511e08..2419e38 100644
--- a/versioncmp.c
+++ b/versioncmp.c
@@ -1,4 +1,5 @@
 #include "cache.h"
+#include "strbuf.h"
 
 /*
  * versioncmp(): copied from string/strverscmp.c in glibc commit
@@ -20,6 +21,57 @@
 #define  CMP    2
 #define  LEN    3
 
+struct subst_rule
+{
+	const char *before;
+	const char *after;
+};
+static struct subst_rule *rules;
+static int rule_nr, rule_alloc;
+
+static int versioncmp_config(const char *k, const char *v, void *cb)
+{
+	char *p, *s;
+	if (strcmp(k, "versionsort.substitute"))
+		return 0;
+	ALLOC_GROW(rules, rule_nr + 1, rule_alloc);
+	s = xstrdup(v);
+	p = strchr(s, ' ');
+	if (!p)
+		return error("missing space in %s", v);
+	*p = '\0';
+	rules[rule_nr].before = s;
+	rules[rule_nr].after = p + 1;
+	rule_nr++;
+	return 0;
+}
+
+static char *substitute(const unsigned char **strp)
+{
+	struct strbuf sb = STRBUF_INIT;
+	const char *str = (const char *)*strp;
+	int i;
+	if (!rules) {
+		rules = xmalloc(sizeof(*rules));
+		rule_alloc = 1;
+		git_config(versioncmp_config, NULL);
+	}
+	for (i = 0; i < rule_nr; i++) {
+		const struct subst_rule *r = rules + i;
+		const char *p = strstr(str, r->before);
+		if (!p)
+			continue;
+		if (!sb.len)
+			strbuf_addstr(&sb, str);
+		strbuf_splice(&sb, p - str, strlen(r->before),
+			      r->after, strlen(r->after));
+		str = sb.buf;
+	}
+	if ((const unsigned char *)str == *strp)
+		return NULL;
+	*strp = (const unsigned char *)sb.buf;
+	return sb.buf;
+}
 
 /*
  * Compare S1 and S2 as strings holding indices/version numbers,
@@ -32,6 +84,7 @@ int versioncmp(const char *s1, const char *s2)
 {
 	const unsigned char *p1 = (const unsigned char *) s1;
 	const unsigned char *p2 = (const unsigned char *) s2;
+	char *free1, *free2;
 	unsigned char c1, c2;
 	int state, diff;
 
@@ -58,6 +111,8 @@ int versioncmp(const char *s1, const char *s2)
 
 	if (p1 == p2)
 		return 0;
+	free1 = substitute(&p1);
+	free2 = substitute(&p2);
 
 	c1 = *p1++;
 	c2 = *p2++;
@@ -75,6 +130,10 @@ int versioncmp(const char *s1, const char *s2)
 	}
 
 	state = result_type[state * 3 + (((c2 == '0') + (isdigit (c2) != 0)))];
+	if (state != LEN) {
+		free(free1);
+		free(free2);
+	}
 
 	switch (state) {
 	case CMP:
@@ -82,10 +141,16 @@ int versioncmp(const char *s1, const char *s2)
 
 	case LEN:
 		while (isdigit (*p1++))
-			if (!isdigit (*p2++))
+			if (!isdigit (*p2++)) {
+				free(free1);
+				free(free2);
 				return 1;
+			}
 
-		return isdigit (*p2) ? -1 : diff;
+		c2 = *p2;
+		free(free1);
+		free(free2);
+		return isdigit (c2) ? -1 : diff;
 
 	default:
 		return state;
-- 8< --