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

[Junio C Hamano <gitster@pobox.com>]

Jeff King <peff@peff.net> writes:

> On Thu, Dec 08, 2016 at 03:23:54PM +0100, SZEDER Gábor wrote:
>
>> > 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.

I also had worries about transitiveness but couldn't break it after
trying for some time.  I find your pre-parsing suggestion a great
one, not from the point of view of performance, but because I would
imagine that the resulting logic would become a lot easier to
understand.