unstable sort in case where versions only differ in their build

[keshav-space]

We're observing unstable sort in cases where versions only differ in their build.

>>> from semantic_version import Version
>>> v1 = Version("2.0.12+123")
>>> v2 = Version("2.0.12+1")
>>> v3 = Version("2.0.12+321")
>>> v4 = Version("2.0.12+22")
>>> sorted([v1,v2,v3,v4])
[Version('2.0.12+123'), Version('2.0.12+1'), Version('2.0.12+321'), Version('2.0.12+22')]
>>> sorted([v4,v2,v1,v3])
[Version('2.0.12+22'), Version('2.0.12+1'), Version('2.0.12+123'), Version('2.0.12+321')]
>>> sorted([v1,v2,v3,v4])
[Version('2.0.12+123'), Version('2.0.12+1'), Version('2.0.12+321'), Version('2.0.12+22')]
>>>

This is due to Semver mandating that the versions differing only in their build must have the same precedence.
Nevertheless, we have an implementation in node which does consider build to yield a stable sorting.
Can we have something similar here?

[rbarrois]

That's indeed an interesting issue ;)

I concur that one would expect the following to be true:

def ensure_stable_sort(seq):
    """Ensure sort stability.

    Once sorted, all permutations of a sequence should be equal;
    i.e objects at position i are always equal -- though they may not have the same "id".
    """
    shuffled = random.sample(seq, k=len(seq))  # See note in https://docs.python.org/3/library/random.html#random.shuffle
    for orig, shuf in zip(sorted(seq), sorted(shuffled)):
        assert orig == shuf

Here, as you've shown, that property doesn't hold.

My idea would be to have a mechanism for comparing versions that doesn't apply any formalized semantics on the build version.
For instance, one could use some hash of the build component as a precedence key: it's deterministic, stable, yet opaque from the user. The only issue would be that the hash will be different across runs or processes (see the note about PYTHONHASHSEED in python(1)).

What do you think? Is this consistent with the behaviour you would expect?

[keshav-space]

Hash would work for a particular run.
But we're expecting consistent sorting across runs/devices. Which IMO isn't achievable using hash.
We might need some alphanumeric comparison of the build itself.

What do you say @pombredanne?

[keshav-space]

Or maybe we can instead use something like SHA-256 which is guaranteed to be same across runs/devices.

[pombredanne]

The only issue would be that the hash will be different across runs or processes

@rbarrois this would IMHO break the stability property. Sort stability is expected to apply across Python versions and implementations.

The thing it is hard to get this right:

1. It is quite nice to use the standard rich comparison operators such that version are comparable with >, < and so on. This is the basis of this implementation (and the basis of most if all version handling libraries I know of... we looked at quite a few ;) for univers)
2. semver is peculiar is that the "build" segment is not significant for determining precedence.
3. this library implements a correct hash() that includes the build segment correctly

• in contrast this other library at https://github.com/python-semver/python-semver that we had to include in univers because it was a dep of a nuget version parser we included does NOT include the build in the hash, which triggers a truckload of issues https://github.com/python-semver/python-semver/blob/d06388727caa4999cf224b94251128ceaf86b051/src/semver/version.py#L495 ignored the build segment in the hash().

4. this library and the other libraries both ignore the build segment in sorting.
5. this library uses the all segments in equality as it should

With this said, here is my suggestion:

• the semver spec that the build does not matter for precedence. Therefore it does not matter too that this is used. Since two builds will be equivalent which one is picked over another one does not matter and is still compliant with the spec. So the build can be included in the precedence and no harm is done
• you could add a new method to the version that returns True if two versions are identical ignoring build say is_equivalent(self, other)
• when you do matching you can also ignore the build segment: tow version can be equivalent, but neither equal nor identical (same hash). But two versions that are identical hash-wise should be equal IMHO.

[pombredanne]

Just to restate my key point that may not be obvious: since the build does not matter in semver ordering, using here a stable order including build is still compliant because order does not matter .

[rbarrois]

@pombredanne Thanks for the details. I agree that any ordering is valid.
However, I'm afraid that, were I to order build numbers lexically, users would come to rely on that behaviour. The suggestion by @keshav-space to use a SHA hash has the benefit of using an opaque hash, alleviating that concern.

Hence, I think I'll move forward with a SHA-like hash of the build for the precedence key (maybe opting for a faster-to-compute one for performance concerns).
Would that match your expectations?

[pombredanne]

Would that match your expectations?

Not really. 😇

Using a checksum to hide the ordering will not hide anything IMHO. Unless you take the library closed source ;) you are not hiding anything from anyone. So I could read the code and come to rely on a certain stable order based on whatever hashing you picked.
IMHO KISS, and in earnest I would find it super surprising if the build ordering was not based the plain sort of the strings.
Say you have 1.2.3+1 and 1.2.3+2 ... it begs to be sorted by 1 then 2. Anything else will be a (bad) surprise and a head scratcher IMHO.

And -- this is key here-- this is also the observed behaviour of node-semver See https://github.com/npm/node-semver/blob/4907647d169948a53156502867ed679268063a9f/test/functions/sort.js#L4 and https://github.com/npm/node-semver/blob/f1e4e293de1ad73fa250336bfcfb9b4142d21d1b/classes/semver.js#L152

[rbarrois]

I see your point; however, I don't want to have the discussion of *Should 1.0.0+1.1 sort before or after 1.0.0+11.1?

Until that point is discussed and settled in the semver spec, I'd rather opt for an opaque ordering (not obfuscated, just not lexical).

As a side note, this was somewhat sidestepped in the SemVer repo: semver/semver#89.

[pombredanne]

@rbarrois re:

Until that point is discussed and settled in the semver spec, I'd rather opt for an opaque ordering (not obfuscated, just not lexical).

This is your call of course, but this means that this library will not match the node-semver behaviour and we will need to either subclass or fork it as this is a primary use case for univers. For instance, it will not pass the same tests as node-semver.

I am in earnest less interested in the semver spec per-se than its prominent implementations because the spec is mostly interpreted loosely by its key users. So much so that at this stage I very much doubt that there is any "true-to-spec" implementation of semver based on our experience with the univers library and vulnerable code: there is IMHO roughly one slightly different take on semver in each implementation.

[rbarrois]

@pombredanne After giving this some more thought, I think that using the same ordering rules as for components of the "prerelease" bits (i.e according to the rules in section 11.4 of Semver) will be the least-surprising way to go.

I'll have to add some mentions on that topic in the docs, though :)