Re: [PATCHv2 0/7] Fix and generalize version sort reordering

From: Jeff King <peff@peff.net>
Date: Dec 14, 2016, 17:08 UTC
Message-ID: <20161214170852.bzh5pyl4bov6rwbt@sigill.intra.peff.net>
In-Reply-To: <20161208142401.1329-1-szeder.dev@gmail.com>

On Thu, Dec 08, 2016 at 03:23:54PM +0100, SZEDER Gábor wrote:

Show 13 quoted lines

> > With my patches it looks like this:
> > 
> >     $ git -c versionsort.prereleasesuffix=-pre \
> >           -c versionsort.prereleasesuffix=-prerelease \
> >           tag -l --sort=version:refname
> >     v1.0.0-prerelease1
> >     v1.0.0-pre1
> >     v1.0.0-pre2
> >     v1.0.0
> 
> And when there happen to be more than one matching suffixes starting
> at the same earliest position, then we should pick the longest of
> them.  The new patch 6/7 implements this behavior.

The whole approach taken by the suffix code (before your patches) leaves me with the nagging feeling that the comparison is not always going to be transitive (i.e., that "a < b && b < c" does not always imply "a < c"), which is going to cause nonsensical sorting results.

And that may be part of the issue your 6/7 fixes.

I spent some time playing with this the other day, though, and couldn't come up with a specific example that fails the condition above.

It just seems like the whole thing would conceptually easier if we pre-parsed the versions into a sequence of elements, then the comparison between any two elements would just walk that sequence. The benefit there is that you can implement whatever rules you like for the parsing (like "prefer longer suffixes to shorter"), but you know the comparison will always be consistent.

It would also be more efficient, I think (it seems like the sort is O(nr_tags * lg(nr_tags) * nr_suffixes) due to parsing suffixes in the comparator). Though that probably doesn't matter much in practice.

I dunno. I think maybe your 6/7 has converged on an equivalent behavior. And I am certainly not volunteering to re-write it, so if what you have works, I'm not opposed to it.

-Peff